Parallelizing simulated annealing algorithm in many integrated core architecture

Junhao ZHOU, Hong XIAO, Hao WANG*, Hong Ning DAI

*Corresponding author for this work

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

2 Citations (Scopus)

Abstract

The simulated annealing algorithm (SAA) is a wellestablished approach to the approximate solution of combinatorial optimisation problems. SAA allows for occasional uphill moves in an attempt to reduce the probability of becoming stuck in a poor but locally optimal solution. Previous work showed that SAA can find better solutions, but it takes much longer time. In this paper, in order to harness the power of the very recent hybrid Many Integrated Core Architecture (MIC), we propose a new parallel simulated annealing algorithm customised for MIC. Our experiments with the Travelling Salesman Problem (TSP) show that our parallel SAA gains significant speedup.

Original languageEnglish
Title of host publicationComputational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings
EditorsAna Maria A.C. Rocha, Shangguang Wang, David Taniar, Beniamino Murgante, Carmelo M. Torre, Elena Stankova, Bernady O. Apduhan, Sanjay Misra, Osvaldo Gervasi
PublisherSpringer-Verlag GmbH and Co. KG
Pages239-250
Number of pages12
ISBN (Print)9783319421070
DOIs
Publication statusPublished - Jul 2016
Externally publishedYes
Event16th International Conference on Computational Science and Its Applications, ICCSA 2016 - Beijing, China
Duration: 4 Jul 20167 Jul 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9787
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Computational Science and Its Applications, ICCSA 2016
Country/TerritoryChina
CityBeijing
Period4/07/167/07/16

Bibliographical note

Funding Information:
The work described in this paper was partially supported by Macao Science and Technology Development Fund under Grant No. 096/2013/A3 and the NSFC-Guangdong Joint Fund under Grant No. U1401251 and Guangdong Science and Technology Program under Grant No.2015B090923004.

Publisher Copyright:
© Springer International Publishing Switzerland 2016.

Keywords

  • MIC optimization
  • Parallel computing
  • Simulated annealing

Fingerprint

Dive into the research topics of 'Parallelizing simulated annealing algorithm in many integrated core architecture'. Together they form a unique fingerprint.

Cite this