New spectral methods for ratio cut partitioning

Partitioning of circuit netlists is important in many phases of VLSI design, ranging from layout to testing and hardware simulation. The ratio cut objective function [29] has received much attention since it naturally captures both min- cut and equipartition, the two traditional goals of partitioning. In this paper, we show that the second smallest eigenvalue of a matrix derived from the netlist gives a provably good approx- imation of the optimal ratio cut partition cost. We also dem- onstrate that fast Lanczos-type methods for

the sparse sym- metric eigenvalue problem are a robust basis for computing heuristic ratio cuts based on the eigenvector of this second ei- genvalue. Effective clustering methods are an immediate by- product of the second eigenvector computation, and are very successful on the “difficult” input classes proposed in the CAD literature. Finally, we discuss the very natural intersection graph representation of the circuit netlist as a basis for partitioning, and propose a heuristic based on spectral ratio cut partitioning of the netlist intersection graph. Our partitioning heuristics were tested on industry benchmark suites, and the results com- pare favorably with those of Wei and Cheng [29], 1321 in terms of both solution quality and runtime. This paper concludes by describing several types of algorithmic speedups and directiops for future work. I. PRELIMINARIES S SYSTEM complexity increases, a divide-and-con- A quer approach is used to keep the circuit design pro- cess tractable. This recursive decomposition of the syn- thesis problem is reflected in the hierarchical organization of boards, multi-chip modules, integrated circuits, and macro cells. As we move downward in the design hier- archy, signal delays typically decrease; for example, on- chip communication is faster than inter-chip communi- cation. Therefore, the traditional metric for the decom- position is the number of signal nets which cross between layout subproblems. Minimizing this number is the es- sence of partitioning. Any decision made early in the layout synthesis pro- cedure will constrain succeeding decisions, and hence good solutions to the placement, global routing, and de- tailed routing problems depend on the quality of the par- titioning algorithm. As noted by such authors as Donath Manuscript received June 9, 1991; revised December 12, 1991. This work was supported by the National Science Foundation under Grant MIP- 91 10696. A. B. Kahng is supported also by awational Science Foundation Young Investigator Award. This paper was recommended by Editor A. Dunlop. The authors are with the Department of Computer Science, University of California at Los Angeles, Los Angeles, CA 90024-1596. IEEE Log Number 9200832. [7] and Wei and Cheng [32], partitioning is basic to many fundamental CAD problems, including the following: Pacbging of designs: Logic is partitioned into blocks, subject to I/O bounds and constraints on block area; this is the canonical partitioning appli- cation at all levels of design, arising whenever .tech- nology improves and existing designs must be re- packaged onto higher-capacity blocks. Clustering analysis:...

Website: w.sliponline.org | Filesize: -
No of Page(s): 12
Download New spectral methods for ratio cut partitioning and - UCSD VLSI CAD.pdf