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

Fingerprint

Simulated annealing
Annealing
Decomposition
Taxonomies
Temperature
Switches
Data storage equipment
Costs

ASJC Scopus subject areas

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

Cite this

Placement by Simulated Annealing on a Multiprocessor. / Kravitz, Saul A.; Rutenbar, Rob A.

In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 6, No. 4, 07.1987, p. 534-549.

Research output: Contribution to journalArticle

@article{1308a9553f964bee85aa75afa32c6173,
title = "Placement by Simulated Annealing on a Multiprocessor",
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.",
author = "Kravitz, {Saul A.} and Rutenbar, {Rob A.}",
year = "1987",
month = "7",
doi = "10.1109/TCAD.1987.1270301",
language = "English (US)",
volume = "6",
pages = "534--549",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

TY - JOUR

T1 - Placement by Simulated Annealing on a Multiprocessor

AU - Kravitz, Saul A.

AU - Rutenbar, Rob A.

PY - 1987/7

Y1 - 1987/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023383256&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023383256&partnerID=8YFLogxK

U2 - 10.1109/TCAD.1987.1270301

DO - 10.1109/TCAD.1987.1270301

M3 - Article

AN - SCOPUS:0023383256

VL - 6

SP - 534

EP - 549

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

SN - 0278-0070

IS - 4

ER -