Parallel N-ary speculative computation of simulated annealing
- 1 January 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 6 (10) , 997-1005
- https://doi.org/10.1109/71.473510
Abstract
Simulated annealing is known to be an efficient method for combinatorial optimization problems. Its usage for realistic problem size, however, has been limited by the long execution time due to its sequential nature. This report presents a practical approach to synchronous simulated annealing for massively parallel distributed-memory multiprocessors. We use an n-ary speculative tree to execute n different iterations in parallel on n processors, called Generalized Speculative Computation (GSC). Execution results of the 100- to 500-city Traveling Salesman Problems on the AP1000 massively parallel multiprocessor demonstrate that the GSC approach can be an effective method for parallel simulated annealing as it gave over 20-fold speedup on 100 processors.Keywords
This publication has 12 references indexed in Scilit:
- Improving AP1000 Parallel Computer Performance With Message CommunicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Low-latency message communication support for the AP1000Published by Association for Computing Machinery (ACM) ,1992
- Parallel simulated annealing using speculative computationIEEE Transactions on Parallel and Distributed Systems, 1991
- Parallel simulated annealing techniquesPhysica D: Nonlinear Phenomena, 1990
- Parallel simulated annealing algorithms for cell placement on hypercube multiprocessorsIEEE Transactions on Parallel and Distributed Systems, 1990
- A distributed implementation of simulated annealing for the travelling salesman problemParallel Computing, 1989
- Parallel standard cell placement algorithms with quality equivalent to simulated annealingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1988
- A Parallel Simulated Annealing Algorithm for the Placement of Macro-CellsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Placement by Simulated Annealing on a MultiprocessorIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Optimization by Simulated AnnealingScience, 1983