WSSA: A High Performance Simulated Annealing and Its Application to Transistor Placement

Shunji SAIKA  Masahiro FUKUI  Masahiko TOYONAGA  Toshiro AKINO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.12   pp.2584-2591
Publication Date: 2000/12/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Layout Synthesis
Keyword: 
simulated annealing,  temperature scheduling,  phase transition,  placement optimization,  cell synthesis,  

Full Text: PDF>>
Buy this Article




Summary: 
Another high performance simulated annealing is proposed which we call widely stepping simulated annealing (WSSA). It flies from a starting high temperature to a finishing low temperature staying at only twenty or so temperatures to approach thermal equilibriums. We survey the phase transition in simulated annealing process and estimate the major cost variation (dEc) at the critical temperature. The WSSA uses a function (H(t)) that represents the probability for a hill-climbing with the dEc of cost increase to be accepted in Metropolis' Monte Carlo simulation at temperature t. We have applied the first version of WSSA to one dimensional transistor placement optimizations for several industrial standard cells, and compared its performance with simulated annealing with a geometrically scheduled cooling. The solutions by the WSSA are as good as, and sometimes much better than, the solutions by the simulated annealing, while the time consumption by the WSSA is properly under one 30th of that by the simulated annealing.