Wire length prediction based clustering and its application in placement

TitleWire length prediction based clustering and its application in placement
Publication TypeConference Paper
Year of Publication2003
AuthorsHu, B, Marek-Sadowska, M
Conference NameDesign Automation Conference, 2003. Proceedings
Date Publishedjune
Keywordscircuit layout CAD, deterministic algorithms, edge separability, element proximity, fast placer implementation, fine-granularity clustering algorithm, FPI framework, global placement, integrated circuit interconnections, integrated circuit layout, multipin net, net absorption algorithm, placement quality loss, wire length prediction based clustering
AbstractIn this paper, we introduce a metric to evaluate proximity of connected elements in a netlist. Compared to connectivity by S. Hauck and G. Borriello (1997) and edge separability by J. Cong and S.K. Lim (2000), our metric is capable of predicting short connections more accurately. We show that the proposed metric can also predict relative wire length in multipin nets. We develop a fine-granularity clustering algorithm based on the new metric and embed it into the Fast Placer Implementation (FPI) framework by B. Hu and M. Marek-Sadowska (2003). Experimental results show that the new clustering algorithm produces better global placement results than the net absorption of Hu and M. Marek-Sadowska (2003) algorithm, connectivity of S. Hauck and G. Borriello (1997), and edge separability of J. Cong and S.K. Lim (2000) based algorithms. With the new clustering algorithm, FPI achieves up to 50% speedup compared to the latest version of Capo8.5 in http://vlsicad.ucsd.edu/Resources/SoftwareLinks/PDtools/, without placement quality losses.
DOI10.1109/DAC.2003.1219128