(A) study on circuit netlist partitioning with spectral method = 스펙트럴 방법을 이용한 회로분할에 관한 연구

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 199
  • Download : 0
The essence of partitioning is to divide a circuit or a system into appropriate number of components. As the system complexity is enormously increased in the past several years, partitioning has become more and more important task. Partitioning divides a system into a number of smaller sub-blocks which are manageable with existing CAD tools and technology. This thesis describes two partitioning approaches with spectral method which uses the eigenvectors and the eigenvalues of the Laplacian of a graph. The first approach is multi-way scaled cost partitioning based on linear ordering. Recently, one-dimensional linear ordering scheme has received increasing attention. Some partitioning algorithm has shown optimal result for a given linear ordering. Thus netlist partitioning with respect to scaled cost can be transformed to the linear ordering problem. In this thesis, two linear ordering algorithms are proposed. The first algorithm called CBLO improved the quality of linear ordering by clustering. CBLO consists of global ordering and local ordering. The global ordering again consists of cluster formation and inter-cluster ordering. As CBLO has more global partitioning information than previous approaches by clustering, the proposed algorithm produces better result in multi-way partitioning than previous algorithms. The second algorithm called LIME constructs linear ordering by merging two segments into new one until only one segment remains. The final resultant segment corresponds to the linear ordering. In this algorithm, it is important to select two segments to be merged. The proposed cost function selecting two segments can produce optimal(q-1) segments for a given q segments in terms of scaled cost function. LIME also runs extremely fast, because it exploits sparsity of netlist. Compared with the earlier work, LIME is eight times faster in producing linear ordering and yields an average of 17% improvement for the multi-way scaled cost partitioning. The secon...
Kyung, Chong-Minresearcher경종민researcher
한국과학기술원 : 전기및전자공학과,
Issue Date
114128/325007 / 000925170

학위논문(박사) - 한국과학기술원 : 전기및전자공학과, 1997.2, [ ix, 101 p. ]

Appears in Collection
Files in This Item
There are no files associated with this item.


  • mendeley


rss_1.0 rss_2.0 atom_1.0