Improving Annealing via Directed Moves

Simulated annealing remains a widely-used heuristic for FPGA placement due, in part, to its ability to produce high-quality placements while accommodating complex objective functions and architectural constraints. In this work, we investigate the concept of "directed moves" during annealing as a means of improving upon the quality and run-time of the technique. We intersperse "intelligent" strategies for selecting and placing cells along with traditional, random moves during an anneal. This allows our annealer to converge more quickly and to attain better-quality placements with less statistical variability. Our results confirm that, for the same amount of computational effort, directed moves achieve 5% and 10% improvement in critical path delay and wire length, respectively, compared to traditional annealing perturbations.