Simulated annealing is known to be highly sequential due to loop-carried dependencies. This report presents a new approach to parallel simulated annealing, called generalized speculative computation (GSC). We use an n-ary speculative tree and loop indices to execute n iterations in parallel on n processors while maintaining the same decision sequence as sequential simulated annealing. To verify the performance of GSC, we implement 100- to 500-city Traveling Salesman Problems on the AP1000 massively parallel multiprocessor. Execution results demonstrate that the GSC approach can indeed be an effective method for simulated annealing. We obtain over 20-fold speedup for the initial temperature of 0.1 and 11-fold speedup for the initial temperature of 10, all on 100 processors.
|Original language||English (US)|
|Journal||Proceedings of the International Conference on Parallel Processing|
|State||Published - 1994|
|Event||23rd International Conference on Parallel Processing, ICPP 1994 - Raleigh, NC, United States|
Duration: Aug 15 1994 → Aug 19 1994
All Science Journal Classification (ASJC) codes
- Hardware and Architecture