An efficient net ordering algorithm for buffer insertion

ABSTRACT

There are efficient algorithms for net-based buffer insertion but they lead to sub-optimal path delays or unnecessarily large number of buffers due to their lack of global view. This can increase power consumption as well as die area. The ordering of nets for buffer insertion has a crucial impact on the quality of buffering in terms of path delay and the number of used buffers. A good net ordering can extend the local view of any net-based buffer insertion algorithm.In this paper, an efficient O(nlogn) algorithm for net ordering is presented. The net ordering problem is mapped to traditional knapsack problem to obtain an efficient ordering. Experimental results show that our algorithm can meet timing constraints with an 18.8% reduction in the number of buffers on average.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Jason Cong , Zhigang Pan , Lei He , Cheng-Kok Koh , Kei-Yong Khoo, Interconnect design for deep submicron ICs, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.478-485, November 09-13, 1997, San Jose, California, United States
• 4: Cong, J. and Pan, D. Z., Interconnect delay estimation models for synthesis and design planning. In Proc. Asia and South Pacific Design Automation Conf., 1999, 97--100.
• 5: ISCAS Benchmarks, http://iwls.org/iwls2005/benchmarks.
• 6: 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
• 7: Saxena, P., Menzes, N., Cocchini, P., and D. Kirkpatrick, A., Repeater scaling and its impact on CAD. In IEEE Trans. on Computer-Aided Design, 23, 4 (April 2004), 451--463.
• 8: Semiconductor Industry Association, NationalTechnoogy Roadmap for Semiconductor, 1997.
• 9: Weiping Shi , Zhuo Li, An O(nlogn) time algorithm for optimal buffer insertion, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775980]
• 10: 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, San Diego, California, USA [doi>10.1145/1065579.1065711]
• 11: 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]
• 12: Van Ginneken, L. P. P. P., Buffer Placement in distributed RC-tree networks for minimal Elmore delay. In Proc. IEEE Int. Symp. on Circuit and Systems, 1990, 865--868.
• 13: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 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, buffer usage, net ordering