Title :
A general purpose, multiple-way partitioning algorithm
Author :
Yeh, Ching-Wei ; Cheng, Chung-Kuan ; Lin, Ting-Ting Y.
Author_Institution :
Dept. of Electr. Eng., Nat. Chung-Cheng Univ., Chiayi, Taiwan
fDate :
12/1/1994 12:00:00 AM
Abstract :
Multiple-way partitioning is an important extension of two-way partitioning as it provides a more natural and direct model for many partitioning applications. In this paper, we discuss several objective functions derived from such an extension and propose an iterative improvement algorithm to solve the multiple-way partitioning problem. The algorithm proceeds in three phases. The first phase employs a recursive ratio-cut scheme to group highly connected subcircuits into clusters. The second phase performs iterative improvement on the clustered circuit using a Dew net-based move model and a Primal-Dual refinement procedure. The third phase is the same as the second phase except that the iterative improvement is done on the original circuit. Experiments show good results in all tested cases
Keywords :
iterative methods; logic CAD; logic partitioning; network topology; recursive functions; Dew net-based move model; clustered circuit; highly connected subcircuits; iterative improvement algorithm; multiple-way partitioning algorithm; objective functions; primal-dual refinement procedure; recursive ratio-cut scheme; Algorithm design and analysis; Circuit simulation; Circuit testing; Clustering algorithms; Computer science; Iterative algorithms; Partitioning algorithms; Process design; Simulated annealing; Timing;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
