Problem-independent parallel realisation of simulated annealing on a ring multiprocessor architecture based on speculative computation

In this 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 the prediction, subsequent moves can be proposed and evaluated before decisions on whether to accept or reject preceding 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 our parallel SA is best implemented on a coarse to medium grain multiprocessor system