Freeze: engineering a fast repeater insertion solver for power minimization using the ellipsoid method

ABSTRACT

This paper presents a novel repeater insertion algorithm for the power minimization of realistic interconnect trees under given timing budgets. Our algorithm judiciously combines a local optimizer based on the dynamic programming technique and a global search engine using the ellipsoid method. As a result, our approach is capable of producing high-quality solutions at a very fast speed. Furthermore, our scheme is robust and does not need any manual tuning of the iteration-control parameters.We have developed a repeater insertion tool, called F<small>REEZE</small>, using the proposed algorithm and applied it to various interconnect trees with different timing targets. Experimental results demonstrate the high effectiveness of our approach. In comparison with the state-of-the-art low-power repeater insertion schemes, F<small>REEZE</small> requires 5.8 times fewer iterations on the average, achieving up to 27 times speedup with even better power savings. When compared with a dynamic programming based scheme, which guarantees the optimal solution, our tool delivers up to 50 times speedup with 0.9% power increase on the average.

REFERENCES

• 1: C. Alpert, A. Devgan, and S. T. Quay. Buffer insertion for noise and delay optimization. IEEE Trans. Computer-Aided Design of Integrated 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: 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]
• 4: 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.
• 5: H. B. Bakoglu. Circuits, Interconnects, and Packaging for VLSI. Reading, MA: Addison-Wesley, 1990.
• 6: 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.
• 7: 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]
• 8: 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]
• 9: 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]
• 10: 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]
• 11: 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.
• 12: N. Hedenstierna and K. O. Jeppson. CMOS circuit speed and buffer optimization. IEEE Trans. CAD, 6(2):270--280, Feb. 1987.
• 13: 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]
• 14: 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.
• 15: 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]
• 16: 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]
• 17: Xun Liu , Yuantao Peng , Marios C. Papaefthymiou, RIP: An Efficient Hybrid Repeater Insertion Scheme for Low Power, Proceedings of the conference on Design, Automation and Test in Europe, p.1330-1335, March 07-11, 2005 [doi>10.1109/DATE.2005.262]
• 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: A. Nemirovsky and D. Yudin. Informational complexity and efficient methods for solution of convex extremal problems. J. Wiley & Sons, New York, 1983.
• 21: 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]
• 22: J. F. Shapiro. Mathematical Programming: Structures and Algorithms. Wiley-Interscience Publication, 1979.
• 23: 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]
• 24: D. Sylvester and K. Keutzer. A global wiring paradigm for deep submicron design. IEEE Trans. CAD, 19(2):242--252, Feb. 2000.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms

Keywords:
interconnect, low power, repeater insertion