DocumentCode :
2736094
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
fYear :
1999
fDate :
18-21 Jan 1999
Firstpage :
81
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;
fLanguage :
English
Publisher :
ieee
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
Type :
conf
DOI :
10.1109/ASPDAC.1999.759715
Filename :
759715
Link To Document :
بازگشت