(A) study on circuit netlist partitioning with spectral method

Abstract

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...