Parallel simulated annealing using speculative computation

Author

Witte, Ellen E. ; Chamberlain, Roger D. ; Franklin, Mark A.

Author_Institution

Comput. & Commun. Res. Center, Washington Univ., St. Louis, MO, USA

Volume

2

Issue

4

fYear

1991

fDate

10/1/1991 12:00:00 AM

Firstpage

483

Lastpage

494

Abstract

A parallel simulated annealing algorithm that is problem-independent, maintains the serial decision sequence, and obtains speedup which can exceed log₂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

Keywords

parallel algorithms; simulated annealing; concurrency; hypercube multiprocessor; parallel simulated annealing algorithm; problem independent algorithm; processors; serial decision sequence; speculative computation; task assignment problem; Computational modeling; Concurrent computing; Cost function; Data structures; Hypercubes; Parallel algorithms; Parallel processing; Simulated annealing; Temperature control; Temperature distribution;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.97904

Filename

97904