Circuit-wise buffer insertion and gate sizing algorithm with scalability

ABSTRACT

Most existing buffer insertion algorithms, such as van Ginneken's algorithm, consider individual nets and therefore often result in high buffer cost due to lack a global view. Thus, circuit-wise buffering is necessary to reduce buffer cost. Recently, some circuit-wise buffering algorithms are proposed. However, these algorithms are based on heuristics which are not scalable in handling large circuits.

In this paper, we present a scalable circuit-wise algorithm with three novel features. (1) A linear modeling of nonlinear delay versus cost tradeoff. Due to the similar nature of buffer insertion and gate sizing, gate sizing is handled in such a manner. (2) A dynamic critical sink selection procedure to solve multiple-sink net. Multiple-sink nets have been problems for previous circuit-wise buffering algorithms. (3) A circuit partition technique to divide the circuit into sub-circuits and apply divide-and-conquer scheme. This technique provides high scalability for the algorithm.

Experiments on ISCAS85 circuits show that the new algorithm achieves 17X speedup compared with Sze's path based algorithm. In the meantime, it saves 16.0% buffer cost and 4.9% gate cost without increasing circuit delay. Furthermore, the running time of a testcase in ITC99 with approximate one hundred thousand gates is less than 11 minutes, which demonstrates the scalability of the new algorithm.

REFERENCES

• 1: P. Saxena and N. Menezes and P. Cocchini and D. A. Kirkpatrick, "Repeater scaling and its impact on CAD," TCAD, 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: L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree networks for minimal Elmore delay," ISCAS, pp. 865--868, 1990.
• 4: J. Lillis, C.-K. Cheng and T.-T.Y. Lin, "Optimal wire sizing and buffer insertion for low power and a generalized delay model," Journal of Solid State Circuits, vol. 31, no. 3, pp. 437--447, 1996.
• 5: An Efficient Buffer Insertion Algorithm for Large Networks Based on Lagrangian Relaxation, Proceedings of the 1999 IEEE International Conference on Computer Design, p.210, October 10-13, 1999
• 6: C. N. Sze , Charles J. Alpert , Jiang Hu , Weiping Shi, Path based buffer insertion, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065711]
• 7: Ruiming Chen , Hai Zhou, Efficient algorithms for buffer insertion in general circuits based on network flow, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.322-326, November 06-10, 2005, San Jose, CA
• 8: Mandar Waghmode , Zhuo Li , Weiping Shi, Buffer insertion in large circuits with constructive solution search techniques, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146988]
• 9: J. P. Fishburn and A. E. Dunlop, "TILOS: A posynomial programming approach to transistor sizing," ICCAD, pp. 326--328, 1985.
• 10: S. S. Sapatnekar, V. B. Rae, P. M. Vaidya, and S. M. Kang, "An exact solution to the transistor sizing problem for CMOS circuits using convex optimizaiton," TCAD, pp. 1621--1634, 1993.
• 11: Chung-Ping Chen , Chris C. N. Chu , D. F. Wong, Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.617-624, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289097]
• 12: C. J. Alpert , Jiang Hu , S. S. Sapatnekar , C. N. Sze, Accurate estimation of global buffer delay within a floorplan, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.706-711, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382667]
• 13: Charles Alpert , Chris Chu , Gopal Gandham , Miloš Hrkić , Jiang Hu , Chandramouli Kashyap , Stephen Quay, Simultaneous driver sizing and buffer insertion using a delay penalty estimation technique, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505414]
• 14: X. Lu and W. Shi, "Layout and parasitic information for iscas circuits," http://dropzone.tamu.edu/.xiang/iscas.html, 2003.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Performance

Keywords:
buffer insertion, gate sizing, interconnect synthesis