A study of scheduling problems with preemptions on multi-core computers with GPU accelerators

Jacek Blazewicz, Safia Kedad-Sidhoum, Florence Monna, Grégory Mounié, Denis TrystramDiscret. Appl. Math 2015 · DOI

TL;DR

This paper tackles the complex challenge of scheduling tasks on modern hybrid CPU-GPU computing systems, focusing on how to leverage preemption on CPUs to improve performance. They introduce a new notation for these systems and propose algorithms that adapt classical scheduling techniques and develop novel approaches for problems with no direct classical counterparts.

What Problem Does This Paper Address?

Traditional scheduling problems often dealt with homogeneous systems (all CPUs or all GPUs). However, today's high-performance computing (HPC) systems are increasingly heterogeneous, featuring multi-core CPUs working alongside powerful GPU accelerators. This hybrid architecture presents new scheduling challenges, particularly in efficiently allocating and sequencing tasks across these diverse resources. A key difficulty is the differing capabilities of CPUs and GPUs, especially regarding preemption – the ability to interrupt a task and resume it later. While preemption is common and beneficial on CPUs, it's often difficult or impossible on GPUs due to their architecture. This paper aims to characterize these new scheduling problems, propose a formal notation for them, and develop algorithms that account for this heterogeneity and the specific constraints of preemption on CPUs.

Methods

The authors extend the classical Graham notation for scheduling problems to accommodate heterogeneous platforms with both uniform CPUs and GPUs. They introduce notation like (Pm, Pk) for identical CPUs and GPUs, and (Qm, Qk) for uniform CPUs and GPUs, where tasks have different processing times on each type of processor. A significant contribution is the formalization of "partial preemption" (ppmtn), where preemption is allowed only on CPUs, not between CPUs and GPUs or between GPUs.

The paper then analyzes various scheduling problems, categorizing them based on whether they have classical counterparts or are entirely new. For problems with classical parallels, they adapt existing algorithms. For novel problems, particularly those involving task-dependent speedups and partial preemption, they employ a dual approximation technique combined with binary search. This approach iteratively refines a guess for the optimal makespan by determining if a schedule of a certain length is feasible. For more complex scenarios, they also explore dynamic programming.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Heterogeneity is the new normal: Modern computing systems are fundamentally hybrid, and scheduling algorithms must adapt to this reality.
  • Partial preemption is key: Allowing preemption on CPUs while restricting it on GPUs is a realistic and potentially performance-boosting strategy for hybrid systems.
  • New notation is essential: The authors' extended notation provides a clear framework for describing and analyzing these complex scheduling problems.
  • Classical algorithms can be adapted, but new ones are needed: While some problems can be solved by modifying existing techniques, others require entirely new algorithmic approaches, such as dual approximation and dynamic programming.
  • GPU preemption is a future frontier: While this paper focuses on CPU preemption, the authors acknowledge that future GPU architectures might support more granular preemption, opening up new research avenues.

Key Results

The paper analyzes several scheduling problems, classifying them by hardness (polynomial or NP-hard) and providing algorithmic costs.

  • Polynomial Problems: Problems like (Pm, Pk) || ΣCj (minimizing mean flow time on identical CPUs and GPUs) are shown to be polynomial and solvable using adaptations of classical methods.
  • NP-hard Problems: Problems like (Pm, Pk) | qj = q | Cmax (minimizing makespan on identical CPUs and uniform GPUs with task-dependent speedups) are NP-hard, requiring approximation algorithms.
  • New Algorithms for Novel Problems: For problems with no direct classical counterparts, such as (Pm, Pk) | ppmtn | Cmax (minimizing makespan with partial preemption), they develop dual approximation algorithms with specific approximation ratios and time complexities (e.g., O(n log n) for the single GPU case).
  • Complexity Analysis: The paper systematically analyzes the complexity of various combinations of machine types (identical/uniform CPUs/GPUs), task characteristics (speedups), and preemption policies.

Limitations and Future Work

  • Preemption on GPUs: The paper assumes preemption is not allowed on GPUs. Future work could explore granular preemption on GPUs, where tasks can be interrupted after a certain processing time, as suggested by recent research.
  • Communication Costs: The current models largely ignore or simplify communication costs between CPUs and GPUs. Future research should incorporate more realistic models of communication delays and overlaps.
  • Task Dependencies: The paper primarily deals with independent tasks. Extending the models to handle task dependencies (precedence constraints) is a crucial area for future work.
  • Dynamic Environments: The algorithms presented are largely static. Adapting them to dynamic environments where tasks arrive or change characteristics over time would be valuable.
  • Hardware Evolution: The authors note that GPU architectures are evolving, and future work should consider these advancements, such as increased support for preemption.

Summary updated

BibTeX
@article{blazewicz2015study,
  author = {Jacek Blazewicz and Safia Kedad-Sidhoum and Florence Monna and Grégory Mounié and Denis Trystram},
  title = {{A study of scheduling problems with preemptions on multi-core computers with GPU accelerators}},
  journal = {Discret. Appl. Math.},
  year = {2015},
  doi = {10.1016/j.dam.2015.04.009},
}
Figure