Temperature measurement and equilibrium dynamics of simulated annealing placements

One way to alleviate the heavy computation required by simulated annealing placement algorithms is to replace a significant fraction of the higher or middle temperatures with a faster heuristic, and then follow it with simulated annealing. A crucial issue in this approach is the determination of the starting temperature for the simulated annealing phase-a temperature should be chosen that causes an appropriate amount of optimization to be done, but makes good use of the structure provided by the heuristic. A method for measuring the temperature of an existing placement is presented. The approach is based on the measurement of the probability distribution of the change in cost function, P(ΔC), and makes the assumption that the placement is in simulated annealing equilibrium at some temperature. The temperature of placements produced by both a simulated annealing and a min-cut placement algorithm are measured, and good agreement with known temperatures is obtained. The P(ΔC) distribution is also used to give an interesting view of the equilibrium dynamics of simulated annealing