IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v57y2013i3p863-890.html
   My bibliography  Save this article

An efficient implementation of parallel simulated annealing algorithm in GPUs

Author

Listed:
  • A. Ferreiro
  • J. García
  • J. López-Salas
  • C. Vázquez

Abstract

In this work we propose a highly optimized version of a simulated annealing (SA) algorithm adapted to the more recently developed graphic processor units (GPUs). The programming has been carried out with compute unified device architecture (CUDA) toolkit, specially designed for Nvidia GPUs. For this purpose, efficient versions of SA have been first analyzed and adapted to GPUs. Thus, an appropriate sequential SA algorithm has been developed as starting point. Next, a straightforward asynchronous parallel version has been implemented and then a specific and more efficient synchronous version has been developed. A wide appropriate benchmark to illustrate the performance properties of the implementation has been considered. Among all tests, a classical sample problem provided by the minimization of the normalized Schwefel function has been selected to compare the behavior of the sequential, asynchronous and synchronous versions, the last one being more advantageous in terms of balance between convergence, accuracy and computational cost. Also the implementation of a hybrid method combining SA with a local minimizer method has been developed. Note that the generic feature of the SA algorithm allows its application in a wide set of real problems arising in a large variety of fields, such as biology, physics, engineering, finance and industrial processes. Copyright Springer Science+Business Media, LLC. 2013

Suggested Citation

  • A. Ferreiro & J. García & J. López-Salas & C. Vázquez, 2013. "An efficient implementation of parallel simulated annealing algorithm in GPUs," Journal of Global Optimization, Springer, vol. 57(3), pages 863-890, November.
    • Handle: RePEc:spr:jglopt:v:57:y:2013:i:3:p:863-890
    DOI: 10.1007/s10898-012-9979-z
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10898-012-9979-z
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10898-012-9979-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ana Maria Ferreiro-Ferreiro & José Antonio García-Rodríguez & Luis A. Souto & Carlos Vázquez, 2020. "Efficient Model Points Selection in Insurance by Parallel Global Optimization Using Multi CPU and Multi GPU," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 62(1), pages 5-20, February.
    2. Konstantin Barkalov & Victor Gergel, 2016. "Parallel global optimization on GPU," Journal of Global Optimization, Springer, vol. 66(1), pages 3-20, September.
    3. Ferreiro-Ferreiro, Ana María & García-Rodríguez, José A. & Souto, Luis & Vázquez, Carlos, 2020. "A new calibration of the Heston Stochastic Local Volatility Model and its parallel implementation on GPUs," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 177(C), pages 467-486.
    4. Ana M. Ferreiro & Enrico Ferri & José A. García & Carlos Vázquez, 2021. "Global Optimization for Automatic Model Points Selection in Life Insurance Portfolios," Mathematics, MDPI, vol. 9(5), pages 1-19, February.
    5. Jinlong Yuan & Lei Wang & Xu Zhang & Enmin Feng & Hongchao Yin & Zhilong Xiu, 2015. "Parameter identification for a nonlinear enzyme-catalytic dynamic system with time-delays," Journal of Global Optimization, Springer, vol. 62(4), pages 791-810, August.
    6. Chandra Ade Irawan & Said Salhi & Kusmaningrum Soemadi, 2020. "The continuous single-source capacitated multi-facility Weber problem with setup costs: formulation and solution methods," Journal of Global Optimization, Springer, vol. 78(2), pages 271-294, October.
    7. Ferreiro-Ferreiro, Ana M. & García-Rodríguez, José A. & Souto, Luis & Vázquez, Carlos, 2019. "Basin Hopping with synched multi L-BFGS local searches. Parallel implementation in multi-CPU and GPUs," Applied Mathematics and Computation, Elsevier, vol. 356(C), pages 282-298.
    8. A. M. Ferreiro & J. A. Garc'ia & J. G. L'opez-Salas & C. V'azquez, 2024. "SABR/LIBOR market models: pricing and calibration for some interest rate derivatives," Papers 2408.01470, arXiv.org.
    9. Ferreiro, Ana M. & García-Rodríguez, José Antonio & Vázquez, Carlos & e Silva, E. Costa & Correia, A., 2019. "Parallel two-phase methods for global optimization on GPU," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 156(C), pages 67-90.
    10. Yue Sun & Alfredo Garcia, 2017. "Interactive model-based search with reactive resource allocation," Journal of Global Optimization, Springer, vol. 67(1), pages 135-149, January.
    11. Schryen, Guido, 2020. "Parallel computational optimization in operations research: A new integrative framework, literature review and research directions," European Journal of Operational Research, Elsevier, vol. 287(1), pages 1-18.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:57:y:2013:i:3:p:863-890. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.