Wire length prediction based clustering and its application in placement

In 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.