Practical repeater insertion for low power: what repeater library do we need?

ABSTRACT

In this paper, we investigate the problem of repeater insertion for low power under a given timing budget. We propose a novel repeater insertion algorithm to compute the optimal repeater number and width in the discrete solution space, as defined by a given repeater library. Using our algorithm, we show that rounding the solution under the continuity assumption to the closest discrete solution candidate may result in suboptimal designs, or it may even fail to find an existing solution. Given a certain tolerance to the degradation of repeater power dissipation, we address two practical and highly important questions: (1) How coarse could the repeater size granularity be? (2) What range should the repeater size be in?Experimental results demonstrate the high effectiveness of the proposed scheme and provide valuable insights into repeater library design. Our approach achieves up to 23 power reduction in comparison to rounding-based approaches. With a 4 power degradation tolerance, repeater size granularity as coarse as 8 can be used, reducing the library size by more than 87. For interconnects with various wire lengths and timing targets, our investigation reveals that the range of optimal repeater sizes for low-power is limited, indicating that a low-cost small-size repeater library, if well designed, is adequate to provide high quality repeater insertion solutions.

REFERENCES

• 1: V. Adler and E. G. Friedman. Repeater design to reduce delay and power in resistive interconnect. IEEE Trans. Circuits and Systems--II: Analog and Digital Signal Processing, 45(5):607--616, May 1998.
• 2: H. B. Bakoglu. Circuits, Interconnects, and Packaging for VLSI. Reading, MA: Addison-Wesley, 1990.
• 3: 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.
• 4: 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]
• 5: 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]
• 6: 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
• 7: 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]
• 8: Maggie Kang , Wayne W.-M. Dai , Tom Dillinger , David LaPotin, Delay bounded buffered tree construction for timing driven floorplanning, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.707-712, November 09-13, 1997, San Jose, California, United States
• 9: 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]
• 10: 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]
• 11: Weiping Liao , Lei He, Full-Chip Interconnect Power Estimation and Simulation Considering Concurrent Repeater and Flip-Flop Insertion, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.574, November 09-13, 2003 [doi>10.1109/ICCAD.2003.75]
• 12: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Optimal wire sizing and buffer insertion for low power and a generalized delay model, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.138-143, November 05-09, 1995, San Jose, California, United States
• 13: H. Zhou, D. F. Wong, I. M. Liu and A. Aziz. Simultaneous routing and buffer insertion with restrictions on buffer locations. IEEE Trans. Computer Aided Design of Intergrated Circuits and System, 19(7):819--824, 2000.
• 14: A. Nalamalpu and W. P. Burleson. Repeater insertion in deep sub-micron CMOS: Ramp-based analytical model and placement sensitivity analysis. In International Symposium on Circuits and Systems, May 2000.
• 15: 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.
• 16: 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]
• 17: Dennis Sylvester , Kurt Keutzer, Getting to the bottom of deep submicron, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.203-211, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288614]
• 18: D. Sylvester and K. Keutzer. A global wiring paradigm for deep submicron design. IEEE Trans. CAD, 19(2):242--252, Feb. 2000.
• 19: L. P. P. P. van Ginneken. Buffer placement in distributed rc-tree networks for minimal elmore delay. In Proc. Intl. Symposium on Circuits and Systems, 1990.
• 20: C. Y. Wu and M. Shiau. Delay models and speed improvement techniques for RC tree interconnections among small geometry CMOS VLSI. Journal of Solid-State Circuits, 25(10):1247--1256, Oct. 1990.

INDEX TERMS

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

General Terms:
Design

Keywords:
interconnect, low power, repeater insertion