Quality-time tradeoffs in simulated annealing for VLSI placement

A model is presented to characterize the relationship between the best solution (incumbent) found by an iterative algorithm (simulated annealing) and the time spent in achieving it. The target application has been chosen to be the placement of cells on a VLSI chip. The model is used to achieve a tradeoff between solution quality and time spent. This gives an idea of the time at which the iterative algorithm should be terminated when the marginal gain in solution quality is smaller than the marginal increase in cost (or time) spent. Nonlinear regression analysis is used to predict the decrease in time with respect to improvement in solution quality. Experimental results on benchmark circuits are presented to show the errors of run-time prediction compared to a static prediction