Parallel N-ary Speculative Computation of Simulated Annealing

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

Simulated annealing is known to be an efficient method for combinatorial optimization problems. Its usage for realistic problem size, however, has been limited by the long execution time due to its sequential nature. This report presents a practical approach to synchronous simulated annealing for massively parallel distributed-memory multiprocessors. We use an n-ary speculative tree to execute n different iterations in parallel on n processors, called Generalized Speculative Computation (GSC). Execution results of the 100- to 500-city Traveling Salesman Problems on the AP1000 massively parallel multiprocessor demonstrate that the GSC approach can be an effective method for parallel simulated annealing as it gave over 20-fold speedup on 100 processors.

Original languageEnglish (US)
Pages (from-to)997-1005
Number of pages9
JournalIEEE Transactions on Parallel and Distributed Systems
Volume6
Issue number10
DOIs
StatePublished - Oct 1995

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • Parallel simulated annealing
  • Traveling Salesman Problem
  • combinatorial optimization
  • simulated annealing
  • speculative computation
  • synchronous simulated annealing

Fingerprint Dive into the research topics of 'Parallel N-ary Speculative Computation of Simulated Annealing'. Together they form a unique fingerprint.

Cite this