05106979

j

05106979 Witte, E.E. Chamberlain, R.D. Franklin, M.A. Parallel Simulated Annealing using Speculative Computation. IEEE Transactions on Parallel and Distributed Systems 02, No.04, 483-494 (1991). 1991 Institute of Electrical and Electronics Engineers (IEEE), New York, NY EN Index Termsproblem independent algorithm speculative computation parallel simulated annealingalgorithm serial decision sequence processors concurrency hypercube multiprocessor task assignment problem parallel algorithms simulated annealing

doi:10.1109/71.97904

Summary: A parallel simulated annealing algorithm that is problem-independent, maintains the serial decision sequence, and obtains speedup which can exceed log/sub 2/P on P processors is discussed. The algorithm achieves parallelism by using the concurrency technique of speculative computation. Implementation of the parallel algorithm on a hypercube multiprocessor and application to a task assignment problem are described. The simulated annealing solutions are shown to be, on average, 28% better than the solutions produced by a random task assignment algorithm and 2% better than the solutions produced by a heuristic.