Heterogeneous cluster computing for many-task exact optimization - Application to permutation problems

Jan Gmys 1, 2, 3
3 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : Branch-and-Bound (B&B) is a frequently used tree-search exploratory method for the exact resolution of combinatorial optimization problems (COPs). However, in practice, only small problem instances can be solved on a sequential computer, as B&B generates often generates a huge amount of subproblems to be evaluated. In order to solve large COPs, we revisit the design and implementation of massively parallel B&B on top of large heterogeneous clusters, integrating multi-core CPUs, many-core processors and GPUs. For the efficient storage and management of subproblems an original data structure (IVM) dedicated to permutation problems is used. Because of the highly irregular and unpredictable shape of the B&B tree, dynamic load balancing between parallel exploration processes is one of the main issues addressed in this thesis. Based on a compact encoding of the search space in the form of intervals, work stealing strategies for multi-core and GPU are proposed, as well as hierarchical approaches for load balancing in distributed memory multi-CPU/multi-GPU systems. Three permutation problems, the Flowshop Scheduling Problem (FSP), the Quadratic Assignment Problem (QAP) and the n-Queens puzzle problem are used as test-cases. The resolution, in 9 hours, of a FSP instance with an estimated sequential execution time of 22 years demonstrates the scalability of the proposed algorithms on a cluster composed of 36 GPUs.
Complete list of metadatas

https://hal.inria.fr/tel-01652000
Contributor : Jan Gmys <>
Submitted on : Wednesday, November 29, 2017 - 6:09:18 PM
Last modification on : Friday, October 18, 2019 - 12:22:02 PM

File

Main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01652000, version 1

Collections

Citation

Jan Gmys. Heterogeneous cluster computing for many-task exact optimization - Application to permutation problems. Distributed, Parallel, and Cluster Computing [cs.DC]. Université de Mons (UMONS); Université de Lille, 2017. English. ⟨tel-01652000⟩

Share

Metrics

Record views

564

Files downloads

377