SPECULATIVE PARALLEL SIMULATED ANNEALING WITH ACCEPTANCE PREDICTION

In the paper, a novel problem-independent parallel realisation of the simulated annealing (SA) algorithm is proposed. By employing speculati ve computation, concurrency is introduced into the inherently sequenti al algorithm. This is achieved by predicting the acceptance of each ge nerated move before the move is evaluated. Based on this prediction, s ubsequent moves can be proposed and evaluated before decisions on whet her to accept or reject preceeding moves are made. To preserve the seq uential decision nature of SA, all moves subsequent to a prediction th at is eventually proved wrong are discarded. A simple and effective pr ediction mechanism using previous move statistics is developed. Effici ent realisation of the parallel SA algorithm on a ring multiprocessor architecture is described. Analytical and simulation performance resul ts 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 dis cussed.