Speculative parallel simulated annealing with acceptance prediction
Kam‐Fai Wong, Anthony George Constantinides · IEE Proceedings - Computers and Digital Techniques · 1996
In the paper, a novel problem-independent parallel realisation of the simulated annealing (SA) algorithm is proposed. By employing speculative computation, concurrency is introduced into the inherently sequential algorithm. This is achieved by predicting the acceptance of each generated move before the move is evaluated. Based on this prediction, subsequent moves can be proposed and evaluated before decisions on whether to accept or reject preceeding moves are made. To preserve the sequential decision nature of SA, all moves subsequent to a prediction that is eventually proved wrong are discarded. A simple and effective prediction mechanism using previous move statistics is developed. Efficient realisation of the parallel SA algorithm on a ring multiprocessor architecture is described. Analytical and simulation performance results are presented. These results indicate that the authors' parallel SA is best implemented on a coarse to medium grain multiprocessor system. Factors affecting performance in actual implementations are also discussed.