An adaptive timing-driven layout for high speed VLSI

ABSTRACT

An adaptive timing-driven layout system, called JUNE, has been developed. The constructive algorithm, which combines placement with the global routing, constructs a placement satisfying timing and routability constraints. The placement problem for each macro is solved hierarchically as a sequence of two optimization problems followed by an adaptive correction procedure. Experimental results for industrial sea-of-gates chips confirmed effectiveness of this approach.

REFERENCES

• ASA85: T. Asano , S. Sato, Long path enumeration algorithms for timing verification on large digital systems, Graph theory with applications to algorithms and computer science, John Wiley & Sons, Inc., New York, NY, 1985
• BUR85: Michael Burstein , Mary N. Youssef, Timing influenced layout design, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.124-130, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317845]
• CHA87: V. V. Chalam, Adaptive Control Systems: Techniques and Applications, Marcel Dekker, Inc., New York, NY, 1987
• DAI87: W.M. Dai, and et. al., "BEAR: A New Building-Block Layout System", Proc. International Conf. on Computer-Aided Design, pp. 88-91, 1987.
• DUN84: A. E. Dunlop , V. D. Agrawal , D. N. Deutsch , M. F. Jukl , P. Kozak , M. Wiesel, Chip layout optimization using critical path weighting, Proceedings of the 21st conference on Design automation, p.133-136, June 25-27, 1984, Albuquerque, New Mexico, United States
• HAN72: M. Hanan, J. Kurtzber8, Design Automation of Digital System - Vol 1 Theory and Techniques, (by Melvin A. Breuer), Chapter 5, Prentice-Hal|, Inc., 1972.
• HAU87: P.S. Hauge, R. Nair, E.J. Yoga, "Circuit Placement for Predictable Performance", Proc. Intern~tionM Conf. on Computer-Aided Design, pp. 34~87, 1987.
• IGU89: M. Igusa , M. Beardslee , A. Sangiovanni-Vicentelli, ORCA a sea-of-gates place and route system, Proceedings of the 26th ACM/IEEE conference on Design automation, p.122-127, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74404]
• JAC87: M. Jackson, E.S. Kuh, M. Marek-Sadowska, "Timing Driven Routing for Building Block Layout", Proc. Internation~l Syrup. on Circuits and Systems, pp. 518-519, 1987.
• JAC89: M. A. B. Jackson , E. S. Kuh, Performance-driven placement of cell based IC's, Proceedings of the 26th ACM/IEEE conference on Design automation, p.370-375, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74444]
• LEE61: C.Y. Lee, "An Algorithm for Path Connections and its Applications", IRE Trans. Electron. Comput., Sept., pp. 346-365, 1981.
• OGA86: Yasushi Ogawa , Tatsuki Ishii , Yoichi Shiraishi , Hidekazu Terai , Tokinori Kozawa , Kyoji Yuyama , Kyoji Chiba, Efficient placement algorithms optimizing delay for high-speed ECL masterslice LSIs, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.404-410, July 1986, Las Vegas, Nevada, United States
• SH88A: E. Sharagowitz , J. Lee , S. Sahni, Algorithms for physical design of `sea-of-gates' chips, Computer-Aided Design, v.20 n.7, p.382-397, Sept. 1988 [doi>10.1016/0010-4485(88)90215-1]
• SH88B: E. Shragowitz, H. Youssef, and Lionel C. Bening, "Predictive Tools in VLSI System Design. Timing Aspects", in proc. of COMPEURO'88, pp. 48-55.
• SH88C: E. Shra$owitz, J. Lee, S. Sahni, "New Approach to Function and Technique of Global Routing", International Journal of Computer Aided VLSI Design, Vol 1., pp. 25-49, 1988.
• TEI87: S. Tei$, R.L. Smith, and J. Seaton, "Timing-Driven Layout of Cell-Based iCs", Design Automation Guide., pp. 94-101, 1987
• YOU89: H. Youssef, E. Shru$owitz, and L. Bening, "Critical Path Issue in VLSI Design", Proc. International Conf. on Computer-Aided Design, pp. 520-523, 1989.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

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

General Terms:
Algorithms, Design, Experimentation