UltraBO - Calcul ultra-scale pour la résolution de problèmes d’optimisation de grande taille

Coordinateur : Monsieur Nouredine Melab Université de Lille CRIStAL

Équipe : BONUS du Groupe Thématique : OPTIMA.

Dates : 11/22 - 08/26

Résumé :

Les supercalculateurs (Top500) sont de plus en plus larges (millions de cœurs), hétérogènes (CPU-GPU, …) et moins fiables (MTBF<1h) complexifiant leur programmation. Le développement d’algorithmes pour ces supercalculateurs n’est qu’à ses débuts en optimisation combinatoire (OC). L’objectif est d’investiguer les approches exascale MPI+X et PGAS pour la conception et l’implémentation d’algorithmes hybrides combinant méthodes exactes (e.g. B&B) et métaheuristiques (e.g. algorithmes évolutionnaires) pour la résolution de problèmes d’OC difficiles.
Nous adresserons de manière holistique (peu commune) trois défis sur la route de l’exascale : la scalabilité basée sur la localité, l’hétérogénéité CPU-GPU et la tolérance aux pannes via checkpointing.
Notre défi applicatif est de résoudre à l’optimalité des instances de benchmarks très difficiles (e.g. celles du Flowshop non résolues depuis 25 ans). Les supercalculateurs pétascale Jean Zay (France) et ULHPC (Luxembourg) seront utilisés pour l’expérimentation..

Abstract :

According to Top500 modern supercomputers are increasingly large (millions of cores), heterogeneous (CPU-GPU, …) and less reliable (MTBF<1h) making their programming more complex. The development of parallel algorithms for these ultra-scale supercomputers is in its infancy especially in combinatorial optimization. Our objective is to investigate the MPI+X and PGAS-based approaches for the exascale-aware design and implementation of hybrid algorithms combining exact methods (e.g. B&B) and metaheuristics (e.g. Evolutionary Algorithms) for solving challenging optimization problems.
We will address in a holistic way (uncommon) three roadblocks on the road to exascale : locality-aware ultra-scalability, CPU-GPU heterogeneity and checkpointing-based fault tolerance.
Our application challenge is to solve to optimality very hard benchmark instances (e.g. Flowshop ones unsolved since 25 years). The Jean Zay (France) and ULHPC (Luxembourg) petascale supercomputers will be used for experimentation.