Placement by Simulated Annealing on a Multiprocessor

Saul A. Kravitz, Rob A. Rutenbar

Research output: Contribution to journalArticle

Abstract

Physical design tools based on simulated annealing algorithms have been shown to produce results of extremely high quality, but typically at a very high cost in execution time. This paper selects a representative annealing application—standard cell placement—and develops multiprocessor-based annealing algorithms for placement. A taxonomy of possible multiprocessor decompositions of annealing algorithms is presented which divides decomposition schemes into two broad classes: Those which divide individual moves into subtasks and distribute them across cooperating processors, and those which perform complete moves in parallel. It is shown that the choice of multiprocessor annealing strategy is influenced by temperature; in particular, the paper introduces the idea of adaptive strategies that dynamically change the parallel decomposition scheme to achieve maximum speedup as the annealing task progresses through each temperature regime. Implementations of three parallel placement strategies are described for an experimental shared-memory multiprocessor. Practical speedups are achieved over a serial version of the algorithm, and it is shown that an adaptive strategy which switches between two parallel decompositions at the optimal temperature yields speedup significantly better than any single strategy approach. Models are developed to account for the observed performance, and to predict the crossover points for switching strategies.

Original languageEnglish (US)
Pages (from-to)534-549
Number of pages16
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume6
Issue number4
DOIs
StatePublished - Jul 1987

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Placement by Simulated Annealing on a Multiprocessor'. Together they form a unique fingerprint.

  • Cite this