Standard cell placement using simulated sintering

ABSTRACT

Simulated annealing is a powerful optimization technique based on the annealing phenomenon in crystallization. In this paper we propose a simulated sintering technique which is analogous to the sintering process in material processing. In sintering one improves the quality of a processed material by heating it to a temperature close to the melting point. Analogously, we show that by starting out with a good initial configuration instead of a random configuration, and restricting uphill moves, we can considerably speed up simulated annealing. We use this idea for a standard cell placement program - GRIM in LTX2, an AT&T Bell Labs VLSI layout system. The initial configuration is produced either by changes to a layout the designer had done previously, or else by a fast program like min-cut. We obtain improvements of about 10% in chip area starting from a min-cut placement, in times about 3 times faster than our simulated annealing program (which itself is several times faster than other well known simulated annealing programs).

REFERENCES

• 1: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 2: S. Kirkpatrick, et al., "Optimization by simulated annealing," Science, vol. 220, pp.671-680, 1983.
• 3: N. Metropolis et al., Y. Chem. Phys., Vol. 21, pp. 1087, 1953. For a recent review see K. Binder, editor, "The Monte Carlo method in Statiatical Physics," New York: Springer Verlag, 1978.
• 4: B.W. Colbry & J. Soukup, "Layout aspects of the VLSI Microprocessor Design," International Sympoeium on Circuits and Systems, May 1982, pp.19.14-1228.
• 5: A. E. Dunlop, "Automatic Layout of Gate Arrays," International Sympoaium on Circuit~ and System~, May 1983, pp.1245-1248.
• 6: A. E. Dunlop & B. W. Kernighan, "A Placement procedure for Polycell VLSI Circuits," Proceedings of the ICCAD, pp.1045-1048, 1983.
• 7: Lay K. Grovel "A new simulated annealing algorithm for standard cell placement," Proceeding8 of the ICGAD, 1986.
• 8: Lay K. Graver, "GRIM - A Fast Simulated Annealing Program for Standard Cell Placement," Proceedings of the CTCC, 1987.
• 9: Steve White, "Concepts of scale in simulated annealing," Proeeedingn of the ICGD, 1984.
• 10: Lay K. Grovel "Simulated Annealing using approximate calculations," submitted to IEEE Transaction~ on CAD.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

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

General Terms:
Algorithms, Design