Multilevel circuit partitioning for computer-aided VLSI design

As designs become massively interconnect-dominated and present unmanageable instance complexities, circuit partitioning is recognized as a critical optimization problem in computer-aided VLSI design automation; the feasibility as well as the quality of the automatic placement and routing procedures heavily depends on the quality of partitioning solutions. In this dissertation, the weakness and the limitation of current partitioning techniques are identified, and new partitioning algorithms are suggested. Not only we define new metrics for additional qualities of partitioning solutions, but we also present novel partitioning techniques for large scale designs. First, we present a new multilevel circuit partitioning algorithm which is guided by design hierarchies. In addition to a flat netlist hypergraph, a logical design hierarchy is used as a guidance for multilevel partitioning. Using Rent’s exponent as a quality indicator for physical connectivities of the hierarchical elements, multilevel clustering scopes are guided (and dynamically restructured) by strongly connected hierarchical elements in the design hierarchy. By exploiting the design hierarchy, our algorithm produces higher quality solutions than conventional multilevel partitioners and the solutions are also significantly more stable over the multiple runs. Second, we define stability as an additional quality measure for partitioning solutions, and a new stable multiway partitioning algorithm is presented. Given a previous partitioning result P∗ on an original netlist hypergraph H∗ and a par- tially modified netlist hypergraph H, a new cost function with similarity factor is defined to produce a new partition P on H which is similar to the original partition P∗. We also present a multilevel version of the algorithm with multilevel restricted coarsening. The proposed partitioner is especially beneficial to engineering change order (ECO) applications, where partial modifications of a netlist are handled by the incremental methodology in a design iteration cycle. Third, we propose a new multilevel multiway partitioning approach which is aware of the resource utilization distribution, assuming the resource utilization per partitioned block is proportional to the logic occupation rate and required interconnection. A new quality, crowdedness, is defined as a virtual complexity metric where the physical size and the local connectivity of a partitioned block are combined as the weighted sum. Unlike conventional partitioners focusing on the overall intercon- nection minimization, which have wide variances in the crowdedness(equivalently, resource utilization) distribution, the proposed algorithm produces near-optimal so- lutions in terms of crowdedness distribution while overall interconnection quality is also improved. Lastly, we present an improved version of the multilevel partitioning which utilizes the cluster quality statistics from the multilevel clustering tree constructed during the coarsening phase. Though the multilevel partitioning paradigm is rela- tively robust, it has limited flexibility; while the partitioning solution is refined over multiple levels, the problem instance at each level totally relies on the construction of the multilevel clustering tree. In the proposed version of multilevel partitioner, the multilevel uncoarsening phase involves multi-rate unclustering, where some ill- formed intermediate clusters are identified earlier and unclustered at faster rates across the levels. The superiority of the suggested multilevel partitioner is justified by the experimental results.