| A fully polynomial time approximation scheme for timing driven minimum cost buffer insertion |
| Full text |
Pdf
(188 KB)
|
| Source
|
Annual ACM IEEE Design Automation Conference
archive
Proceedings of the 46th Annual Design Automation Conference
table of contents
San Francisco, California
SESSION: Advances in physical synthesis
table of contents
Pages: 424-429
Year of Publication: 2009
ISBN:978-1-60558-497-3
|
|
Authors
|
|
Shiyan Hu
|
Michigan Technological University, Houghton, Michigan
|
|
Zhuo Li
|
IBM Austin Research Laboratory, Austin, Texas
|
|
Charles J. Alpert
|
IBM Austin Research Laboratory, Austin, Texas
|
|
| Sponsors |
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 10, Downloads (12 Months): 20, Citation Count: 0
|
|
|
ABSTRACT
As VLSI technology enters the nanoscale regime, interconnect delay has become the bottleneck of the circuit timing. As one of the most powerful techniques for interconnect optimization, buffer insertion is indispensable in the physical synthesis flow. Buffering is known to be NP-complete and existing works either explore dynamic programming to compute optimal solution in the worst-case exponential time or design efficient heuristics without performance guarantee. Even if buffer insertion is one of the most studied problems in physical design, whether there is an efficient algorithm with provably good performance still remains unknown. This work settles this open problem. In the paper, the first fully polynomial time approximation scheme for the timing driven minimum cost buffer insertion problem is designed. The new algorithm can approximate the optimal buffering solution within a factor of 1 + ε running in O(m2n2b/ε3 + n3b2/ε) time for any 0 < ε < 1, where n is the number of candidate buffer locations, m is the number of sinks in the tree, and b is the number of buffers in the buffer library. In addition to its theoretical guarantee, our experiments on 1000 industrial nets demonstrate that compared to the commonly-used dynamic programming algorithm, the new algorithm well approximates the optimal solution, with only 0.57% additional buffers and 4.6x speedup. This clearly demonstrates the practical value of the new algorithm.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
P. Saxena and N. Menezes and P. Cocchini and D. A. Kirkpatrick, "Repeater scaling and its impact on CAD," TCAD, vol. 23, no. 4, pp. 451--463, 2004.
|
| |
2
|
J. Cong, "An interconnect-centric design flow for nanometer technologies," Proceedings of the IEEE, vol. 89, no. 4, pp. 505--528, 2001.
|
 |
3
|
Zhuo Li , Charles J. Alpert , Shiyan Hu , Tuhin Muhmud , Stephen T. Quay , Paul G. Villarrubia, Fast interconnect synthesis with layer assignment, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
[doi> 10.1145/1353629.1353648]
|
 |
4
|
|
| |
5
|
L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree networks for minimal Elmore delay," in Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 865--868, 1990.
|
| |
6
|
J. Lillis and C.-K. Cheng and T.-T.Y. Lin, "Optimal wire sizing and buffer insertion for low power and a generalized delay model," IEEE Journal of Solid State Circuits, vol. 31, no. 3, pp. 437--447, 1996.
|
| |
7
|
W. Shi and Z. Li, "A fast algorithm for optimal buffer insertion," TCAD, vol. 24, no. 6, pp. 879--891, 2005.
|
| |
8
|
|
| |
9
|
|
 |
10
|
Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion for noise and delay optimization, Proceedings of the 35th annual Design Automation Conference, p.362-367, June 15-19, 1998, San Francisco, California, United States
[doi> 10.1145/277044.277145]
|
 |
11
|
Shiyan Hu , Charles J. Alpert , Jiang Hu , Shrirang Karandikar , Zhuo Li , Weiping Shi , C. N. Sze, Fast algorithms for slew constrained minimum cost buffering, Proceedings of the 43rd annual Design Automation Conference, July 24-28, 2006, San Francisco, CA, USA
[doi> 10.1145/1146909.1146990]
|
 |
12
|
|
 |
13
|
Hai Zhou , D. F. Wong , I-Min Liu , Adnan Aziz, Simultaneous routing and buffer insertion with restrictions on buffer locations, Proceedings of the 36th annual ACM/IEEE Design Automation Conference, p.96-99, June 21-25, 1999, New Orleans, Louisiana, United States
[doi> 10.1145/309847.309885]
|
 |
14
|
|
| |
15
|
Jason Cong , Tianming Kong , David Zhigang Pan, Buffer block planning for interconnect-driven floorplanning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.358-363, November 07-11, 1999, San Jose, California, United States
|
 |
16
|
Charles J. Alpert , Jiang Hu , Sachin S. Sapatnekar , Paul Villarrubia, A practical methodology for early buffer and wire resource allocation, Proceedings of the 38th annual Design Automation Conference, p.189-194, June 2001, Las Vegas, Nevada, United States
[doi> 10.1145/378239.378461]
|
| |
17
|
|
 |
18
|
|
|