Fast Wire Length Estimation by Net Bundling for Block Placement

The wire length estimation is the bottleneck of packing based block placers. To cope with this problem, we present a fast wire length estimation method in this paper. The key idea is to bundle the 2-pin nets between block pairs, and measure the wire length bundle by bundle, instead of net by net. Previous bundling method (Chan et al., 2005) introduces a huge error which compromises the performance. We present an error-free bundling approach which utilizes the piecewise linear wire length function of a pair of blocks. With the function implemented into a lookup table, the wire length can be computed promptly and precisely by binary search. Furthermore, we show that 3-pin nets can also be bundled, resulting in a further speedup. The effectiveness of our method is verified by experiments