Modern high-performance computing (HPC) has shifted toward heterogeneous architectures, where traditional multi-core CPUs are paired with specialized accelerators like GPUs. While these hybrid platforms offer immense computational power, they introduce significant complexity in task management. This paper addresses the fundamental challenge of scheduling tasks with precedence constraints on such platforms, specifically focusing on narrowing the "approximability window"—the gap between the best known algorithm and the theoretical limit of what can be achieved.
The Scheduling Challenge
The paper focuses on the $(Pm, Pk) | prec | C_{max}$ problem. In this model, we have $m$ identical CPUs and $k$ identical GPUs. The goal is to minimize the makespan ($C_{max}$), which is the total time required to complete a set of tasks given two primary constraints:
- Heterogeneity: Tasks exhibit different processing times depending on the resource type. A task might be highly optimized for a GPU but run significantly slower on a CPU, or vice versa.
- Precedence Constraints: Tasks often have dependencies, forming a Directed Acyclic Graph (DAG) where certain tasks cannot begin until their predecessors have finished.
Prior to this work, the best-known polynomial-time algorithm provided a 6-approximation (meaning the result was at most 6 times the optimal makespan), while the known lower bound was 2. This left a wide gap in our understanding of how efficiently these systems can be scheduled.
The HLP-$b$ Algorithm
The authors propose a new two-phase algorithm called Heterogeneous Linear Program with parameter $b$ (HLP-$b$). This approach decouples the resource assignment from the actual timing of the tasks.
Phase 1: Allocation via LP Rounding
The algorithm first determines whether each task should be assigned to a CPU or a GPU. This is modeled as an Integer Linear Program (ILP) that seeks to balance the average load on the processors against the length of the critical path (the longest chain of dependent tasks). Since solving an ILP is NP-hard, the authors solve a fractional Linear Programming (LP) relaxation.
The innovation lies in the rounding procedure. Instead of using a static threshold, the authors introduce a flexible parameter $b$ that is tuned based on the ratio of CPUs to GPUs ($m/k$). When the LP is "ambiguous" about a task's placement, the algorithm intelligently assigns it to the processor type where it performs most efficiently, mitigating the impact of the rounding on the final schedule.
Phase 2: List Scheduling
Once tasks are assigned to a specific resource type, the algorithm employs a standard List Scheduling strategy. Tasks are executed as soon as their predecessors are complete and a processor of the assigned type becomes available.
Narrowing the Approximability Window
The paper provides two major theoretical contributions that redefine the bounds of this problem:
1. A New Upper Bound
The authors prove that the HLP-$b$ algorithm achieves an approximation ratio of $3 + 2\sqrt{2} \approx 5.83$. While this is a numerical improvement over the previous ratio of 6, the result is more significant because the ratio is dynamic. The performance is defined by the formula:
$$3 + 4\sqrt{\frac{1-k/m}{2-k/m}}$$
As the number of CPUs and GPUs becomes more balanced ($m/k$ approaches 1), the approximation ratio improves, eventually approaching 3.
2. A New Lower Bound
Perhaps the most impactful contribution is the establishment of a new conditional lower bound. By using a reduction from the "$q$-partite problem" (a complex graph theory problem), the authors prove that no polynomial-time algorithm can achieve an approximation ratio better than 3, assuming certain complexity theory conjectures (a variant of the Unique Games Conjecture) hold.
This result effectively "raises the floor" of the problem. It demonstrates that the previous goal of reaching a 2-approximation was likely impossible, and that 3 is the true theoretical target for researchers.
Significance and Future Work
By improving the upper bound to 5.83 and raising the lower bound to 3, the authors have significantly narrowed the approximability window for hybrid scheduling. The discovery that the bounds meet at 3 when $m=k$ suggests that the HLP-$b$ approach is near-optimal for balanced systems.
However, a gap remains for highly unbalanced systems where $m \gg k$. Future research will likely focus on refining allocation strategies to close this remaining window, potentially through even more sophisticated rounding techniques or by exploring whether the lower bound can be further tightened for specific processor ratios.
Summary updated