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

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.

Keywords:

• global optimization
• Branch-and-Bound
• interval arithmetic
• parallel algorithms
• shared memory
• multithreading

AMS Subject Classification :

• 90C30
• 65G20
• 68W10

Acknowledgements

This work has been partially supported by grants TIN2005-00447, RYC-2007-00287 (MEC), and P06-TIC-01426 (CICE, Junta de Andalucía).