Title :
Faster and better spectral algorithms for multi-way partitioning
Author :
Chang, Jan-Yang ; Liu, Yu-Chen ; Wang, Ting-Chi
Author_Institution :
Dept. of Inf. & Comput. Eng., Chung Yuan Christian Univ., Chung Li, Taiwan
Abstract :
In this paper two faster and better spectral algorithms are presented for the multi-way circuit partitioning problem with the objective of minimizing the scaled cost. The problem can be approximately transformed into the vector partitioning problem by mapping each circuit component to a multi-dimensional vector. The common key idea of our two algorithms for solving the vector partitioning problem is to first treat the set of vectors as a cluster; and then repeatedly select a cluster which gives the maximum cost improvement among all the current clusters, and partition it into two new clusters. The bipartitioning process is continued until the number of clusters is equal to the required number of partitions. The experimental results indicate that the two algorithms significantly outperform MELO+DP-RP [3] in both the run time and partitioning result
Keywords :
VLSI; circuit CAD; integrated circuit design; logic CAD; logic partitioning; minimisation of switching nets; VLSI design; bipartitioning process; cost improvement; multi-way partitioning; run time; scaled cost; spectral algorithms; vector partitioning problem; Circuits; Clustering algorithms; Constraint optimization; Cost function; Dynamic programming; Iterative algorithms; Iterative methods; Partitioning algorithms; Vectors; Very large scale integration;
Conference_Titel :
Design Automation Conference, 1999. Proceedings of the ASP-DAC '99. Asia and South Pacific
Conference_Location :
Wanchai
Print_ISBN :
0-7803-5012-X
DOI :
10.1109/ASPDAC.1999.759715