Parallel Simulated Annealing Using Speculative Computation

Simulated annealing is a technique for obtaining approximate solutions to combinatorial optimization problems. The serial algorithm, however, can require extensive computation time. Most parallel algorithms for simulated annealing are problem-specific and/or violate the serial decision sequence, thereby allowing errors not present in the serial algorithm. With existing proofs, maintaining the serial sequence is necessary to prove that the algorithm converges to a global optimum solution when allowed to reach equilibrium at each temperature. This paper describes a new parallel algorithm which is both problem-independent and maintains the serial decision sequence. The parallel algorithm uses the concurrency technique of speculative computation to achieve speedup which can exceed log₂P, on P processors. This paper describes the parallel algorithm, its implementation on a hypercube multiprocessor, and the application to the important parallel processing problem of task assignment.