Learning as applied to stochastic optimization for standard-cell placement

Lixin Su, Wray Buntine, A. Richard Newton, Bradley S. Peters

Research output: Contribution to journalArticleResearchpeer-review

8 Citations (Scopus)

Abstract

Stochastic combinatorial optimization techniques, such as simulated annealing and genetic algorithms, have become increasingly important in design automation as the size of design problems have grown and the design objectives have become increasingly complex. However, stochastic algorithms are often slow since a large number of random design perturbations are required to achieve an acceptable result-they have no built-in "intelligence". In this paper, it is shown that statistical learning techniques can improve the quality of results and reduce the number of expensive cost-function evaluations for stochastic optimization for a particular solution quality. In particular, simulated annealing was selected as a representative stochastic optimization approach and a two-dimensional cell-based layout placement problem was used to evaluate the utility of such a learning-based approach. In this paper, we used regression to learn the properties of the solution space and tested the trained algorithm on a number of examples to demonstrate the improvement gained. A general response model is constructed by learning from the annealing of benchmark circuits. This model is then used in the trained simulated annealing, which returns significantly better annealing quality than the untrained algorithm for the same number of moves in the solution space. The annealing quality improvement was 15%-43% for the set of examples used in training and 7%-21% when the trained algorithm was applied to new examples. With the same amount of central processing unit time, the trained algorithm improved the annealing quality by up to 28% for some benchmark circuits we tested. In addition, the use of the response model successfully predicted the effect of the windowed sampling technique and derived the informally accepted advantages of windowing from the test set automatically.

Original languageEnglish
Pages (from-to)516-527
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume20
Issue number4
DOIs
Publication statusPublished - 1 Apr 2001

Keywords

  • Circuit
  • Floorplanning
  • Large-scale optimization
  • Layout
  • Learning
  • Physical design
  • Placement
  • Stochastic optimization
  • VLSI

Cite this

@article{c6823fd3dbdc433295ee2862d163d612,
title = "Learning as applied to stochastic optimization for standard-cell placement",
abstract = "Stochastic combinatorial optimization techniques, such as simulated annealing and genetic algorithms, have become increasingly important in design automation as the size of design problems have grown and the design objectives have become increasingly complex. However, stochastic algorithms are often slow since a large number of random design perturbations are required to achieve an acceptable result-they have no built-in {"}intelligence{"}. In this paper, it is shown that statistical learning techniques can improve the quality of results and reduce the number of expensive cost-function evaluations for stochastic optimization for a particular solution quality. In particular, simulated annealing was selected as a representative stochastic optimization approach and a two-dimensional cell-based layout placement problem was used to evaluate the utility of such a learning-based approach. In this paper, we used regression to learn the properties of the solution space and tested the trained algorithm on a number of examples to demonstrate the improvement gained. A general response model is constructed by learning from the annealing of benchmark circuits. This model is then used in the trained simulated annealing, which returns significantly better annealing quality than the untrained algorithm for the same number of moves in the solution space. The annealing quality improvement was 15{\%}-43{\%} for the set of examples used in training and 7{\%}-21{\%} when the trained algorithm was applied to new examples. With the same amount of central processing unit time, the trained algorithm improved the annealing quality by up to 28{\%} for some benchmark circuits we tested. In addition, the use of the response model successfully predicted the effect of the windowed sampling technique and derived the informally accepted advantages of windowing from the test set automatically.",
keywords = "Circuit, Floorplanning, Large-scale optimization, Layout, Learning, Physical design, Placement, Stochastic optimization, VLSI",
author = "Lixin Su and Wray Buntine and Newton, {A. Richard} and Peters, {Bradley S.}",
year = "2001",
month = "4",
day = "1",
doi = "10.1109/43.918210",
language = "English",
volume = "20",
pages = "516--527",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "IEEE, Institute of Electrical and Electronics Engineers",
number = "4",

}

Learning as applied to stochastic optimization for standard-cell placement. / Su, Lixin; Buntine, Wray; Newton, A. Richard; Peters, Bradley S.

In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No. 4, 01.04.2001, p. 516-527.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Learning as applied to stochastic optimization for standard-cell placement

AU - Su, Lixin

AU - Buntine, Wray

AU - Newton, A. Richard

AU - Peters, Bradley S.

PY - 2001/4/1

Y1 - 2001/4/1

N2 - Stochastic combinatorial optimization techniques, such as simulated annealing and genetic algorithms, have become increasingly important in design automation as the size of design problems have grown and the design objectives have become increasingly complex. However, stochastic algorithms are often slow since a large number of random design perturbations are required to achieve an acceptable result-they have no built-in "intelligence". In this paper, it is shown that statistical learning techniques can improve the quality of results and reduce the number of expensive cost-function evaluations for stochastic optimization for a particular solution quality. In particular, simulated annealing was selected as a representative stochastic optimization approach and a two-dimensional cell-based layout placement problem was used to evaluate the utility of such a learning-based approach. In this paper, we used regression to learn the properties of the solution space and tested the trained algorithm on a number of examples to demonstrate the improvement gained. A general response model is constructed by learning from the annealing of benchmark circuits. This model is then used in the trained simulated annealing, which returns significantly better annealing quality than the untrained algorithm for the same number of moves in the solution space. The annealing quality improvement was 15%-43% for the set of examples used in training and 7%-21% when the trained algorithm was applied to new examples. With the same amount of central processing unit time, the trained algorithm improved the annealing quality by up to 28% for some benchmark circuits we tested. In addition, the use of the response model successfully predicted the effect of the windowed sampling technique and derived the informally accepted advantages of windowing from the test set automatically.

AB - Stochastic combinatorial optimization techniques, such as simulated annealing and genetic algorithms, have become increasingly important in design automation as the size of design problems have grown and the design objectives have become increasingly complex. However, stochastic algorithms are often slow since a large number of random design perturbations are required to achieve an acceptable result-they have no built-in "intelligence". In this paper, it is shown that statistical learning techniques can improve the quality of results and reduce the number of expensive cost-function evaluations for stochastic optimization for a particular solution quality. In particular, simulated annealing was selected as a representative stochastic optimization approach and a two-dimensional cell-based layout placement problem was used to evaluate the utility of such a learning-based approach. In this paper, we used regression to learn the properties of the solution space and tested the trained algorithm on a number of examples to demonstrate the improvement gained. A general response model is constructed by learning from the annealing of benchmark circuits. This model is then used in the trained simulated annealing, which returns significantly better annealing quality than the untrained algorithm for the same number of moves in the solution space. The annealing quality improvement was 15%-43% for the set of examples used in training and 7%-21% when the trained algorithm was applied to new examples. With the same amount of central processing unit time, the trained algorithm improved the annealing quality by up to 28% for some benchmark circuits we tested. In addition, the use of the response model successfully predicted the effect of the windowed sampling technique and derived the informally accepted advantages of windowing from the test set automatically.

KW - Circuit

KW - Floorplanning

KW - Large-scale optimization

KW - Layout

KW - Learning

KW - Physical design

KW - Placement

KW - Stochastic optimization

KW - VLSI

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

U2 - 10.1109/43.918210

DO - 10.1109/43.918210

M3 - Article

AN - SCOPUS:0035308898

VL - 20

SP - 516

EP - 527

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 -