Fast algorithms for slew constrained minimum cost buffering

ABSTRACT

As a prevalent constraint, sharp slew rate is often required in circuit design which causes a huge demand for buffering resources. This problem requires ultra-fast buffering techniques to handle large volume of nets, while also minimizing buffering cost. This problem is intensively studied in this paper. First, a highly efficient algorithm based on dynamic programming is proposed to optimally solve slew buffering with discrete buffer locations. Second, a new algorithm is developed to handle the difficult cases in which no assumption is made on buffer input slew. Third, an adaptive buffer selection approach is proposed to efficiently handle slew buffering with continuous buffer locations. Experiments on industrial netlists demonstrate that our algorithms are very effective and highly efficient: we achieve > 100X speed up and save up to 40% buffer area over the commonly-used van Ginneken style buffering.

REFERENCES

• 1: P. Saxena and N. Menezes and P. Cocchini and D. A. Kirkpatrick, "Repeater scaling and its impact on CAD," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 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: J. Lillis and C.-K. Cheng and T.-T.Y. Lin, "Optimal wire sizing and buffer insertion for low power and a generalized delay model," IEEE Journal of Solid State Circuits, vol. 31, no. 3, pp. 437--447, 1996.
• 4: 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
• 5: 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]
• 6: 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]
• 7: Charles Alpert , Andrew B. Kahng , Bao Liu , Ion Măndoiu , Alexander Zelikovsky, Minimum-buffered routing of non-critical nets for slew rate and reliability control, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 8: Charles J. Alpert , Jiang Hu , Sachin S. Sapatnekar , Paul Villarrubia, A practical methodology for early buffer and wire resource allocation, Proceedings of the 38th conference on Design automation, p.189-194, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378461]
• 9: Chandramouli V. Kashyap , Charles J. Alpert , Frank Liu , Anirudh Devgan, Closed form expressions for extending step delay and slew metrics to ramp inputs, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640009]
• 10: H. B. Bakoglu, Circuits, Interconnects, and Packaging for Addison-Wesley Publishing Company, 1990.
• 11: N. H. Weste and K. Eshraghian, Principles of CMOS VLSI Design. Addison Wesley, 1993, pp. 221--223.
• 12: L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree networks for minimal Elmore delay," in Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 865--868, 1990.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Performance

Keywords:
buffer insertion, physical design, slew constraint