t(k)-SA: Accelerated Simulated Annealing Algorithm for Application Mapping on Networks-on-Chip

: Yang B, Guang L, Santti T, Plosila J

: Terry Soule

: 2012

: Genetic and Evolutionary Computation Conference (GECCO 2012)

: PROCEEDINGS OF THE FOURTEENTH INTERNATIONAL CONFERENCE ON GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE

: 1191

: 1198

: 8

: 978-1-4503-1177-9

DOI: https://doi.org/10.1145/2330163.2330327

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 t(k)-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.