Maze routing with buffer insertion and wiresizing

ABSTRACT

We propose an elegant formulation of the Maze Routing with Buffer Insertion and Wiresizing pr oblem as a graph-the oretic shortest path problem. This formulation provides time and space performance improvements over previously proposed dynamic-programming based techniques. R outing c onstr aints such as wiring obstacles and restrictions on buffer locations and types are easily inc orporated in the formulation. Furthermore, efficient softwar e routines solving shortest path problems in existing graph applic ation libraries can be applied. We construct a BP-Graph such that the length of every path in this graph is e qual to the Elmore delay. Therefore, finding the minimum Elmore delay path becomes a finite shortest path problem. The buffer choices and insertion locations are repr esente d as the vertices in the BP-Graph. The inter connect wir es are sized by constructing a look-up table for buffer-to-buffer wir esizing solutions. We also provide a technique that is able to tremendously improve the runtime. Experiments show improvements over previously proposed methods.

REFERENCES

• 1: H. B. Bakoglu, Circuits, Interconnections and Packaging for VLSI, Addison-Wesley, Reading, Mass., 1990.
• 2: C. Chu and D. F. Wong, " A New Approach to Simultaneous Buffer Insertion and Wire Sizing," IEEE Trans. on CAD, 1997.
• 3: W. C. Elmore, "The Transient Response of Damped Linear Network with Particular Regard to Wideband Amplifiers," J. Applied Physics, 1948, pp. 55-63.
• 4: L. P. P. P. van Ginneken, "Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay," Proc. Int'l Symp. on Circuits and Systems, 1990, pp. 865-868.
• 5: Rohini Gupta , Byron Krauter , Bogdan Tutuianu , John Willis , Lawrence T. Pileggi, The Elmore delay as bound for RC trees with generalized input signals, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.364-369, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217556]
• 6: J. Lillis, C.-K. Cheng, and T.-T. Y. Lin, "Optimal and Efficient Buffer Insertion and Wire Sizing," IEEE Custom Integrated Circuits Conf., 1995, pp. 259-262.
• 7: 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
• 8: The National Technology Roadmap for Semiconductors, Semiconductor Industry Association, 1997.
• 9: 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.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
      B.7.2 Design Aids
          Subjects: Placement and routing
  B.8 Performance and Reliability

  C. Computer Systems Organization

  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: Path and circuit problems

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