Low-power repeater insertion with both delay and slew rate constraints

ABSTRACT

In this paper, a novel repeater insertion algorithm is presented to minimize the power dissipation of interconnect trees under given timing budgets and slew rate constraints. In contrast to traditional bottom-up dynamic programming approaches, the proposed algorithm combines a Lagrangian relaxation framework and a graph-based search method to derive possible solutions in a top-down fashion. As a result, it is capable of analyzing repeater slew rates efficiently. In addition, our scheme incorporates accurate circuit models and is therefore able to capture the precise delay and slew rate information, leading to high-quality interconnect designs.We have applied our scheme to interconnects of different topologies and various timing and slew rate constraints. Experimental results demonstrate the effectiveness of our approach in comparison with previous low-power repeater insertion schemes. Under tight timing constraints, our scheme can always derive repeater insertion solutions that meet both delay and slew rate requirements, whereas other schemes often fail. Under loose timing constraints, our algorithm achieves up to a 23% average power dissipation reduction for different interconnects specifications with shorter runtimes.

REFERENCES

• 1: C. Alpert, A. Devgan, and S. T. Quay. Buffer insertion for noise and delay optimization. IEEE Trans. CAD, 18(11):1633--1645, Nov. 1999.
• 2: 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]
• 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: 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]
• 6: 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]
• 7: 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]
• 8: Y. Gao , D. Wong, A graph based algorithm for optimal buffer insertion under accurate delay models, Proceedings of the conference on Design, automation and test in Europe, p.535-539, March 2001, Munich, Germany
• 9: 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]
• 10: L. Ginneken. Buffer placement in distributed RC-tree networks for minimal Elmore delay. In ISCAS, 1990.
• 11: N. Hedenstierna and K. O. Jeppson. CMOS circuit speed and buffer optimization. IEEE Trans. CAD, 6(2):270--280, Feb. 1987.
• 12: 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]
• 13: J. Lillis, C. K. Cheng, and T.-T. Y. Lin. Optimal wire sizing and buffer insertion for low power and a generalized delay model. JSSC, 31(3):437--447, Mar. 1996.
• 14: I-Min Liu , Adnan Aziz , D. F. Wong, Meeting delay constraints in DSM by minimal repeater insertion, Proceedings of the conference on Design, automation and test in Europe, p.436-440, March 27-30, 2000, Paris, France [doi>10.1145/343647.343814]
• 15: Noel Menezes , Chung-Ping Chen, Spec-Based Repeater Insertion and Wire Sizing for On-chip Interconnect, Proceedings of the 12th International Conference on VLSI Design - 'VLSI for the Information Appliance', p.476, January 10-13, 1999
• 16: A. Nalamalpu and W. P. Burleson. A practical approach to DSM repeater insertion: Satisfying delay constraints while minimizing area and power. In IEEE Inter. ASIC/SOC Conference, Sept. 2001.
• 17: M. Nekili and Y. Savaria. Optimal methods of driving interconnections in VLSI circuits. In ISCAS, May 1993.
• 18: 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]
• 19: Yuantao Peng , Xun Liu, Freeze: engineering a fast repeater insertion solver for power minimization using the ellipsoid method, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065794]
• 20: P. Saxena, N. Menezes, P. Cocchini, and D. A. Kirkpatrick. Repeater scaling and its impact on CAD. IEEE Trans. CAD, 23(4):451--463, Apr. 2004.
• 21: J. F. Shapiro. Mathematical Programming: Structures and Algorithms. Wiley-Interscience Publication, 1979.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
interconnect, low power, repeater insertion, slew rate