MHERTZ: a new optimization algorithm for floorplanning and global routing

ABSTRACT

Timing-driven placement is essential for full-custom VLSI, Gallium Arsenide, and ECL circuits to meet wire timing constraints. A new macro/custom cell floorplanner and global router, called MHERTZ, meets wire timing constraints by using force-directed cost functions in multi-start and simulated annealing (SA) optimization algorithms. MHERTZ also prevents wire coupling, meets specified chip aspect ratios, and produces smaller floorplans than TIMBERWOLFMC.

REFERENCES

• 1: D.B.. Brasen. MHEI~TZ" A New Optimization Algorithm For Floorplanning And Global Routing Of Integrated Circuits. Master's thesis, Rutgers U,, Oct. 1989.
• 2: N.P. Chen. New Algorithms For Steiner Tree on Graphs, In Proc. of ISCAS, pp 1217-1219, May 1983,
• 3: N.P. Chen, C.P. Hsu, and E.S. Kuh. The Berkeley Building-Dlock (BBL) Layout System for VLSI Design. In VLSI '83, pp 37-44. North-Holland~ Aug. 1983.
• 4: W. Dai, H. Chen, R. Durra, M. Jackson, E.S. Kuh, et. al. BEAR: A New Building-Block Layout System. In Proc. of" the ICCAD, pp 34-37. Nov. 1987.
• 5: 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
• 6: J. B. Lassere , P. P. Varaiya , J. Walrand, Simulated Annealing, Random Search, MultiStart or SAD?, Systems & Control Letters, v.8 n.4, p.297-301, March 1987 [doi>10.1016/0167-6911(87)90094-6]
• 7: N.R. Quinn and M,A Breuer. A Forced.Directed Component Placement Procedure For Printed Circuit Boards. IEEE Trans. on Circuit8 and Spstems, CAS- 26(6):377-388, June 1979.
• 8: Carl Sechen, Chip-planning, placement, and global routing of macro/custom cell integrated circuits using simulated annealing, Proceedings of the 25th ACM/IEEE conference on Design automation, p.73-80, June 12-15, 1988, Atlantic City, New Jersey, United States

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

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, Experimentation