Reservation-Based Federated Scheduling for Parallel Real-Time Tasks

Niklas Ueter, Georg von der Brüggen, Jian-Jia Chen, Jing Li, Kunal Agrawal

Abstract

Multicore systems are increasingly utilized in real-time systems to address high computational demands. To fully exploit multicore processing, intra-task parallelism modeled as a directed acyclic graph (DAG) must be utilized efficiently. This paper considers the scheduling problem for parallel real-time tasks with constrained and arbitrary deadlines. It generalizes federated scheduling and proposes a novel reservation-based approach. We propose a strategy that reduces scheduling arbitrary-deadline DAG task sets to scheduling arbitrary-deadline sequential task sets by allocating reservation servers. We provide a general reservation design for sporadic parallel tasks, allowing any scheduling algorithm and analysis for sequential tasks to be used. The proposed algorithms provide constant speedup factors with respect to any optimal scheduler. Numerical and empirical experiments demonstrate that our algorithms are competitive with the state of the art.

Introduction: The Challenge of Parallel Real-Time Tasks

In modern real-time systems, such as autonomous vehicles or robotics, tasks are increasingly parallelized to meet high computational demands. These are often modeled as Directed Acyclic Graphs (DAGs), where nodes represent subtasks and edges represent dependencies.

Example of a parallel task modeled as a Directed Acyclic Graph (DAG).

The challenge lies in scheduling these tasks on multicore processors. Existing "federated scheduling" approaches classify tasks as "heavy" (needing more than one processor) and grant them exclusive access to a set of cores. However, this can be wasteful; if a heavy task has a short deadline but low overall work, it might hog processors that sit idle. Furthermore, previous research suggested that federated scheduling could not provide a "constant speedup factor" for tasks with arbitrary deadlines.

Methodology: Reservation-Based Federated Scheduling

The authors propose a "reservation-based" approach that generalizes federated scheduling. Instead of allocating $N$ physical processors to a task, they assign $m_i$ reservation servers.

Key components of the method include:

  • Task Transformation: Algorithms like R-MIN and R-EQUAL transform a single parallel DAG task into a set of sequential "reservation" tasks with specific execution budgets and deadlines.
  • The Reservation Condition: A formal condition ($C_i + L_i(m_i - 1) \leq \sum E_{i,j}$) ensures that if these sequential servers are scheduled successfully, the original parallel DAG task meets its deadline.
  • List Scheduling: Within the allocated reservation time, a simple "list scheduler" picks available subtasks from the DAG.
  • Reduction to Sequential Scheduling: By converting parallel tasks into sequential ones, developers can use established analyses like Partitioned Deadline Monotonic or Earliest Deadline First.
The R-MIN Algorithm for transforming heavy parallel tasks into sequential reservation servers.

Key Insights and Results

The most powerful idea is the "interface" created by provably sufficient reservations, which hides internal task parallelism from the global scheduler. The authors prove that their method achieves a constant speedup factor of $3 + 2\sqrt{2} \approx 5.82$, refuting earlier assumptions about the limitations of federated-style scheduling for arbitrary-deadline tasks.

The proposed approach "dominates" traditional federated scheduling by offering more flexibility to pack "light" tasks onto the same processors, reducing resource waste. The R-MIN algorithm (shown above) optimizes packing by creating the minimum number of servers required.

Conclusion and Future Work

While the analysis accounts for "spinning" (active servers with no ready subtasks), it assumes a worst-case DAG structure, which can be pessimistic. Future work aims to treat gaps in DAG execution as "self-suspensions" for tighter analysis and to extend this reservation logic to global scheduling algorithms.

Summary updated

Abstract

This paper considers the scheduling of parallel real-time tasks with arbitrary-deadlines. Each job of a parallel task is described as a directed acyclic graph (DAG). In contrast to prior work in this area, where decomposition-based scheduling algorithms are proposed based on the DAG-structure and inter-task interference is analyzed as self-suspending behavior, this paper generalizes the federated scheduling approach. We propose a reservation-based algorithm, called reservation-based federated scheduling, that dominates federated scheduling. We provide general constraints for the design of such systems and prove that reservation-based federated scheduling has a constant speedup factor with respect to any optimal DAG task scheduler. Furthermore, the presented algorithm can be used in conjunction with any scheduler and scheduling analysis suitable for ordinary arbitrary-deadline sporadic task sets, i.e., without parallelism.
BibTeX
@inproceedings{ueter2018reservation,
  author = {Niklas Ueter and Georg von der Brüggen and Jian-Jia Chen and Jing Li and Kunal Agrawal},
  title = {{Reservation-Based Federated Scheduling for Parallel Real-Time Tasks}},
  booktitle = {RTSS},
  year = {2018},
  url = {https://openreview.net/forum?id=p9ROaQUxRdo},
}
Figure