On simulated annealing in EDA

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

Abstract

Simulated annealing was first introduced in 1983 as a generic stochastic algorithmic approach to solve optimization problems. Prof. C. L. Liu and his students H. W. Leong and D. F. Wong were among the earliest EDA researchers who applied simulated annealing to EDA. They solved a wide range of EDA problems with successes and reported their results in a series of papers at premier EDA conferences such DAC and ICCAD. Liu, Leong, and Wong later summarized their works in a research monograph entitled Simulated Annealing for VLSI Design, published in 1988 by Kluwer Academic Publishers. In the Preface of their book, the authors wrote "We hope that our experiences with the techniques we employed, some of which indeed bear certain similarities for different problems, could be useful as hints and guides for other researchers in applying the method to the solutions of other problems". Indeed, there were "similarities in techniques" among Liu's works that had influenced the design of simulated annealing EDA algorithms in the past 20 some years. To better understand Liu's contributions in simulated annealing, one should note that a typical simulated annealing algorithm uses a solution space and a cost function that come directly with the problem. Although computation time may be high, the algorithm is straightforward to design, making simulated annealing an attractive option for difficult problems where clever algorithms are hard to come by. On the contrary, Liu's simulated annealing algorithms have a completely different style: They resemble clever algorithms that attempt to solve difficult problems in polynomial time, and they often have a strong algorithmic flavor with a significant effort spent on optimizing the solution space and cost function. In this talk, we will discuss Prof. Liu's pioneering contributions in simulated annealing for EDA.
Original languageEnglish
Title of host publicationISPD'12 - Proceedings of the 2012 International Symposium on Physical Design
EditorsJiang Hu
PublisherAssociation for Computing Machinery (ACM)
Pages63
Number of pages1
ISBN (Print)9781450311670
DOIs
Publication statusPublished - 25 Mar 2012
Event2012 ACM International Symposium on Physical Design, ISPD'12 - Napa, CA, United States
Duration: 25 Mar 201228 May 2012

Publication series

NameProceedings of the International Symposium on Physical Design
PublisherAssociation for Computing Machinery

Symposium

Symposium2012 ACM International Symposium on Physical Design, ISPD'12
Country/TerritoryUnited States
CityNapa, CA
Period25/03/1228/05/12

Scopus Subject Areas

  • Electrical and Electronic Engineering

User-Defined Keywords

  • Simulated annealing
  • electronic design automation
  • EDA
  • computer-aided design
  • CAD
  • VLSI

Fingerprint

Dive into the research topics of 'On simulated annealing in EDA'. Together they form a unique fingerprint.

Cite this