@inproceedings{fc636624b3d34ceeab9529bdb076dd23,
title = "A distinctive O(mn) time algorithm for optimal buffer insertions",
abstract = "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(nlog2n) time algorithm, and the O(n2) 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.",
keywords = "Buffer insertion, delay, interconnect, time complexity",
author = "Xinsheng Wang and Wenpan Liu and Mingyan Yu",
note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 16th International Symposium on Quality Electronic Design, ISQED 2015 ; Conference date: 02-03-2015 Through 04-03-2015",
year = "2015",
month = apr,
day = "13",
doi = "10.1109/ISQED.2015.7085442",
language = "英语",
series = "Proceedings - International Symposium on Quality Electronic Design, ISQED",
publisher = "IEEE Computer Society",
pages = "293--297",
booktitle = "Proceedings of the 16th International Symposium on Quality Electronic Design, ISQED 2015",
address = "美国",
}