TL;DR
This paper tackles the challenge of efficiently scheduling tasks on modern computing nodes that combine CPUs and multiple types of accelerators (like GPUs). They extend a previously successful scheduling strategy, HETEROPRIO, to handle more than two resource types, demonstrating significant performance improvements over standard methods for linear algebra operations.
What Problem Does This Paper Address?
Modern high-performance computing nodes are increasingly heterogeneous, featuring a mix of CPU cores and various accelerators such as GPUs. Effectively utilizing these diverse resources for complex computations like dense linear algebra operations is a major challenge. Existing scheduling strategies, like HEFT, often struggle with this heterogeneity, leading to suboptimal performance. Specifically, they can fail to leverage slower resources effectively, or they might not adapt well to platforms with more than two distinct resource types (e.g., multiple GPU architectures or clustered CPUs alongside GPUs). This paper aims to bridge this gap by proposing a generalized scheduling approach that can handle arbitrary numbers of heterogeneous resource types, including clustered CPUs.
Methods
The core of this paper is the generalization of the HETEROPRIO scheduling strategy. HETEROPRIO is a resource-centric dynamic scheduler that leverages "affinities" between tasks and resources. In its original form, it prioritized tasks for GPUs based on their acceleration ratio and for CPUs based on lower acceleration ratios.
The authors extend this by:
- Generalizing Scoring Systems: Instead of a simple acceleration ratio, they introduce two new scoring systems: "Area" and "Heterogeneity Index (Het.Index)". These systems provide a more nuanced way to quantify how well a task type suits a particular resource, allowing for more than two resource categories.
- Handling Multiple Resource Classes: The generalized HETEROPRIO can now manage platforms with individual CPUs, CPU groups of varying sizes, and multiple types of accelerators.
- CPU Clustering: The work explicitly considers the scenario where CPU cores are grouped together to form larger, more powerful processing units, which can improve resource utilization and reduce platform heterogeneity.
- Dynamic Adaptation: For actual execution, they incorporate mechanisms like work-stealing for CPU clusters and a merged queue for GPUs to dynamically adapt the static schedule generated by the simulation. They also introduce a small inflation of CPU execution times to account for communication overhead.
Datasets
Not discussed in the paper. The evaluation uses synthetic task graphs derived from standard linear algebra operations (Cholesky and QR factorization) and real-world execution traces.
Key Insights and Ideas
- Beyond Two Resource Types: The limitation of previous heterogeneous scheduling approaches to just two resource types (CPU/GPU) is a significant bottleneck for modern hardware. Generalizing HETEROPRIO unlocks better performance on more complex platforms.
- CPU Clustering is Key: Grouping CPU cores is not just about parallelism; it's a crucial technique to reduce platform heterogeneity and make scheduling strategies more effective, especially when dealing with accelerators.
- Het.Index vs. Area: The Het.Index scoring system appears to be more robust and stable across different configurations and matrix sizes compared to the Area score, suggesting it better captures the dynamic nature of task execution on heterogeneous systems.
- Dynamic Adaptation Matters: While simulation provides a good starting point, real-world execution requires dynamic adjustments (like work-stealing and communication overhead compensation) to achieve optimal performance.
- Task Graph Structure is Crucial: The performance of scheduling algorithms is highly dependent on the structure of the task graph and the matrix size. For very small matrices, critical path length can dominate, while for larger matrices, task parallelism and resource utilization become more important.
Key Results
- The generalized HETEROPRIO significantly outperforms the standard HEFT scheduling strategy across various configurations and matrix sizes for both Cholesky and QR factorization.
- In simulations, HETEROPRIO variants consistently achieve better performance than HEFT, especially in highly heterogeneous configurations.
- Actual execution results show that the adapted HETEROPRIO, with dynamic features and a 15% CPU execution time inflation, achieves substantial performance improvements over HEFT, particularly for smaller to medium-sized matrices. For example, for a 12x12 matrix,
heft-best(HEFT with clustering) showed a 58% increase overheft-wc(HEFT without clustering), andhp-best(HETEROPRIO) provided a 6% improvement overheft-best. - The Het.Index variant of HETEROPRIO demonstrated better overall stability and performance compared to the Area variant.
Limitations and Future Work
- Static Configuration: While the scheduling decisions are dynamic, the underlying platform configuration (CPU clustering) is determined statically before execution. The paper acknowledges that finding the optimal configuration is a complex problem.
- Simulation vs. Reality: The simulation neglects communication costs, which are then partially addressed by an empirical inflation of CPU execution times. A more integrated approach to communication handling would be beneficial.
- Future Work: The authors plan to develop a fully dynamic implementation of HETEROPRIO, eliminating the need for static schedule generation. They also aim to explore methods for automatically selecting optimal CPU cluster configurations and investigate how performance can be further improved by dynamically changing cluster configurations during execution.
Summary updated