A distinctive O(mn) time algorithm for optimal buffer insertions

With the development of technology, interconnect delay has become a key factor in VLSI. Buffer insertion is an effective technique for reducing interconnect delay. This paper presents an advanced algorithm for finding the optimal buffer insertion solution. The advanced algorithm can further improve O(mn) time algorithm for optimal buffer insertion, in which m is the number of sinks and n is the number of candidate buffer insertion positions. Assuming that the sink number m is fixed, it is a significant improvement over O(nlog²n) time algorithm, and the O(n²) time algorithm. The improvement is made possible by a new pruning rule and the predictive merging technique that can perform 2-pin and multi-pin interconnect optimal buffer insertion faster. Based on the test cases, the advanced algorithm is evidently faster than previous best algorithm.