loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Asia and South Pacific Design Automation Conference 1999 (ASP-DAC'99)
An Efficient Two-Level Partitioning Algorithm for VLSI Circuits
Wanchai, Hong Kong
January 18-January 21
ISBN: 0-7803-5012-X
Jong-Sheng Cherng, National Taiwan Univ., Taipei
Sao-Jie Chen, National Taiwan Univ., Taipei
Chia-Chun Tsai, National Taiwan Univ., Taipei
Jan-Ming Ho, Academia Sinica, Taipei, Taiwan
In this paper, a new two-level bipartitioning algorithm TLP, combining a hybrid clustering technique with an iterative improvement based partitioning process, is proposed. The hybrid clustering algorithm consisting of a local bottom-up clustering technique to merge modules and a global top-down ratio-cut technique for decomposition can be used to reduce the partitioning complexity and improve the performance. To generate a high-quality partitioning solution, a module migration based partitioning algorithm MMP is also proposed as the base partitioner for the TLP algorithm. The MMP algorithm implicitly promotes the move of clusters during the module migration processes by paying more attention to the neighbors of moved modules, relaxing the size constraints temporarily during the migration process, and controlling the module migration direction.
Experimental results obtained show that the TLP algorithm generates stable and high-quality partitioning results. The TLP algorithm improves the unstable property of module migration based algorithms such as FM [6] and STABLE [3] in terms of the average net cut value. On the other hand, TLP outperforms MELO [2], [11], GFMt and [5] by 23%, 7%, and 10%, respectively and is CDIPLA3 competitive with hMetis [8], [1], and LSR/MFFS [4] which have MLC generated better results than many recent state-of-the-art partitioning algorithms.
Citation:
Jong-Sheng Cherng, Sao-Jie Chen, Chia-Chun Tsai, Jan-Ming Ho, "An Efficient Two-Level Partitioning Algorithm for VLSI Circuits," asp-dac, pp.69, Asia and South Pacific Design Automation Conference 1999 (ASP-DAC'99), 1999
Usage of this product signifies your acceptance of the Terms of Use.