$O(mn)$ Time Algorithm for Optimal Buffer Insertion of Nets With $m$ Sinks
作者： Zhuo Li , Ying Zhou , Weiping Shi
DOI: 10.1109/TCAD.2011.2174639
关键词: Algorithm design 、 Elmore delay 、 Buffer (optical fiber) 、 Algorithm 、 Data structure 、 Computer science 、 Linked list 、 Freivalds' algorithm
摘要: 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 the number of sinks and n positions. When small, our significant improvement over recent O(nlog2n) by Shi Li, O(n2) van Ginneken. For b types, algorithms runs in O(b2n+bmn) time, O(bn2) Li Shi. The made possible innovative linked list that can perform addition wire, amortized O(1) smart design pointers. We then present extension cost minimization problem, which improves previous best algorithm. On industrial test cases, new faster than order magnitude.
sci-hub.se 参考文章(17)
Ruiming Chen, Hai Zhou, A flexible data structure for efficient buffer insertion international conference on computer design. pp. 216- 221 ,(2004) , 10.1109/ICCD.2004.1347925
Weiping Shi, Zhuo Li, Charles J Alpert, None, Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost asia and south pacific design automation conference. pp. 609- 614 ,(2004) , 10.5555/1015090.1015257
Natarajan Viswanathan, Gi-Joon Nam, Jarrod A Roy, Zhuo Li, Charles J Alpert, Shyam Ramji, Chris Chu, None, ITOP: integrating timing optimization within placement international symposium on physical design. pp. 83- 90 ,(2010) , 10.1145/1735023.1735048
Zhuo (Robert) Li, Weiping Shi, An O(mn) time algorithm for optimal buffer insertion of nets with m sinks Proceedings of the 2006 conference on Asia South Pacific design automation - ASP-DAC '06. pp. 320- 325 ,(2006) , 10.1145/1118299.1118379
Zhuo Li, David A Papa, Charles J Alpert, Shiyan Hu, Weiping Shi, Cliff Sze, Ying Zhou, None, Ultra-fast interconnect driven cell cloning for minimizing critical path delay international symposium on physical design. pp. 75- 82 ,(2010) , 10.1145/1735023.1735047
Charles J Alpert, Shrirang K Karandikar, Zhuo Li, Gi-Joon Nam, Stephen T Quay, Haoxing Ren, Cliff N Sze, Paul G Villarrubia, Mehmet C Yildiz, None, Techniques for Fast Physical Synthesis Proceedings of the IEEE. ,vol. 95, pp. 573- 599 ,(2007) , 10.1109/JPROC.2006.890096
P. Saxena, N. Menezes, P. Cocchini, D.A. Kirkpatrick, Repeater scaling and its impact on CAD IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 23, pp. 451- 463 ,(2004) , 10.1109/TCAD.2004.825841
Chuck Alpert, Shiyan Hu, Zhuo Li, Tuhin Mahmud, Stephen Quay, Paul Villarrubia, Fast interconnect synthesis with layer assignment international symposium on physical design. pp. 71- 77 ,(2008) , 10.1145/1353629.1353648
Ying Zhou, Charles J Alpert, Zhuo Li, Cliff Sze, Louise H Trevillyan, None, Shedding physical synthesis area bloat Vlsi Design. ,vol. 2011, pp. 2- ,(2011) , 10.1155/2011/503025
Shiyan Hu, Zhuo Li, Charles J Alpert, None, A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion Proceedings of the 46th Annual Design Automation Conference on ZZZ - DAC '09. pp. 424- 429 ,(2009) , 10.1145/1629911.1630026