An O(bn2) time algorithm for optimal buffer insertion with b buffer types

Buffer insertion is a popular technique to reduce interconnect delay. The classic buffer insertion algorithm of L.P.P.P. van Ginneken (see ISCAS, p.865-8, 1990) has time complexity O(n²), where n is the number of buffer positions. J. Lillis et al. (see IEEE Trans. Solid-Slate Circuits, vol.31, no.3, p.437-47, 1996) extended van Ginneken´s algorithm to allow b buffer types in time O(b²n²). For modern design libraries that contain hundreds of buffers, it is a serious challenge to balance the speed and performance of the buffer insertion algorithm. We present a new algorithm that computes the optimal buffer insertion in O(bn²) time. The reduction is achieved by the observation that the (Q, C) pairs of the candidates that generate the new candidates must form a convex hull. On industrial test cases, the new algorithm is faster than the previous best buffer insertion algorithms by orders of magnitude.