Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Simulated annealing methods have proven to be particularly successful in physical design applications, but often require burdensome, long run times. This paper studies the design and analysis of standard cell placement by annealing in a multiprocessor environment. Annealing is not static: we observe that the temperature parameter which controls hill-climbing in simulated annealing changes the behavior of an annealing algorithm as it runs, and strongly influences the choice of multiprocessor partitioning strategy. We introduce the idea of adaptive strategies that exhibit different speedups across different temperature ranges. Measured performance of parallel placement algorithms running on a multiprocessor demonstrate practical speedups consistent with our predictions.

REFERENCES

• 1: R. Ba~roa et al., "MACH-I: Aa Operating System Environment for Large-Scale Multiprocessor Applications", IEEE Software, July 1985.
• 2: Dah-Juh Chyan , Melvin A. Breuer, A placement algorithm for array processors, Proceedings of the 20th conference on Design automation, p.182-188, June 27-29, 1983, Miami Beach, Florida, United States
• 3: Alexander Iosupovicz , Clarence King , Melvin A. Breuer, A module interchange placement machine, Proceedings of the 20th conference on Design automation, p.171-174, June 27-29, 1983, Miami Beach, Florida, United States
• 4: S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, "Optimization by Simulated Annealing", Science, 220(4598):671-680 , May 1983.
• 5: S. Kravitz, "Multiprocessor-Bazed Placement by Simulated Annealing", Research Report CMUCAD-86-6, Dept. of ECE, Carnegie-Mellon University, February 1986.
• 6: C. Sechea, A. Sangiovaani Vineentelli, "The Timberwolf Placement and Routing Package", IEEE Journal of Solid-State Circuits, SC-20(2):510-522, April 1985.
• 7: R. Smith, "Accelerator Plans for Iterative Improvement Placement", Presentation at IEEE Physical Design Workshop, January 1985.
• 8: Philip M. Spira , Carl Hage, Hardware acceleration of gate array layout, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.359-366, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317913]
• 9: K. Ueda, T. Komatsubara, and T. Hosaka, "A Parallel Processing Approach for Logic Module Placement", IEEE Trans. on CAD, CAD-2(1):39-47 , January 1983.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization

  J. Computer Applications

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