Parallelizing simulated annealing algorithm in many integrated core architecture

Junhao ZHOU; Hong XIAO; Hao WANG; Hong Ning DAI

doi:10.1007/978-3-319-42108-7_18

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 Proceedings › Conference paper (refereed) › Research › peer-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 language	English
Title of host publication	Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings
Editors	Ana Maria A.C. Rocha, Shangguang Wang, David Taniar, Beniamino Murgante, Carmelo M. Torre, Elena Stankova, Bernady O. Apduhan, Sanjay Misra, Osvaldo Gervasi
Publisher	Springer-Verlag GmbH and Co. KG
Pages	239-250
Number of pages	12
ISBN (Print)	9783319421070
DOIs	https://doi.org/10.1007/978-3-319-42108-7_18
Publication status	Published - Jul 2016
Externally published	Yes
Event	16th International Conference on Computational Science and Its Applications, ICCSA 2016 - Beijing, China Duration: 4 Jul 2016 → 7 Jul 2016

Publication series

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

Conference

Conference	16th International Conference on Computational Science and Its Applications, ICCSA 2016
Country/Territory	China
City	Beijing
Period	4/07/16 → 7/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

Access to Document

10.1007/978-3-319-42108-7_18

Cite this

ZHOU, J., XIAO, H., WANG, H., & DAI, H. N. (2016). Parallelizing simulated annealing algorithm in many integrated core architecture. In A. M. A. C. Rocha, S. Wang, D. Taniar, B. Murgante, C. M. Torre, E. Stankova, B. O. Apduhan, S. Misra, & O. Gervasi (Eds.), Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings (pp. 239-250). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9787). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-42108-7_18

ZHOU, Junhao ; XIAO, Hong ; WANG, Hao ; DAI, Hong Ning. / Parallelizing simulated annealing algorithm in many integrated core architecture. Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. editor / Ana Maria A.C. Rocha ; Shangguang Wang ; David Taniar ; Beniamino Murgante ; Carmelo M. Torre ; Elena Stankova ; Bernady O. Apduhan ; Sanjay Misra ; Osvaldo Gervasi. Springer-Verlag GmbH and Co. KG, 2016. pp. 239-250 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9a46247451dd4e6abdcd71fa64df88a5,

title = "Parallelizing simulated annealing algorithm in many integrated core architecture",

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.",

keywords = "MIC optimization, Parallel computing, Simulated annealing",

author = "Junhao ZHOU and Hong XIAO and Hao WANG and DAI, {Hong Ning}",

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: {\textcopyright} Springer International Publishing Switzerland 2016.; 16th International Conference on Computational Science and Its Applications, ICCSA 2016 ; Conference date: 04-07-2016 Through 07-07-2016",

year = "2016",

month = jul,

doi = "10.1007/978-3-319-42108-7_18",

language = "English",

isbn = "9783319421070",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag GmbH and Co. KG",

pages = "239--250",

editor = "Rocha, {Ana Maria A.C.} and Shangguang Wang and David Taniar and Beniamino Murgante and Torre, {Carmelo M.} and Elena Stankova and Apduhan, {Bernady O.} and Sanjay Misra and Osvaldo Gervasi",

booktitle = "Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings",

address = "Germany",

}

ZHOU, J, XIAO, H, WANG, H & DAI, HN 2016, Parallelizing simulated annealing algorithm in many integrated core architecture. in AMAC Rocha, S Wang, D Taniar, B Murgante, CM Torre, E Stankova, BO Apduhan, S Misra & O Gervasi (eds), Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9787, Springer-Verlag GmbH and Co. KG, pp. 239-250, 16th International Conference on Computational Science and Its Applications, ICCSA 2016, Beijing, China, 4/07/16. https://doi.org/10.1007/978-3-319-42108-7_18

Parallelizing simulated annealing algorithm in many integrated core architecture. / ZHOU, Junhao; XIAO, Hong; WANG, Hao; DAI, Hong Ning.

Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. ed. / Ana Maria A.C. Rocha; Shangguang Wang; David Taniar; Beniamino Murgante; Carmelo M. Torre; Elena Stankova; Bernady O. Apduhan; Sanjay Misra; Osvaldo Gervasi. Springer-Verlag GmbH and Co. KG, 2016. p. 239-250 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9787).

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

TY - GEN

T1 - Parallelizing simulated annealing algorithm in many integrated core architecture

AU - ZHOU, Junhao

AU - XIAO, Hong

AU - WANG, Hao

AU - DAI, Hong Ning

N1 - 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.

PY - 2016/7

Y1 - 2016/7

N2 - 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.

AB - 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.

KW - MIC optimization

KW - Parallel computing

KW - Simulated annealing

UR - http://www.scopus.com/inward/record.url?scp=84978863390&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-42108-7_18

DO - 10.1007/978-3-319-42108-7_18

M3 - Conference paper (refereed)

AN - SCOPUS:84978863390

SN - 9783319421070

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 239

EP - 250

BT - Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings

A2 - Rocha, Ana Maria A.C.

A2 - Wang, Shangguang

A2 - Taniar, David

A2 - Murgante, Beniamino

A2 - Torre, Carmelo M.

A2 - Stankova, Elena

A2 - Apduhan, Bernady O.

A2 - Misra, Sanjay

A2 - Gervasi, Osvaldo

PB - Springer-Verlag GmbH and Co. KG

T2 - 16th International Conference on Computational Science and Its Applications, ICCSA 2016

Y2 - 4 July 2016 through 7 July 2016

ER -

ZHOU J, XIAO H, WANG H, DAI HN. Parallelizing simulated annealing algorithm in many integrated core architecture. In Rocha AMAC, Wang S, Taniar D, Murgante B, Torre CM, Stankova E, Apduhan BO, Misra S, Gervasi O, editors, Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. Springer-Verlag GmbH and Co. KG. 2016. p. 239-250. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-42108-7_18

Parallelizing simulated annealing algorithm in many integrated core architecture

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this