http://iet.metastore.ingenta.com
1887

Speculative parallel simulated annealing with acceptance prediction

Speculative parallel simulated annealing with acceptance prediction

For access to this article, please select a purchase option:

Buy article PDF
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings - Computers and Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

In the paper, a novel problem-independent parallel realisation of the simulated annealing (SA) algorithm is proposed. By employing speculative computation, concurrency is introduced into the inherently sequential algorithm. This is achieved by predicting the acceptance of each generated move before the move is evaluated. Based on this prediction, subsequent moves can be proposed and evaluated before decisions on whether to accept or reject preceeding moves are made. To preserve the sequential decision nature of SA, all moves subsequent to a prediction that is eventually proved wrong are discarded. A simple and effective prediction mechanism using previous move statistics is developed. Efficient realisation of the parallel SA algorithm on a ring multiprocessor architecture is described. Analytical and simulation performance results are presented. These results indicate that the authors' parallel SA is best implemented on a coarse to medium grain multiprocessor system. Factors affecting performance in actual implementations are also discussed.

References

    1. 1)
      • S. Kirkpatrick , C.D. Gelatt , M.P. Vecchi . Optimization by simulated annealing. Science , 4598 , 671 - 680
    2. 2)
      • R.H.J.M. Otten , L.P.P.P. van Ginneken . (1989) The annealing algorithm.
    3. 3)
      • D. Greening . Parallel simulated annealing techniques. Physica D: Nonlinear Phenomena , 293 - 306
    4. 4)
      • Greening, D.: `Simulated annealing with errors', 1995, PhD thesis, UCLA.
    5. 5)
      • D. Abramson . A very high speed architecture for simulated annealing. IEEE Comput. , 5 , 27 - 36
    6. 6)
      • Rutenbar, R., Kravitz, S.: `Layout by annealing in a parallel environment', Proc. IEEE Int. Conf. Computer Design, 1986, p. 434–437.
    7. 7)
      • E. Aarts , F. de Bont , J. Habers , P. van Laarhoven . Parallel implementationsof the statistical cooling algorithm. Integration , 209 - 238
    8. 8)
      • P. Roussel-Ragot , G. Dreyfus . A problem independent parallel implementationof simulated annealing: Models and experiments. IEEE Trans. Comput.-Aided Des. , 8 , 827 - 835
    9. 9)
      • Y. Kim , M. Kim . A step-wise-overlapped parallel annealing algorithm on amessage-passing multiprocessor system. Concurrency, Prac. Exp. , 2 , 123 - 148
    10. 10)
      • K. Wong , Y. Wong . Short-term hydrothermal scheduling, part 2: Parallelsimulated annealing approach. IEE Proc., Gener., Transm. Distrib. , 5 , 502 - 506
    11. 11)
      • Sohn, A.: `Parallel speculative computation of simulated annealing', Proc. IEEE Int. Conf. Parallel Processing, 1994, 3, p. 8–11.
    12. 12)
      • F. Witte , R. Chamberlain , M. Franklin . Parallel simulated annealing usingspeculative computation. IEEE Trans. Parallel and Distrib. Syst. , 4 , 483 - 494
    13. 13)
      • M. Marchesi , G. Molinari , M. Repetto . A parallel simulated annealingalgorithm for the design of magnetic structures. IEEE Trans. Magn. , 5 , 3439 - 3442
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-cdt_19960469
Loading

Related content

content/journals/10.1049/ip-cdt_19960469
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address