1º WCloud-HPC (Online)

Abstract: HPC has made great steps and its potential is continuously impacting. The next exciting horizon is the Exascale milestone. In this perspective, it is worth investigating how challenging applications like those coming from combinatorial optimization will benefit from this significant computing power available on supercomputers. The reference branch-and-bound technique for instance needs a special focus at a macroscopic level. Then, as its main ingredient at a node level is how we solve the kernel problem, an efficient shared memory parallelization is worth considering. Multicore has emerged as a typical architecture model since its advent, and it now stands as a standard. The trend is to increase the number of cores and improve memory system performance. Providing an efficient multicore implementation for an important algorithmic kernel is a genuine contribution. From a methodology standpoint, this should be done at the level of the underlying paradigm if any. We study the cases of dynamic programming and greedy algorithms, which are two major combinatorial algorithmic paradigms. We exclusively consider directives-based loop parallelization through OpenMP and investigate necessary transformations to reach a regular parallel form. We evaluate our methodology with a selection of well-known combinatorial optimization problems on an INTEL Broadwell processor. Key points for scalability are discussed before and after experimental results, the NUMA case being our next focus.