An O(mn) time algorithm for optimal buffer insertion of nets with m sinks Conference Paper uri icon


  • Buffer insertion is an effective technique to reduce interconnect delay. In this paper, we give a simple O(mn) time algorithm for optimal buffer insertion, where m is the number of sinks and n is the number of buffer positions. This is the first linear time buffer insertion algorithm for nets with constant number of sinks. When m is small, it is a significant improvement over our recent O(n log 2 n) time algorithm, and the O(n 2) time algorithm of van Ginneken. For b buffer types, the new algorithm runs in O(b 2n + bmn) time, an improvement of our recent O(bn 2) algorithm. The improvement is made possible by a clever bookkeeping method and an innovative linked list data structure that can perform addition of a wire, and addition of a buffer in amortized O(1) time. On industrial test cases, the new algorithm is faster than previous best algorithms by an order of magnitude. © 2006 IEEE.

author list (cited authors)

  • Li, Z., & Shi, W.

publication date

  • September 2006