Making fast buffer insertion even faster via approximation techniques

ABSTRACT

As technology scales to 0.13 micron and below, designs are requiring buffers to be inserted on interconnects of even moderate length for both critical paths and fixing electrical violations. Consequently, buffer insertion is needed on tens of thousands of nets during physical synthesis optimization. Even the fast implementation of van Ginneken's algorithm requires several hours to perform this task. This work seeks to speed up the van Ginneken style algorithms by an order of magnitude while achieving similar results. To this end, we present three approximation techniques in order to speed up the algorithm: (1) aggressive pre-buffer slack pruning, (2) squeeze pruning, and (3) library lookup. Experimental results from industrial designs show that using these techniques together yields solutions in 9 to 25 times faster than van Ginneken style algorithms, while only sacrificing less than 3% delay penalty.

REFERENCES

• 1: P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick, "Repeater scaling and its impact on cad," IEEE Trans. CAD, vol. 23, no. 4, pp. 451--463, 2004.
• 2: Peter J. Osler, Placement driven synthesis case studies on two sets of two chips: hierarchical and flat, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981107]
• 3: L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree network for minimal elmore delay," in ISCAS, 1990, pp. 865--868.
• 4: W. Shi and Z. Li, "A Fast Algorithm for Fast Buffer Insertion," IEEE Trans. CAD, to appear.
• 5: Weiping Shi , Zhuo Li, An O(nlogn) time algorithm for optimal buffer insertion, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775980]
• 6: J. Lillis, C. K. Cheng, and T.-T. Y. Lin, "Optimal wire sizing and buffer insertion for low power and a generalized delay model," IEEE Trans. Solid-State Circuits, vol. 31, no. 3, pp. 437--447, 1996.
• 7: Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion with accurate gate and interconnect delay computation, Proceedings of the 36th ACM/IEEE conference on Design automation, p.479-484, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309983]
• 8: Chung-Ping Chen , Noel Menezes, Noise-aware repeater insertion and wire-sizing for on-chip interconnect using hierarchical moment-matching, Proceedings of the 36th ACM/IEEE conference on Design automation, p.502-506, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309987]
• 9: Takumi Okamoto , Jason Cong, Buffered Steiner tree construction with wire sizing for interconnect layout optimization, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.44-49, November 10-14, 1996, San Jose, California, United States
• 10: Miloš Hrkić , John Lillis, S-Tree: a technique for buffered routing tree synthesis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514066]
• 11: Miloš Hrkić , John Lillis, Buffer tree synthesis with consideration of temporal locality, sink polarity requirements, solution cost and blockages, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505413]
• 12: J. Hu, C. J. Alpert, S. T. Quay and G. Gandham, "Buffer insertion with adaptive blokage avoidance," IEEE Trans. CAD, vol. 22, no. 4, pp. 492--498, 2003.
• 13: Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion for noise and delay optimization, Proceedings of the 35th annual conference on Design automation, p.362-367, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277145]
• 14: Weiping Shi , Zhuo Li , Charles J. Alpert, Complexity analysis and speedup techniques for optimal buffer insertion with minimum cost, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.609-614, January 27-30, 2004, Yokohama, Japan
• 15: Buffer Library Selection, Proceedings of the 2000 IEEE International Conference on Computer Design: VLSI in Computers & Processors, p.221, September 17-20, 2000