### 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 language | English |
---|---|

Pages (from-to) | 516-527 |

Number of pages | 12 |

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

Volume | 20 |

Issue number | 4 |

DOIs | |

Publication status | Published - 1 Apr 2001 |

### Keywords

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

### Cite this

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

*20*(4), 516-527. https://doi.org/10.1109/43.918210

}

*IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems*, vol. 20, no. 4, pp. 516-527. https://doi.org/10.1109/43.918210

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

Research output: Contribution to journal › Article › Research › peer-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 -