Abstract
As modern HPC computing platforms become increasingly heterogeneous, it is challenging for programmers to fully leverage the computation power of massive parallelism offered by such heterogeneity. Consequently, task-based runtime systems have been proposed as an intermediate layer to hide the complex heterogeneity from the application programmers. The core functionality of these systems is to realize efficient task-to-resource mapping in the form of Directed Acyclic Graph (DAG) scheduling. However, existing scheduling schemes face several drawbacks to determine task priorities due to the heavy reliance on domain knowledge or failure to efficiently exploit the interaction of application and hardware characteristics. In this paper, we propose INSPIRIT, an efficient and lightweight scheduling framework with adaptive priority designed for task-based runtime systems. INSPIRIT introduces two novel task attributes inspiring ability and inspiring efficiency for dictating scheduling, eliminating the need for application domain knowledge. In addition, INSPIRIT jointly considers runtime information such as ready tasks in worker queues to guide task scheduling. This approach exposes more performance opportunities in heterogeneous hardware at runtime while effectively reducing the overhead for adjusting task priorities. Our evaluation results demonstrate that INSPIRIT achieves superior performance compared to cutting edge scheduling schemes on both synthesized and real-world task DAGs.
Introduction: The Challenge of Heterogeneous Scheduling
Modern High-Performance Computing (HPC) is increasingly defined by heterogeneity, often pairing powerful CPUs with specialized accelerators like GPUs. To manage this complexity, developers rely on task-based runtime systems. These systems represent programs as Directed Acyclic Graphs (DAGs), where nodes represent computational tasks and edges represent data dependencies.
The central challenge in these systems is efficient scheduling: determining the optimal order and placement of tasks across diverse processing units. Current approaches typically fall into two categories: static schedulers that require manual "domain knowledge" to assign task weights, and dynamic schedulers that use complex heuristics or Deep Learning. Static methods are brittle and non-portable, while dynamic methods often introduce significant computational overhead, sometimes negating the performance gains they seek to achieve.
The INSPIRIT Framework
INSPIRIT (Adaptive Priority Scheduling) provides a lightweight, automatic, and portable solution by focusing on the "inspiring" potential of tasks—their ability to unlock future work. The framework operates in two distinct phases:
1. Offline Preprocessing
Before execution, INSPIRIT analyzes the task DAG to calculate two novel attributes for each task:
- Inspiring Ability: This metric counts the total number of future tasks a specific node will eventually unlock. It serves as a proxy for long-term parallelism.
- Inspiring Efficiency: This measures the number of dependencies a task releases per unit of execution time, representing short-term throughput.
2. Online Adaptive Scheduling
At runtime, INSPIRIT monitors the state of the system, specifically the number of ready tasks ($N_{ready}$) in the worker queues. This allows the scheduler to adapt to the hardware's current "hunger" for work.
As shown in Figure 1, the scheduling priority significantly alters the execution timeline. INSPIRIT uses $N_{ready}$ to toggle its strategy:
- Low $N_{ready}$: If the machine is underutilized, the system prioritizes tasks with high inspiring efficiency to generate new ready tasks as quickly as possible.
- High $N_{ready}$: If the queues are full, the system shifts focus to tasks with high inspiring ability to maintain a steady, long-term stream of work.
This logic is implemented as a plugin for the StarPU runtime system, requiring no changes to the underlying application code.
Evaluation and Results
The researchers evaluated INSPIRIT using a mix of synthesized DAGs and real-world HPC workloads, including Tiled Cholesky factorization, LU decomposition, and a Heat transfer solver. Testing spanned multiple hardware configurations involving Intel Xeon CPUs and NVIDIA RTX 3090/Tesla V100 GPUs.
Key Performance Gains
INSPIRIT achieved significant speedups, ranging from 1.03x to 3.22x over the standard Deque Model Data Aware (DMDA) scheduler. Crucially, it often outperformed state-of-the-art manual priority schemes.
Figure 4 illustrates that INSPIRIT (labeled "Base Priority") consistently provides competitive or superior speedups across different hardware pairings and problem sizes (NBLOCKS). Unlike manual tuning, which may excel in one specific environment but fail in another, INSPIRIT's adaptive nature ensures robust performance across diverse platforms.
Conclusion
INSPIRIT demonstrates that effective scheduling in heterogeneous environments does not require heavy computational overhead or manual expert tuning. By leveraging simple metrics like "inspiring ability" and monitoring runtime queue lengths, the framework achieves state-of-the-art performance with minimal latency. Future work will focus on scaling the offline traversal for massive, dynamic DAGs and integrating the framework into other runtime backends like Legion or PaRSEC.
Summary updated