Supervision : Safia KEDAD-SIDHOUM

Scheduling for new computing platforms with GPUs

More and more computers use hybrid architectures combining multi-core processors (CPUs) and hardware accelerators like GPUs (Graphics Processing Units). These hybrid parallel platforms require new scheduling strategies. This work is devoted to a characterization of this new type of scheduling problems. The most studied objective in this work is the minimization of the makespan, which is a crucial problem for reaching the potential of new platforms in High Performance Computing. The core problem studied in this work is scheduling efficiently n independent sequential tasks with m CPUs and k GPUs, where each task of the application can be processed either on a CPU or on a GPU, with minimum makespan. This problem is NP-hard, therefore we propose approximation algorithms with performance ratios ranging from 2 to (2q+1)/(2q)+1/(2qk), q>0, and corresponding polynomial time complexities. The proposed solving method is the first general purpose algorithm for scheduling on hybrid machines with a theoretical performance guarantee that can be used for practical purposes. Some variants of the core problem are studied: a special case where all the tasks are accelerated when assigned to a GPU, with a 3/2-approximation algorithm, a case where preemptions are allowed on CPUs, the same problem with malleable tasks, with an algorithm with a ratio of 3/2. Finally, we studied the problem with dependent tasks, providing a 6-approximation algorithm. Experiments based on realistic benchmarks have been conducted. Some algorithms have been integrated into the scheduler of the xKaapi runtime system for linear algebra kernels, and compared to the state-of-the-art algorithm HEFT.

2013-2018 Publications

• 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”, thesis, phd defence 11/25/2014, supervision 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)