Dynamic global buffer planning optimization based on detail block locating and congestion analysis

ABSTRACT

By dividing the packing area into routing tiles, we can give the budget of the buffer insertion. And the detail locating of the blocks in their rooms can be implemented for each iterations during the annealing process to favor the later buffer planning. The buffer insertion will affect the possible routes as well the congestion of the packing. The congestion estimation in this paper takes the buffer insertion into account. So we devise a buffer planning algorithm to allocate the buffer into tiles with congestion information considered. The buffer allocation problem is formulated into a net flow problem and the buffer allocation can be handled as an integral part in the floorplanning process. Since there is more freedom for floorplan optimization, the floorplanning algorithm integrated with buffer planning can result in better performance and chip area.

REFERENCES

• 1: J. Cong. " Challenges and opportunities for design innovations in nanometer technologies". In Frontiers in Semiconductor Research: A Collection of SRC Working Papers, 1997.
• 2: Jason Cong , Tianming Kong , David Zhigang Pan, Buffer block planning for interconnect-driven floorplanning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.358-363, November 07-11, 1999, San Jose, California, United States
• 3: Probir Sarkar , Vivek Sundararaman , Cheng-Kok Koh, Routability-driven repeater block planning for interconnect-centric floorplanning, Proceedings of the 2000 international symposium on Physical design, p.186-191, May 2000, San Diego, California, United States [doi>10.1145/332357.332398]
• 4: Xiaoping Tang , D. F. Wong, Planning buffer locations by network flows, Proceedings of the 2000 international symposium on Physical design, p.180-185, May 2000, San Diego, California, United States [doi>10.1145/332357.332397]
• 5: 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]
• 6: Chiu Wing Sham , Evangeline F. Y. Young, Routability driven floorplanner with buffer block planning, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505402]
• 7: W. C. Elmore, "The transient response of damped linear networks with particular regard to wide-band amplifiers," J. Appl. Phys., vol. 19, pp.55--63, Jan. 1948.
• 8: J. Cong and D. Z. Pan, "Interconnect delay estimation models for synthesis and design planning," in Proc.ASP Design Automation Conf., Jan. 1999, pp. 97--100.
• 9: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 10: Semiconductor Industry Association, National Technology Roadmap for Semiconductors. San Jose, CA: SIA, 1997.
• 11: Xianlong Hong , Gang Huang , Yici Cai , Jiangchun Gu , Sheqin Dong , Chung Kuan Cheng , Jun Gu, Corner block list: an effective and efficient topological representation of non-slicing floorplan, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 12: Yuchun Ma , Xianlong Hong , Sheqin Dong , Song Chen , Yici Cai , C. K. Cheng , Jun Gu, An integrated floorplanning with an efficient buffer planning algorithm, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640031]
• 13: Song Chen , Xianlong Hong , Sheqin Dong , Yuchun Mal , Yici Cai , Chung-Kuan Cheng , Jun Gu, A buffer planning algorithm based on dead space redistribution, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119859]

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, congestion, floorplanning, routability