Scheduling on Hybrid Platforms: Improved Approximability Window

Vincent Fagnon, Imed Kacem, Giorgio Lucarelli, Bertrand Simon

This paper, titled "Scheduling on Hybrid Platforms: Improved Approximability Window," tackles a fundamental challenge in modern high-performance computing: how to efficiently manage tasks across systems that mix traditional CPUs with specialized accelerators like GPUs.

TL;DR

The authors narrow the "approximability window" for scheduling tasks with precedence constraints on hybrid CPU/GPU platforms. They introduce a new algorithm with a $5.83$ approximation ratio (improving on the previous $6$) and prove a new conditional lower bound of $3$, showing that no polynomial-time algorithm can do better than a factor of 3 under certain complexity assumptions.

What Problem Does This Paper Address?

In modern computing, we rarely use just one type of processor. Hybrid platforms—combining many CPUs with several GPUs—are the standard for heavy workloads like matrix operations or file system management. However, scheduling on these platforms is notoriously difficult.

The challenge is twofold:

  1. Heterogeneity: A task might run 10x faster on a GPU than a CPU, while another might actually be slower on a GPU due to communication overhead.
  2. Precedence Constraints: Tasks often depend on one another (e.g., Task B cannot start until Task A finishes).

The goal is to minimize the makespan ($C_{max}$), which is the total time elapsed from the start of the first task to the completion of the last. Mathematically, this is the $(Pm, Pk) | prec | C_{max}$ problem. Prior to this paper, the best-known algorithm guaranteed a solution within a factor of 6 of the optimum, while the known lower bound was only 2.

Methods

The authors propose a two-phase algorithm called HLP-$b$ (Heterogeneous Linear Program with parameter $b$):

  1. The Allocation Phase: The algorithm first decides whether each task should run on a CPU or a GPU. It uses an Integer Linear Program (ILP) that balances the average load on processors against the "critical path" (the longest chain of dependent tasks). Because solving an ILP is NP-hard, they solve a fractional relaxation (an LP) and then apply a novel rounding procedure.
  2. The $b$ Parameter: Unlike previous approaches that used a fixed rounding threshold (like 0.5), this paper introduces a flexible parameter $b$ that depends on the ratio of CPUs ($m$) to GPUs ($k$).
  3. Smart Rounding: If the LP is "unsure" about a task, the algorithm assigns it to the processor type where it runs fastest.
  4. The Scheduling Phase: Once every task is assigned to a resource type, the algorithm uses a standard List Scheduling approach, executing tasks as soon as their predecessors are finished and a processor of the assigned type is free.

To establish the Lower Bound, the authors use a reduction from the "$q$-partite problem," a complex graph theory problem, to show that achieving an approximation ratio better than 3 is likely impossible for polynomial-time algorithms.

Datasets

As a theoretical computer science paper, this work does not use empirical datasets or benchmarks. Instead, it relies on mathematical proofs and worst-case complexity analysis to validate the algorithm's performance across all possible valid task graphs and processing time distributions.

Key Insights and Ideas

  • The "Middle Ground" Strategy: The core "aha moment" is that the rounding rule for the allocation phase doesn't need to be optimal for the allocation sub-problem to be optimal for the entire scheduling problem. By choosing a rounding rule that specifically favors the faster processor type when the LP is ambiguous, they provide much stronger guarantees for the subsequent scheduling phase.
  • Closing the Gap: The authors noticed that the approximation ratio actually improves as the number of CPUs and GPUs becomes more balanced. When $m = k$, their algorithm's performance approaches their newly proven lower bound of 3.
  • The Power of 3: By proving a lower bound of 3, the authors significantly raised the floor of the problem. Previously, researchers were aiming for a ratio of 2; this paper shows that 3 is the more realistic "holy grail" for this specific hybrid problem.

Key Results

  • New Upper Bound: The HLP-$b$ algorithm achieves an approximation ratio of $3 + 2\sqrt{2} \approx 5.83$.
  • Dynamic Ratio: The ratio is defined by the formula $3 + 4\sqrt{\frac{1-k/m}{2-k/m}}$. As the ratio of CPUs to GPUs ($m/k$) approaches 1, the approximation ratio approaches 3.
  • New Lower Bound: The authors proved a conditional lower bound of 3. This means that unless certain widely-held complexity theory conjectures (specifically a variant of the Unique Games Conjecture) are false, no algorithm can ever guaranteed a ratio better than 3.

Limitations and Future Work

The primary limitation is the remaining gap between the lower bound (3) and the upper bound (5.83) when the number of CPUs and GPUs is significantly different ($m \gg k$). While the bounds meet when $m=k$, the "approximability window" is still open for highly unbalanced systems.

The authors suggest that future work should focus on closing this gap for all values of $m$ and $k$, potentially by finding even more sophisticated allocation strategies or further refining the lower bound proofs.

Summary updated

BibTeX
@inproceedings{fagnon2020scheduling,
  author = {Vincent Fagnon and Imed Kacem and Giorgio Lucarelli and Bertrand Simon},
  title = {{Scheduling on Hybrid Platforms: Improved Approximability Window}},
  booktitle = {LATIN},
  year = {2020},
  doi = {10.1007/978-3-030-61792-9\_4},
}
Figure