A buffer planning algorithm based on dead space redistribution

ABSTRACT

This paper studies the buffer planning problem for interconnect-centric floorplanning for nanometer technologies. The dead-spaces are the spaces within a placement that are not held by any circuit block. In this paper, we proposed a buffer planning algorithm based on dead space redistribution to make good use of dead-spaces for buffer insertion. Associated with circuit blocks under topological representations, the dead space can be redistributed by freely moving some circuit blocks within their rooms in the placement. The total area and the topology of the placement keep unchanged while doing the dead space redistribution. The number of nets satisfying the delay constraint can be increased by redistributing the dead space all over the placement, which has been demonstrated by the experimental results. The increment of the number of nets that satisfy delay constraints is 9% on an average.

REFERENCES

• 1: 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
• 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: J. Cong, "Challenges and opportunities for design innovations in nanometer technologies," Frontiers in Semiconductor Research: A collection of SRC Working Papers, Semiconductor Research Corporation, http://www.src.org/prg_mgmt/frontier.dgw, 1997
• 4: 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]
• 5: 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]
• 6: 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]
• 7: Collaborative Benchmarking Laboratory, North Carolina State University, http://www.cbl.ncsu.edu/CBL Docs/lys92.html: LayoutSynth'92 Benchmark Information.
• 8: 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]
• 9: Feodor F. Dragan , Andrew B. Kahng , Ion Măndoiu , Sudhakar Muddu , Alexander Zelikovsky, Provably good global buffering using an available buffer block plan, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 10: Feodor F. Dragan , Andrew B. Kahng , Ion Mandoiu , Sudhakar Muddu , Alexander Zelikovsky, Provably good global buffering by multi-terminal multicommodity flow approximation, Proceedings of the 2001 conference on Asia South Pacific design automation, p.120-125, January 2001, Yokohama, Japan [doi>10.1145/370155.370299]
• 11: 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]
• 12: Shuo Zhou , Sheqin Dong , Chung-Kuan Cheng , Jun Gu, ECBL: an extended corner block list with solution space including optimum placement, Proceedings of the 2001 international symposium on Physical design, p.150-155, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369756]
• 13: 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]
• 14: Faran Rafiq , Malgorzata Chrzanowska-Jeske , Hannah Honghua Yang , Naveed Sherwani, Integrated floorplanning with buffer/channel insertion for bus-based microprocessor designs, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505403]
• 15: Semiconductor Industry Association, National Technology Roadmap for Semiconductors, 1997.