Introduction
In the design of real-time multi-core systems, ensuring that tasks meet their deadlines is a fundamental requirement. These tasks are often modeled as Directed Acyclic Graphs (DAGs), where nodes represent computational units and edges represent execution dependencies. For over half a century, the industry standard for estimating the completion time of these tasks has been Graham’s bound, established in 1969. While robust, Graham’s bound is known for its significant pessimism, often leading to the over-provisioning of hardware resources. This paper introduces a novel analysis technique that provides a tighter response time bound by accounting for multiple long paths within a DAG, rather than relying solely on the single longest path.
The Problem: The Pessimism of Graham’s Bound
Graham’s bound calculates the response time of a DAG task based on two primary metrics: the total workload (the sum of the execution times of all nodes) and the length of the single longest path (the critical path). The bound assumes that any workload not located on the critical path could potentially interfere with its execution by occupying available processor cores.
However, this assumption is often unrealistic. In practice, many "interfering" nodes are constrained by their own internal dependencies, forcing them to run in parallel with the critical path rather than delaying it. Because Graham’s bound treats this interference as a monolithic block of work that can be "smeared" across cores to cause maximum delay, it frequently overestimates the time required for a task to finish. For engineers, this translates to a requirement for more CPU cores than are actually necessary to guarantee safety.
Methodology: From Single-Path to Multi-Path Analysis
The authors propose a shift from a single-path view to a multi-path view of DAG execution. The core of this approach is the identification of a Generalized Path List, which captures the lengths of several disjoint long paths within the graph.
The Residue Graph Algorithm
To identify these paths efficiently, the authors developed a residue-based approach:
- Identify the Longest Path: Find the longest path ($L_0$) in the DAG.
- Create a Residue: Record the length of $L_0$ and set the execution time of all nodes on this path to zero.
- Iterate: Find the longest path in the resulting "residue" graph ($L_1$).
- Repeat: This process continues to generate a sequence of paths ($L_0, L_1, \dots, L_k$).
A New Response Time Formula
By utilizing this list of paths, the authors derived a new closed-form bound. Unlike Graham’s formula, which only subtracts the single longest path from the total workload to calculate potential interference, the new bound subtracts the sum of the lengths of multiple long paths. To ensure the mathematical safety of this bound, the authors introduced the concept of "Virtual Paths"—theoretical abstractions representing workloads that must execute sequentially in a specific trace, even if they do not form a single path in the original DAG. This method is proven to theoretically dominate Graham’s bound, meaning it is guaranteed to be at least as accurate as the classic method and significantly better in most practical scenarios.
Experimental Evaluation
The researchers evaluated the proposed bound using synthetic DAG workloads generated via the Erdős-Rényi method. The study involved 5,000 DAGs for each configuration, varying parameters such as the number of vertices (50 to 250), edge density (parallelism factor), and deadline constraints. The new bound was compared against Graham’s bound and the state-of-the-art Virtually-Federated Scheduling (VFED) analysis.
Key Results
- Increased Accuracy: The new bound improved upon Graham’s predicted response times by 13.1% to 16.2%.
- Resource Efficiency: In single-task scenarios, the method reduced the number of cores required to meet a specific deadline by an average of 47.9%.
- Improved Schedulability: When applied to multi-task systems using federated scheduling, the new bound increased the "acceptance ratio" (the percentage of task sets successfully scheduled) by up to 96.5% compared to VFED.
- Computational Performance: The algorithm for computing the path list is highly efficient, with a complexity of $O(V(V+E))$, making it suitable for integration into real-world design and analysis tools.
Conclusion and Future Work
By moving beyond the single longest path, this research provides a more nuanced and accurate way to calculate the response time of DAG tasks on multi-core systems. The resulting reduction in core requirements offers significant potential for cost and power savings in embedded and real-time systems.
While the current method requires full knowledge of the DAG's structure, future work aims to explore measurement-based approaches where "virtual paths" are identified through execution traces. Additionally, the authors plan to extend this multi-path analysis from federated scheduling to global scheduling environments, where tasks share a common pool of processor cores.
Summary updated