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

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(nlog²n) time algorithm, and the O(n²) time algorithm of van Ginneken. For b buffer types, the new algorithm runs in O(b²n + bmn) time, an improvement of our recent O(bn²) 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