Parallel speculative computation of simulated annealing

Research output: Contribution to journalConference articlepeer-review

4 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). We use an n-ary speculative tree and loop indices to execute n iterations in parallel on n processors while maintaining the same decision sequence as sequential simulated annealing. To verify the performance of GSC, we implement 100- to 500-city Traveling Salesman Problems on the AP1000 massively parallel multiprocessor. Execution results demonstrate that the GSC approach can indeed be an effective method for simulated annealing. We obtain over 20-fold speedup for the initial temperature of 0.1 and 11-fold speedup for the initial temperature of 10, all on 100 processors.

Original languageEnglish (US)
Article number5727820
Pages (from-to)III8-III11
JournalProceedings of the International Conference on Parallel Processing
Volume3
DOIs
StatePublished - 1994
Event23rd International Conference on Parallel Processing, ICPP 1994 - Raleigh, NC, United States
Duration: Aug 15 1994Aug 19 1994

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Hardware and Architecture

Fingerprint

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

Cite this