A fast algorithm for optimal buffer insertion

Abstract—The classic buffer insertion algorithm of van Gin-neken has time and space complexity ( 2), where is the number of possible buffer positions. For more than a decade, van Ginneken’s algorithm has been the foundation of buffer insertion. In this paper, we present a new algorithm that computes the same optimal buffer insertion, but runs much faster. For 2-pin nets, our time complexity is ( log) and space complexity is (). For multipin nets, our time complexity is ( log2) and space complexity is ( log). The speedup is achieved by four novel techniques: predictive pruning, candidate tree, fast redundancy check, and fast merging. On industrial test cases, the new algo-rithms is 2–80 times faster than van Ginneken’s algorithm and uses 1 4–1 500 of the memory. Since van Ginneken’s algorithm and its variations are used by most existing algorithms on buffer insertion and buffer sizing, our new algorithm significantly im-proves the performance of all these algorithms. The predictive pruning technique has been applied to buffer cost minimization (Shi et al., 2004), and significantly improved the running time. Index Terms—Buffer insertion, data structure, Elmore delay, interconnect, routing. I