Exploring alternate trade-offs of placement quality versus runtime in Simulated Annealing algorithm

Simulated Annealing (SA) algorithm is widely employed to achieve optimal placement solution for FPGAs. However, it attempts a notably large number of placement moves on each temperature step, thus increasing the placement runtime considerably. The work presented in this paper reduces the placement runtime by intelligently reducing the total number of placement moves attempted on each temperature step. We have proposed four alternate formulas for calculating the number of moves that must be attempted per temperature step. Empirical study shows that our proposed formulas have achieved up to 2.1 times reduction in placement runtime without compromising placement quality.