Routing tree construction under fixed buffer locations

ABSTRACT

Modern high performance design requires using a large number of buffers. In practice, buffers are organized into buffer blocks and planned in the early stages of design process [1]. Thus, the locations of buffer blocks are usually fixed prior to routing tree construction. In this paper we present the first algorithm for simultaneous routing tree construction and buffer insertion for multiple-pin nets under fixed buffer locations. Given a source and n sinks of a net, the required arrival time associated with each sink, and m buffers with fixed locations, our algorithm can construct a routing tree for this net with possible insertion of buffers at given locations such that the required arrival time at the source is maximized. Experimental results show that our algorithm is efficient to handle fixed buffer location constraints and can also be used for routing tree construction without buffer insertion. Moreover, it can handle obstacles and congestion which will benefit its adaption in a global router. Compared to the well-known BA-tree algorithm [2] followed by a post-processing step for handling fixed buffer location constraints, our algorithm outperforms it by up to 46% in terms of delay while using comparative wirelength.

REFERENCES

• 1: 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
• 2: T. Okamoto and J. Cong, "Interconnect layout optimization by simultaneous Steiner tree construction and buffer insertion," in Proc. A CM/SIGDA Physical Design Workshop, pp. 1-6, 1996.
• 3: J. Cong, "Challenges and opportunities for design innovations in nanometer technologies," in SRC Design Science Concept Papers, 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: J. Cong and D. Z. Pan, "Interconnect delay estimation models for synthesis and design planning," in Proc. Asia and South Pacific Design Automation Conf., pp. 97-100, 1999.
• 6: L. P. P. P. van Ginneken, "Buffer placement in distributed RC-tree networks for minimal Elmore delay," in Proc. IEEE Int. Syrup. on Circuits and Systems, pp. 865-868, 1990.
• 7: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Simultaneous Routing and Buffer Insertion for High Performance Interconnect, Proceedings of the 6th Great Lakes Symposium on VLSI, p.148, March 22-23, 1996
• 8: Jason Cong , Kwok-Shing Leung , Dian Zhou, Performance-driven interconnect design based on distributed RC delay model, Proceedings of the 30th international conference on Design automation, p.606-611, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165065]
• 9: J. Cong, A. Kahng, and K. Leung, "Efficient algorithm for the minimum shortest path steiner arborescence problem with application to VLSI physical design," IEEE Trans. on Computer-Aided Design, vol. 17, pp. 24-38, 1998.
• 10: Hai Zhou , D. F. Wong , I-Min Liu , Adnan Aziz, Simultaneous routing and buffer insertion with restrictions on buffer locations, Proceedings of the 36th ACM/IEEE conference on Design automation, p.96-99, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309885]

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing
  B.8 Performance and Reliability

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Buffering

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory