Parallel simulated annealing by generalized speculative computation

Andrew Sohn, Zhihong Wu, Xue Jin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Simulated annealing is known to be highly sequential due to loop carried dependencies. This report presents a new approach to parallel simulated annealing, called Generalized Speculative Computation (GSC). While the conventional binary speculative computation can execute a maximum of (log n) iterations in parallel on n processors, the GSC can execute n iterations in parallel while maintaining the same decision sequence as a sequential version. To demonstrate the performance of GSC, we implement 100 to 500 city Traveling Salesman Problem on the AP1000 massively parallel machine. Actual experimental results demonstrate that the GSC is highly effective for the given problem as we obtain a nearly 20-fold speedup for the initial temperature of 1 on 100 processors.

Original languageEnglish (US)
Title of host publicationProceedings of the 5th IEEE Symposium on Parallel and Distributed Processing
Editors Anon
PublisherPubl by IEEE
Pages416-419
Number of pages4
ISBN (Print)081864222X
StatePublished - Dec 1 1993
EventProceedings of the 5th IEEE Symposium on Parallel and Distributed Processing - Dallas, TX, USA
Duration: Dec 1 1993Dec 4 1993

Other

OtherProceedings of the 5th IEEE Symposium on Parallel and Distributed Processing
CityDallas, TX, USA
Period12/1/9312/4/93

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Parallel simulated annealing by generalized speculative computation'. Together they form a unique fingerprint.

Cite this