Generalized speculative computation of parallel simulated annealing

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

Simulated annealing is known to be highly sequential due to dependences between iterations. While the conventional speculative computation with a binary tree has been found effective for parallel simulated annealing, its performance is limited to (log p)-fold speedup due to parallel execution of log p iterations on p processors. This report presents a new approach to parallel simulated annealing, called generalized speculative computation (GSC). The GSC is synchronous, maintaining the same decision sequence as sequential simulated annealing. The use of two loop indices encoded in a single integer eliminates broadcasting of central data structure to all processors. The master-slave parallel programming paradigm simplifies controlling the activities of p iterations which are executed in parallel on p processors. To verify the performance of GSC, we implemented 100-city to 500-city Traveling Salesman Problems on the AP1000 massively parallel multiprocessor. Execution results on the AP1000 demonstrate that the GSC approach can indeed be an effective method for parallel simulated annealing as it gave over 20-fold speedup on 100 processors.

Original languageEnglish (US)
Pages (from-to)29-55
Number of pages27
JournalAnnals of Operations Research
Volume63
DOIs
StatePublished - 1996

All Science Journal Classification (ASJC) codes

  • General Decision Sciences
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Generalized speculative computation of parallel simulated annealing'. Together they form a unique fingerprint.

Cite this