Simulated annealing on a multiprocessor

Roger D. Chamberlain; Mark N. Edelman; Mark A. Franklin; Ellen E. Witte

Simulated annealing on a multiprocessor

Roger D. Chamberlain
, Mark N. Edelman
, Mark A. Franklin
, Ellen E. Witte

Department of Computer Science & Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

14 Scopus citations

Abstract

The authors present a method for parallelizing the simulated annealing algorithm by mapping the algorithm onto a dynamically structured tree of processors. The resulting parallel simulated annealing algorithm is discussed and its performance evaluated using simulation techniques. An important property of the parallel algorithm is that it maintains the same move decision sequence as the serial simulated annealing algorithm, thus avoiding problems associated with move conflicts and erroneous move acceptance/rejection decisions which have been associated with other parallel simulated annealing algorithm proposals. The parallel algorithm presented achieves speedups between log₂N and (N+log₂N)/2 where N is the number of processors in the parallel processor. Experimental results are presented on three versions of the basic method: the static, dynamic balanced, and dynamic unbalanced parallel-simulated-annealing algorithms.

Original language	English
Title of host publication	1988 IEEE Int Conf Comput Des VLSI Comput Process ICCD 88 Proc
Publisher	Publ by IEEE
Pages	540-544
Number of pages	5
ISBN (Print)	0818608722
State	Published - 1988

Publication series

Name	1988 IEEE Int Conf Comput Des VLSI Comput Process ICCD 88 Proc

Cite this

@inproceedings{f20c0917d67049b797afe4aeec9cdb94,

title = "Simulated annealing on a multiprocessor",

abstract = "The authors present a method for parallelizing the simulated annealing algorithm by mapping the algorithm onto a dynamically structured tree of processors. The resulting parallel simulated annealing algorithm is discussed and its performance evaluated using simulation techniques. An important property of the parallel algorithm is that it maintains the same move decision sequence as the serial simulated annealing algorithm, thus avoiding problems associated with move conflicts and erroneous move acceptance/rejection decisions which have been associated with other parallel simulated annealing algorithm proposals. The parallel algorithm presented achieves speedups between log2N and (N+log2N)/2 where N is the number of processors in the parallel processor. Experimental results are presented on three versions of the basic method: the static, dynamic balanced, and dynamic unbalanced parallel-simulated-annealing algorithms.",

author = "Chamberlain, \{Roger D.\} and Edelman, \{Mark N.\} and Franklin, \{Mark A.\} and Witte, \{Ellen E.\}",

year = "1988",

language = "English",

isbn = "0818608722",

series = "1988 IEEE Int Conf Comput Des VLSI Comput Process ICCD 88 Proc",

publisher = "Publ by IEEE",

pages = "540--544",

booktitle = "1988 IEEE Int Conf Comput Des VLSI Comput Process ICCD 88 Proc",

}

Simulated annealing on a multiprocessor. / Chamberlain, Roger D.; Edelman, Mark N.; Franklin, Mark A. et al.
1988 IEEE Int Conf Comput Des VLSI Comput Process ICCD 88 Proc. Publ by IEEE, 1988. p. 540-544 (1988 IEEE Int Conf Comput Des VLSI Comput Process ICCD 88 Proc).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Simulated annealing on a multiprocessor

AU - Chamberlain, Roger D.

AU - Edelman, Mark N.

AU - Franklin, Mark A.

AU - Witte, Ellen E.

PY - 1988

Y1 - 1988

N2 - The authors present a method for parallelizing the simulated annealing algorithm by mapping the algorithm onto a dynamically structured tree of processors. The resulting parallel simulated annealing algorithm is discussed and its performance evaluated using simulation techniques. An important property of the parallel algorithm is that it maintains the same move decision sequence as the serial simulated annealing algorithm, thus avoiding problems associated with move conflicts and erroneous move acceptance/rejection decisions which have been associated with other parallel simulated annealing algorithm proposals. The parallel algorithm presented achieves speedups between log2N and (N+log2N)/2 where N is the number of processors in the parallel processor. Experimental results are presented on three versions of the basic method: the static, dynamic balanced, and dynamic unbalanced parallel-simulated-annealing algorithms.

AB - The authors present a method for parallelizing the simulated annealing algorithm by mapping the algorithm onto a dynamically structured tree of processors. The resulting parallel simulated annealing algorithm is discussed and its performance evaluated using simulation techniques. An important property of the parallel algorithm is that it maintains the same move decision sequence as the serial simulated annealing algorithm, thus avoiding problems associated with move conflicts and erroneous move acceptance/rejection decisions which have been associated with other parallel simulated annealing algorithm proposals. The parallel algorithm presented achieves speedups between log2N and (N+log2N)/2 where N is the number of processors in the parallel processor. Experimental results are presented on three versions of the basic method: the static, dynamic balanced, and dynamic unbalanced parallel-simulated-annealing algorithms.

UR - https://www.scopus.com/pages/publications/0024128194

M3 - Conference contribution

AN - SCOPUS:0024128194

SN - 0818608722

T3 - 1988 IEEE Int Conf Comput Des VLSI Comput Process ICCD 88 Proc

SP - 540

EP - 544

BT - 1988 IEEE Int Conf Comput Des VLSI Comput Process ICCD 88 Proc

PB - Publ by IEEE

ER -

Simulated annealing on a multiprocessor

Abstract

Publication series

Other files and links

Fingerprint

Cite this