A problem independent parallel implementation of simulated annealing: models and experiments

Author

Roussel-Ragot, Pierre ; Dreyfus, Gérard

Author_Institution

Lab. d´´Electron., Ecole Superieure de Phys. et de Chimie Ind. de la Ville de Paris, France

Volume

9

Issue

8

fYear

1990

fDate

8/1/1990 12:00:00 AM

Firstpage

827

Lastpage

835

Abstract

The proposed implementation is guaranteed to exhibit the same convergence behavior as the serial algorithm. Two models of parallelization, depending on the value of the temperature, are introduced and statistical models which can predict the speedup for any problem (as a function of the acceptance rate and of the number of processors), are derived. The performances are evaluated on a simple placement problem with a transputer-based network, and the models are compared with experiments

Keywords

circuit layout CAD; parallel architectures; transputers; convergence behavior; experiments; models; parallelization; placement problem; problem independent parallel implementation; serial algorithm; simulated annealing; statistical models; transputer-based network; Computational modeling; Concurrent computing; Convergence; Cost function; Parallel processing; Performance evaluation; Processor scheduling; Simulated annealing; Temperature control; Temperature distribution;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.57790

Filename

57790