Recursive Partitioned Scheduling for Real-Time Gang Tasks

The development of parallel computing architectures has created a growing need for scheduling real-time gang tasks, in which a specified number of threads per task must be executed simultaneously under timing constraints. However, existing approaches struggle to handle a fundamental challenge the heterogeneity in the number of threads across gang tasks. To address the challenge, this paper proposes a novel scheduling framework, called Recursive Partitioned Scheduling (RPS), in which each partition can be recursively divided into subpartitions whose assigned processor sets are disjoint and collectively equal to that of the parent, forming a tree-like hierarchical structure. RPS provides a flexible interface that allows each task to be assigned to an appropriate level in the hierarchy based on the number of threads it requires. To fully exploit RPS, we adopt fixed-priority scheduling and address two key issues. First, we develop a tight schedulability analysis, which not only utilizes the well-known exact schedulability analysis results for uniprocessor scheduling but also leverages the relationship between intra-and inter-partition interference. Second, based on the insights from the analysis, we design an effective partition generation and task assignment algorithm specialized for RPS, and further enhance it through task priority reassignment. Simulation results demonstrate that our approach significantly outperforms existing approaches in terms of schedulability.