ABSTRACT
Simulated annealing is a technique for finding an optimal or near-optimal solution for combinatorial optimization problems, or problems that have discrete variables. This technique was proposed by S. Kirkpatrick, C. Gelatt, and M. Vecchi in 1983 and has been successfully applied to circuit partitioning, placement, and routing in the physical design of integrated circuits. The critical ingredients for a implementing a successful placer based on simulated annealing are the simulated annealing cooling schedule, the cost function to be evaluated, and the generation of new state configurations or move strategies. In simulated annealing, the more new configurations generated during the course of a run, the higher the probability of achieving a better solution. One of the advantages of the simulated annealing algorithm is its ability to accommodate any cost function. Most simulated annealing placement algorithms predominately use two new configuration strategies or moves: a relocation of a single cell to a new position and a pairwise exchange of cells.
