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

Meeting Name

35th Midwest Symposium on Circuits and Systems, 1992


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





© 1992 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Jan 1992