• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

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

Bo Yang, Liang Guang, Tero Säntti, Juha Plosila, tk-SA: Accelerated Simulated Annealing Algorithm for Application Mapping on Networks-on-Chip. In: Terry Soule (Ed.), Genetic and Evolutionary Computation Conference (GECCO 2012), 1191–1198, ACM, 2012.

http://dx.doi.org/10.1145/2330163.2330327

Abstract:

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.

BibTeX entry:

@INPROCEEDINGS{inpYaGuSxPl12a,
  title = {tk-SA: Accelerated Simulated Annealing Algorithm for Application Mapping on Networks-on-Chip},
  booktitle = {Genetic and Evolutionary Computation Conference (GECCO 2012)},
  author = {Yang, Bo and Guang, Liang and Säntti, Tero and Plosila, Juha},
  editor = {Soule, Terry},
  publisher = {ACM},
  pages = {1191–1198},
  year = {2012},
  keywords = {Simulated Annealing, Networks-on-Chip, Application Mapping},
}

Belongs to TUCS Research Unit(s): Embedded Computer and Electronic Systems (ECES)

Edit publication