Direction de recherche : Safia KEDAD-SIDHOUM

Ordonnancement pour les nouvelles plateformes de calcul avec GPUs

De plus en plus d'ordinateurs utilisent des architectures hybrides combinant des processeurs multi-coeurs (CPUs) et des accélérateurs matériels comme les GPUs (Graphics Processing Units). Ces plates-formes parallèles hybrides exigent de nouvelles stratégies d'ordonnancement adaptées. Cette thèse est consacrée à une caractérisation de ce nouveau type de problèmes d'ordonnancement. L'objectif le plus étudié dans ce travail est la minimisation du makespan, qui est un problème crucial pour atteindre le potentiel des nouvelles plates-formes en Calcul Haute Performance. Le problème central étudié dans ce travail est le problème d'ordonnancement efficace de n tâches séquentielles indépendantes sur une plateforme de m CPUs et k GPUs, où chaque tâche peut être exécutée soit sur un CPU ou sur un GPU, avec un makespan minimal. Ce problème est NP-difficiles, nous proposons donc des algorithmes d'approximation avec des garanties de performance allant de 2 à (2q + 1)/(2q) +1/(2qk), q> 0, et des complexités polynomiales. Il s'agit des premiers algorithmes génériques pour la planification sur des machines hybrides avec une garantie de performance et une fin pratique. Des variantes du problème central ont été étudiées : un cas particulier où toutes les tâches sont accélérées quand elles sont affectées à un GPU, avec un algorithme avec un ratio de 3/2, un cas où les préemptions sont autorisées sur CPU, mais pas sur GPU, le modèle des tâches malléables, avec un algorithme avec un ratio de 3/2. Enfin, le problème avec des tâches dépendantes a été étudié, avec un algorithme avec un ratio de 6. Certains des algorithmes ont été intégré dans l'ordonnanceur du système xKaapi.

Publications 2013-2018

• 2018
  • S. Kedad‑Sidhoum, F. Monna, G. Mounié, D. Trystram : “A Family of Scheduling Algorithms for Hybrid Parallel Platforms”, International Journal of Foundations of Computer Science, vol. 29 (1), pp. 63-90, (World Scientific Publishing) (2018)
• 2017
  • R. Bleuse, S. Hunold, S. Kedad‑Sidhoum, F. Monna, G. Mounié, D. Trystram : “Scheduling Independent Moldable Tasks on Multi-Cores with GPUs”, IEEE Transactions on Parallel and Distributed Systems, pp. 14, (Institute of Electrical and Electronics Engineers) (2017)
• 2016
  • R. Bleuse, S. Hunold, S. Kedad‑Sidhoum, F. Monna, G. Mounié, D. Trystram : “Scheduling Independent Moldable Tasks on Multi-Cores with GPUs”, (2016)
• 2015
  • J. Błażewicz, S. Kedad‑Sidhoum, F. Monna, G. Mounié, D. Trystram : “A study of scheduling problems with preemptions on multi-core computers with GPU accelerators”, Discrete Applied Mathematics, vol. 196, pp. 72-82, (Elsevier) (2015)
  • R. Bleuse, S. Kedad‑Sidhoum, F. Monna, G. Mounié, D. Trystram : “Scheduling independent tasks on multi-cores with GPU accelerators”, Concurrency and Computation: Practice and Experience, vol. 27 (6), pp. 1625-1638, (Wiley) (2015)
  • S. Kedad‑Sidhoum, F. Monna, D. Trystram : “Scheduling Tasks with Precedence Constraints on Hybrid Multi-core Machines”, IPDPSW 2015 - IEEE International Parallel and Distributed Processing Symposium Workshop, Hyderabad, India, pp. 27-33 (2015)
• 2014
  • F. Monna : “Ordonnancement pour les nouvelles plateformes de calcul avec GPUs”, thèse, soutenance 25/11/2014, direction de recherche Kedad-sidhoum, Safia (2014)
  • S. Kedad‑Sidhoum, F. Mendonca, F. Monna, G. Mounié, D. Trystram : “Fast Biological Sequence Comparison on Hybrid Platforms”, 43^rd International Conference on Parallel Processing, ICPP 2014, Minneapolis, United States, pp. 501-509 (2014)
  • S. Kedad‑Sidhoum, F. Monna, G. Mounié, D. Trystram : “Scheduling Independent Tasks on Multi-cores with GPU Accelerators”, Euro-Par 2013: Parallel Processing Workshops, vol. 8374, Lecture Notes in Computer Science, Aachen, Germany, pp. 228-237, (Springer) (2014)
• 2013
  • S. Kedad‑Sidhoum, F. Monna, G. Mounié, D. Trystram : “Approximation Algorithms for a Scheduling Problem on Multi-Cores with GPUs”, 11^th workshop on Models and Algorithms for Planning and Scheduling Problems MAPSP, Pont-à-Mousson, France (2013)
  • J. Blazewicz, S. Kedad‑Sidhoum, F. Monna, G. Mounié, D. Trystram : “Preemptive scheduling of independent tasks on multi-cores with GPU”, ECCO XXVI: the 26^th European Chapter on Combinatorial Optimization, Paris, France (2013)