A Hierarchical Circuit Clustering Algorithm with Stable Performance

Seung-June KYOUNG  Kwang-Su SEONG  In-Cheol PARK  Chong-Min KYUNG  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.9   pp.1987-1993
Publication Date: 1999/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: VLSI Design Technology and CAD
Keyword: 
VLSI,  CAD,  partitioning,  clustering,  

Full Text: PDF>>
Buy this Article



Summary: 
Clustering is almost essential in improving the performance of iterative partitioning algorithms. In this paper, we present a clustering algorithm based on the following observation: if a group of cells is assigned to the same partition in numerous local optimum solutions, it is desirable to merge the group into a cluster. The proposed algorithm finds such a group of cells from randomly generated local optimum solutions and merges it into a cluster. We implemented a multilevel bipartitioning algorithm (MBP) based on the proposed clustering algorithm. For MCNC benchmark netlists, MBP improves the total average cut size by 9% and the total best cut size by 3-4%, compared with the previous state-of-the-art partitioners.