Abstract
In parallelizing simulated annealing in a multicomputer, maintaining the global state S involves explicit message traffic and is a critical performance bottleneck. One way to mitigate this bottleneck is to amortize the overhead of these state updates over as many parallel state changes as possible. Using this technique introduces errors in the calculated cost C(S) of a particular state S used by the annealing process. Analytically derived bounds are placed on this error in order to assure convergence to the correct result. The resulting parallel simulated annealing algorithm dynamically changes the frequency of global updates as a function of the annealing control parameter, i.e., temperature. Implementation results on the Intel iPSC/2 are reported
Recommended Citation
B. M. McMillin and C. Hong, "Parallel Error Tolerance Scheme Based on the Hill Climbing Nature of Simulated Annealing," Proceedings of the 35th Midwest Symposium on Circuits and Systems, 1992, Institute of Electrical and Electronics Engineers (IEEE), Jan 1992.
The definitive version is available at https://doi.org/10.1109/MWSCAS.1992.271230
Meeting Name
35th Midwest Symposium on Circuits and Systems, 1992
Department(s)
Computer Science
Keywords and Phrases
Intel IPSC/2; Adaptive Error Control Method; Convergence; Cost Error Measurement Scheme; Fault Tolerant Computing; Hill Climbing; Multicomputer; Parallel Algorithms; Parallel Error Tolerance Scheme; Simulated Annealing; State Updates
Document Type
Article - Conference proceedings
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1992 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
01 Jan 1992
