A PROBLEM INDEPENDENT PARALLEL IMPLEMENTATION OF SIMULATED ANNEALING - MODELS AND EXPERIMENTS

被引：23

作者：

ROUSSELRAGOT, P ^{[1
]}

DREYFUS, G ^{[1
]}

机构：

[1] ECOLE SUPER PHYS & CHIM IND,ELECTR RES DEPT,F-75005 PARIS,FRANCE

来源：

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 1990年 / 9卷 / 08期

关键词：

D O I：

10.1109/43.57790

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We suggest a problem independent parallel implementation of the simulated annealing algorithm which is guaranteed to exhibit the same convergence behavior as the serial algorithm. We introduce two modes of parallelization, depending on the value of the temperature, and we derive statistical models which can predict the speedup for any problem, as a function of the acceptance rate and of the number of processors. The performances are evaluated on a simple placement problem with a transputer-based network, and the models are compared with experiments. © 1990 IEEE

引用

页码：827 / 835

页数：9

共 14 条

[1] AARTS EHL, 1985, PHILIPS J RES, V40, P193
[2] PARALLEL IMPLEMENTATIONS OF THE STATISTICAL COOLING ALGORITHM
AARTS, EHL
DEBONT, FMJ
HABERS, EHA
VANLAARHOVEN, PJM
[J]. INTEGRATION-THE VLSI JOURNAL, 1986, 4 (03) : 209 - 238
[3] Brouwer R. J., 1988, Proceedings of the 1988 IEEE International Conference on Computer Design: VLSI in Computers and Processors - ICCD '88 (Cat. No.88CH2643-5), P4, DOI 10.1109/ICCD.1988.25647
[4] A PARALLEL SIMULATED ANNEALING ALGORITHM FOR THE PLACEMENT OF MACROCELLS
CASOTTO, A
ROMEO, F
SANGIOVANNIVINCENTELLI, A
[J]. IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1987, 6 (05) : 838 - 847
[5] CASOTTO A, 1987, P INT C COMP AID DES, P350
[6] CATONI O, IN PRESS SIMULATED A
[7] PARALLEL ALGORITHMS FOR CHIP PLACEMENT BY SIMULATED ANNEALING
DAREMA, F
KIRKPATRICK, S
NORTON, VA
[J]. IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1987, 31 (03) : 391 - 402
[8] GEMAN S, 1984, IEEE P PATTERN ANAL, P722
[9] OPTIMIZATION BY SIMULATED ANNEALING
KIRKPATRICK, S
GELATT, CD
VECCHI, MP
[J]. SCIENCE, 1983, 220 (4598) : 671 - 680
[10] KRAVITZ S, 1986, 23TH P IEEE DES AUT

← 1 2 →