Title :
An improved objective function for mincut circuit partitioning
Author :
Sechen, C. ; Chen, D.
Author_Institution :
Dept. of Electr. Eng., Yale Univ., New Haven, CT, USA
Abstract :
An improved objective function has been added to the Kernighan-Lin (1970), Fiduccia-Mattheyses (1982) (KLFM) partitioning algorithm. The time complexity of the enhanced KLFM algorithm remains linear in the number of pins, and there is essentially no change in the CPU time requirements. Based on circuit bipartitioning tests with ten industrial circuits, the number of nets cut was reduced by as much as 55% with the new objective function. The average reduction in nets cut was 38%.<>
Keywords :
circuit layout CAD; computational complexity; CPU time requirements; KLFM partitioning algorithm; circuit bipartitioning tests; min-cut partitioning; mincut circuit partitioning; objective function; time complexity; Central Processing Unit; Circuit testing; Integrated circuit interconnections; Pins; Read only memory;
Conference_Titel :
Computer-Aided Design, 1988. ICCAD-88. Digest of Technical Papers., IEEE International Conference on
Conference_Location :
Santa Clara, CA, USA
Print_ISBN :
0-8186-0869-2
DOI :
10.1109/ICCAD.1988.122558
