Speculative parallel simulated annealing with acceptance prediction

Access Full Text

Speculative parallel simulated annealing with acceptance prediction

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

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

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.

© IEE
Published

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.

Inspec keywords: parallel algorithms; multiprocessing systems; simulated annealing; performance evaluation

Other keywords: concurrency; speculative parallel simulated annealing; sequential decision; inherently sequential algorithm; ring multiprocessor architecture; grain multiprocessor; problem-independent parallel realisation; simulation performance; acceptance prediction

Subjects: Parallel programming and algorithm theory; Optimisation techniques; Multiprocessing systems; Performance evaluation and testing

References

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