Simulated annealing is known to be highly sequential due to dependences between iterations. While the conventional speculative computation with a binary tree has been found effective for parallel simulated annealing, its performance is limited to (logp)-fold speedup due to parallel execution of logp iterations on p processors. This report presents a new approach to parallel simulated annealing, called generalized speculative computation (GSC). The GSC is synchronous, maintaining the same decision sequence as sequential simulated annealing. The use of two loop indices encoded in a single integer eliminates broadcasting of central data structure to all processors. The master-slave parallel programming paradigm simplifies controlling the activities of p iterations which are executed in parallel on p processors. To verify the performance of GSC, the paper implemented 100-city to 500-city Traveling Salesman Problems on the AP1000 massively parallel multiprocessor. Execution results on the AP1000 demonstrate that the GSC approach can indeed be an effective method for parallel simulated annealing as it gave over 20-fold speedup on 100 processors.
