J. Gmys, T. Carneiro, N. Melab, E-G. Talbi and D. Tuyttens. A comparative study of high-productivity high-performance programming languages for parallel metaheuristics. Swarm and Evolutionary Computation, Elsevier, Vol. 57, 100720, 2020.
This paper aims at providing a useful data point to help practitioners gauge the difficult question of whether to invest time and effort into learning and using a new programming language. To accomplish this objective, three productivity-aware languages (Chapel, Julia, and Python) are compared in terms of performance, scalability and productivity. To the best of our knowledge, this is the first time such a comparison is performed in the context of parallel metaheuristics. Besides providing a comparative study, we give feedback on the implementation and parallelization process in each language.
T. Carneiro, J. Gmys, N. Melab and D. Tuyttens. Towards ultra-scale Branch-and-Bound using a high-productivity language. Future Generation Computer Systems, Elsevier, 10.1016/j.future.2019.11.011, Vol. 105, pages 196-209, April 2020.
The aim is to increase the scalability of B&B algorithms for solving big optimization problems on future exascale supercomputers. The challenge is to revisit the design and implementation of these algorithms by considering a programming environment (Chapel, from HPE / Cray Inc.) favoring software productivity in addition to performance in order to take into account the complexity of modern supercomputers. This is pioneering in the context of parallel optimization. This article allowed us to initiate a collaboration (2-week stay in December 2019 of Tiago Carneiro at Cray Inc., Seattle) with HPE / Cray, a historical manufacturer of supercomputers.
J. Gmys, M. Mezmaz, N. Melab and D. Tuyttens. A computationally efficient Branch-and-Bound algorithm for the permutation Flow-shop scheduling problem. European Journal of Operational Research (EJOR), Elsevier, 284(3): pp. 814-833, 2020.
In this paper, we investigate the impact on performance of the combined use of 3 major components of B&B algorithms: the lower bound, branching and parallelism. Unlike the literature, we demonstrated that the impact of each component strongly depends on the choices concerning the other two ones. Two difficult instances of the permutation flow-shop (Taillard, 500 jobs on 20 machines) were solved to optimality for the first time (after 25 years). On the other hand, the best known solutions were improved for 89 other instances of the problem from another benchmark (VRF, 2015). This work also allowed us to optimally solve 5 other instances for the first time using 2 million GPU cores from the Jean-Zay supercomputer.
A. Bendjoudi, N. Melab, E-G. Talbi. FTH-B&B: a Fault Tolerant Hierarchical Branch and Bound for Large Scale Unreliable Environments. IEEE Transactions on Computers, Vol. 63(9), pp 2302-2315, 2014.
We propose FTH-B&B, an original fault tolerant hierarchical B&B. FTH-B&B is based on different new mechanisms enabling to efficiently build and maintain balanced the hierarchy, and to store and recover work units (subproblems). We experimented FTH-B&B on the Grid’5000 real French nation-wide computational grid using up to 1900 processor cores distributed over 6 sites. Achieving such scale considering a nation-wide 6-sites grid was uncommon in 2014. The reported results show that the overhead induced by the proposed mechanisms is very low and an efficiency close to 100% can be achieved on some Taillards benchmarks of the Flow-Shop problem.
T-V. Luong, N. Melab, E-G. Talbi. GPU Computing for Parallel Local Search Metaheuristic Algorithms. IEEE Transactions on Computers, Vol. 62(1), pages 173-185, 2013.
This is pioneering work in the design and implementation of parallel local search methods on GPUs. The merit of this article is to propose a unified methodology validated on several local search methods and various optimization problems. This methodology has been implemented in ParadisEO (ParadisEO-GPU) published in ACM GECCO’2013 (nominated for the Best Paper Award).