Reservation-Based Federated Scheduling for Parallel Real-Time Tasks

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

TL;DR

This paper introduces reservation-based federated scheduling, a novel framework for managing parallel real-time tasks modeled as Directed Acyclic Graphs (DAGs). By replacing dedicated processor allocation with flexible "reservation servers," the authors provide a way to schedule complex parallel tasks using standard sequential scheduling tools while guaranteeing a constant speedup factor—a major theoretical milestone for tasks with arbitrary deadlines.

What Problem Does This Paper Address?

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

The challenge lies in scheduling these tasks on multicore processors. Existing "federated scheduling" approaches are popular because they are simple: they classify tasks as "heavy" (needing more than one processor) and give them exclusive access to a set of cores. However, this is incredibly wasteful. If a heavy task has a short deadline but low overall work, it might hog several processors that sit idle most of the time. Furthermore, previous research suggested that federated scheduling couldn't provide a "constant speedup factor" (a measure of how close an algorithm is to an optimal one) for tasks with arbitrary deadlines.

Methods

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

Key components of their method include:

  • Task Transformation: They provide algorithms (R-MIN and R-EQUAL) to transform a single parallel DAG task into a set of sequential "reservation" tasks. These servers have specific execution budgets and deadlines.
  • The Reservation Condition: They derive a formal condition ($C_i + L_i(m_i - 1) \leq \sum E_{i,j}$) ensuring that if these sequential servers are scheduled successfully, the original parallel DAG task is guaranteed to meet its deadline.
  • List Scheduling: Within the allocated reservation time, the system uses a simple "list scheduler" to pick available subtasks from the DAG.
  • Reduction to Sequential Scheduling: By turning parallel tasks into sets of sequential ones, the authors allow developers to use any established scheduling analysis (like Partitioned Deadline Monotonic or Earliest Deadline First) to prove the system is safe.

Datasets

The paper primarily relies on theoretical proofs and synthetic task sets to validate its claims. It references specific task set examples from prior literature (e.g., Chen [7]) to demonstrate how standard federated scheduling fails where their new approach succeeds.

Key Insights and Ideas

  • Bridging the Parallel-Sequential Gap: The most powerful idea here is the "interface." By creating a provably sufficient reservation, the complexity of internal task parallelism is hidden from the global scheduler.
  • Overcoming the "Speedup" Hurdle: The authors prove that their method achieves a constant speedup factor of $3 + 2\sqrt{2} \approx 5.82$. This refutes earlier assumptions that federated-style scheduling was fundamentally limited for arbitrary-deadline tasks.
  • Robustness through "Spinning": The model accounts for "spinning" (when a reservation server is active but the DAG has no ready subtasks due to dependencies). While this sounds inefficient, it provides a robust analytical bound that doesn't require knowing the exact internal structure of the DAG at runtime.

Key Results

  • Dominance: The proposed reservation-based approach "dominates" traditional federated scheduling. It can replicate federated scheduling's behavior but offers more flexibility to pack "light" tasks onto the same processors, reducing waste.
  • Constant Speedup Factor: They formally prove that for both Partitioned Fixed-Priority (DM) and Dynamic-Priority (EDF) scheduling, the algorithm maintains a constant speedup factor relative to an optimal (but computationally impossible) scheduler.
  • Algorithmic Flexibility: The R-MIN algorithm allows for "packing" optimization by creating the minimum number of servers required, while R-EQUAL simplifies analysis by giving all servers the same budget.

Limitations and Future Work

  • Pessimism in Structure: The analysis assumes the worst-case DAG structure. In practice, tasks might finish much earlier, leading to "spinning" where resources are reserved but not used.
  • Self-Suspension: The authors note that treating the gaps in DAG execution as "self-suspensions" could lead to even tighter, more efficient analysis in the future.
  • Global Scheduling: This paper focuses on partitioned scheduling (where tasks are assigned to specific cores). The authors aim to extend this reservation logic to global scheduling algorithms in future research.

Summary updated

Abstract

Multicore systems are increasingly utilized in real-time systems in order to address the high computational demands. To fully exploit the advantages of multicore processing, possible 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. In contrast to prior work in this area, it generalizes federated scheduling and proposes a novel reservation-based approach. Namely, we propose a reservation-based federated scheduling strategy that reduces the problem of scheduling arbitrary-deadline DAG task sets to the problem of scheduling arbitrary-deadline sequential task sets by allocating reservation servers. We provide the general reservation design for sporadic parallel tasks, such that any scheduling algorithm and analysis for sequential tasks with arbitrary deadlines can be used to execute the allocated reservation servers of parallel tasks. Moreover, the proposed reservation-based federated scheduling algorithms provide constant speedup factors with respect to any optimal scheduler for arbitrary-deadline DAG task sets. We demonstrate via numerical and empirical experiments that our algorithms are competitive with the state of the art.
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},
}

Loading related content...

Figure