t_k-SA: Accelerated Simulated Annealing Algorithm for Application Mapping on Networks-on-Chip

摘要

Simulated Annealing (SA) algorithm is a promising method for solving combinatorial optimization problems. The only limitation of applying the SA algorithm to application mapping problem on many-core networks-on-chip (NoCs) is its low speed. To alleviate this limitation, an accelerated SA algorithm called tk-SA algorithm is proposed in this work. The t_k-SA algorithm starts the annealing process from a lower initial temperature t_k with an optimized initial mapping solution. Based on the analysis of the typical behavior of the general SA algorithm, an efficient method is proposed for determining the temperature t_k. Quantitative evaluations verify that the method is capable of obtaining an appropriate t_k such that the t_k-SA algorithm can reproduce the behavior of the full-range SA from temperature t_k. Experimental results show that compared with a parameter-optimized SA algorithm, the proposed t_k-SA algorithm achieves an average speedup of 1.55 without loss of solution quality.