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
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 http://dx.doi.org/10.1109/MWSCAS.1992.271230
35th Midwest Symposium on Circuits and Systems, 1992
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
Article - Conference proceedings
© 1992 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.