Branch-and-Bound interval global optimization on shared memory multiprocessors

L.G. Casado, J.A. Martinez, I. García, E.M.T. Hendrix

Research output: Contribution to journalArticleAcademicpeer-review

26 Citations (Scopus)

Abstract

The focus of this paper is on the analysis and evaluation of a type of parallel strategies applied to the algorithm Advanced Multidimensional Interval analysis Global Optimization (AMIGO). We investigate two parallel versions of AMIGO, called Parallel AMIGO (PAMIGO) algorithm, Global-PAMIGO and Local-PAMIGO. The idea behind our study is that in order to exploit the potential parallelism of algorithms, researchers need to adapt them to the target computer architectures. Our PAMIGO algorithms have been designed for shared memory architectures and are based on a threaded programming model, which is suitable to be run on current personal computers with multicore processors. Our first experimental results show a promising speed-up up to four process units. We analyse the loss of efficiency when the number of process units is greater than four by obtaining a profile of the algorithm executions. Secondly we experiment with the use of a local memory allocator per thread. This increases the efficiency by reducing the number of lock conflicts given by the standard system memory allocator. Our experimental results for both PAMIGO versions, using up to 15 process units, obtain a good performance for hard to solve problems on unicore and multicore processors. It is noteworthy that both versions of PAMIGO obtain a similar performance. Our experiments may be useful for researchers who use parallel B&B algorithms.
Original languageEnglish
Pages (from-to)689-701
JournalOptimization Methods and Software
Volume23
Issue number5
DOIs
Publication statusPublished - 2008

Keywords

  • parallelization

Fingerprint Dive into the research topics of 'Branch-and-Bound interval global optimization on shared memory multiprocessors'. Together they form a unique fingerprint.

  • Cite this