Abstract
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). While the conventional binary speculative computation can execute a maximum of (log n) iterations in parallel on n processors, the GSC can execute n iterations in parallel while maintaining the same decision sequence as a sequential version. To demonstrate the performance of GSC, we implement 100 to 500 city Traveling Salesman Problem on the AP1000 massively parallel machine. Actual experimental results demonstrate that the GSC is highly effective for the given problem as we obtain a nearly 20-fold speedup for the initial temperature of 1 on 100 processors.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing |
| Editors | Anon |
| Publisher | Publ by IEEE |
| Pages | 416-419 |
| Number of pages | 4 |
| ISBN (Print) | 081864222X |
| State | Published - Dec 1 1993 |
| Event | Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing - Dallas, TX, USA Duration: Dec 1 1993 → Dec 4 1993 |
Other
| Other | Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing |
|---|---|
| City | Dallas, TX, USA |
| Period | 12/1/93 → 12/4/93 |
All Science Journal Classification (ASJC) codes
- Engineering(all)