Parallel simulated annealing using speculative computation
- 1 January 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 2 (4) , 483-494
- https://doi.org/10.1109/71.97904
Abstract
A parallel simulated annealing algorithm that is problem-independent, maintains the serial decision sequence, and obtains speedup which can exceed log/sub 2/P on P processors is discussed. The algorithm achieves parallelism by using the concurrency technique of speculative computation. Implementation of the parallel algorithm on a hypercube multiprocessor and application to a task assignment problem are described. The simulated annealing solutions are shown to be, on average, 28% better than the solutions produced by a random task assignment algorithm and 2% better than the solutions produced by a heuristic.Keywords
This publication has 11 references indexed in Scilit:
- Error tolerance in parallel simulated annealing techniquesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A Parallel Simulated Annealing Algorithm for the Placement of Macro-CellsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Parallel implementations of the statistical cooling algorithmIntegration, 1986
- Convergence and finite-time behavior of simulated annealingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Speculative computation, parallelism, and functional programmingIEEE Transactions on Computers, 1985
- The TimberWolf placement and routing packageIEEE Journal of Solid-State Circuits, 1985
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of ImagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- Optimization by Simulated AnnealingScience, 1983
- Parallel interpretation of logic programsPublished by Association for Computing Machinery (ACM) ,1981
- NP-complete scheduling problemsJournal of Computer and System Sciences, 1975