A sensitivity analysis of low-power repeater insertion

ABSTRACT

In this paper, we perform the first quantitative study on the sensitivities of repeater power to available repeater width and candidate location, two key parameters of the dynamic programming (DP) based repeater insertion algorithms. Based on our analysis, we propose a simple yet effective scheme to select repeater widths and locations for DP-based algorithms, achieving an excellent trade-off between the solution quality and runtime. Experimental results have shown that, when combined with our sensitivity-guided scheme, the DP algorithm can attain more than 6 times speedup with negligible power degradation.

REFERENCES

• 1: C. Alpert, A. Devgan, and S. T. Quay. Buffer insertion for noise and delay optimization. IEEE Trans. Computer-Aided Design of Intergrated Circuits and Systems, 18(11):1633--1645, Nov. 1999.
• 2: Charles Alpert , Anirudh Devgan, Wire segmenting for improved buffer insertion, Proceedings of the 34th annual conference on Design automation, p.588-593, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266291]
• 3: C. J. Alpert, J. Hu, S. S. Sapatnekar, and P. G. Villarrubia. A practical methodology for early buffer and wire resource allocation. IEEE Trans. CAD, 22(5), May 2003.
• 4: H. B. Bakoglu. Circuits, Interconnects, and Packaging for VLSI. Reading, MA: Addison-Wesley, 1990.
• 5: K. Banerjee and A. Mehrotra. A power-optimal repeater insertion methodology for global interconnects in nanometer designs. IEEE Trans. VLSI Systems, 49(11):2001--2007, Nov. 2002.
• 6: 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]
• 7: Chris C. N. Chu , D. F. Wong, Closed form solution to simultaneous buffer insertion/sizing and wire sizing, Proceedings of the 1997 international symposium on Physical design, p.192-197, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267712]
• 8: Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
• 9: 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
• 10: W. C. Elmore. The transient response of damped linear network with particular regard to wideband amplifiers. J. Appl. Phys., 19(1):55--63, Jan. 1948.
• 11: Giuseppe S. Garcea , Nick P. van der Meijs , Ralph H. J. M. Otten, Simultaneous Analytic Area and Power Optimization for Repeater Insertion, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.568, November 09-13, 2003 [doi>10.1109/ICCAD.2003.124]
• 12: L. Ginneken. Buffer placement in distributed RC-tree networks for minimal Elmore delay. In Proc. Intl. Symposium on Circuits and Systems, 1990.
• 13: N. Hedenstierna and K. O. Jeppson. CMOS circuit speed and buffer optimization. IEEE Trans. CAD, 6(2):270--280, Feb. 1987.
• 14: Pawan Kapur , Gaurav Chandra , Krishna C. Saraswat, Power estimation in global interconnects and its reduction using a novel repeater optimization methodology, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514035]
• 15: Ruiming Li , Dian Zhou , Jin Liu , Xuan Zeng, Power-Optimal Simultaneous Buffer Insertion/Sizing and Wire Sizing, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.581, November 09-13, 2003 [doi>10.1109/ICCAD.2003.116]
• 16: J. Lillis, C. K. Cheng, and T.-T. Y. Lin. Optimal wire sizing and buffer insertion for low power and a generalized delay model. J. of Solid-State Circuits, 31(3):437--447, Mar. 1996.
• 17: Xun Liu , Yuantao Peng , Marios C. Papaefthymiou, Practical repeater insertion for low power: what repeater library do we need?, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996576]
• 18: A. Nalamalpu and W. P. Burleson. A practical approach to DSM repeater insertion: Satisfying delay constraints while minimizing area and power. In IEEE International ASIC/SOC Conference, Sept. 2001.
• 19: M. Nekili and Y. Savaria. Optimal methods of driving interconnections in VLSI circuits. In International Symposium on Circuits and Systems, May 1993.
• 20: Ralph H. J. M. Otten, Global wires: harmful?, Proceedings of the 1998 international symposium on Physical design, p.104-109, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274550]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Design

Keywords:
low power, repeater insertion, sensitivity