TL;DR
This paper introduces a novel, purely combinatorial algorithm for computing symbolic worst-case execution times (WCET) in real-time systems. It offers a significant improvement over existing methods by achieving polynomial time complexity in both input and output size, while also providing more accurate bounds by avoiding the relaxation of non-linear constraints inherent in previous approaches.
What Problem Does This Paper Address?
In real-time systems, especially those with hard deadlines (like medical devices or flight control), it's crucial not only that computations are logically correct but also that they complete within a specified time frame. Missing a deadline can have catastrophic consequences. To guarantee this timeliness, engineers need to compute upper bounds on the worst-case execution time (WCET) of software tasks.
Traditional WCET analysis involves constructing a control flow graph (CFG) of the program, estimating execution times for basic code blocks, and determining bounds on loop iterations. The WCET is then found by identifying the longest path in the CFG that respects these loop bounds. A major challenge arises when loop bounds are not fixed numerical values but depend on system inputs (e.g., sensor readings). In such "parametric" or "symbolic" scenarios, existing methods often resort to integer linear programming (ILP) solvers. However, symbolic loop bounds introduce non-linearities into the ILP formulation, forcing relaxations that reduce accuracy. Furthermore, these ILP-based approaches can be computationally expensive, with exponential running times.
This paper addresses the need for a more efficient and accurate method for symbolic WCET analysis, particularly for software with a regular structure common in real-time systems.
Methods
The authors propose a new, purely combinatorial algorithm for computing symbolic longest path weights in control flow graphs (CFGs). The core of their approach is a recursive decomposition of the problem.
- Singleton-Loop Graphs: The algorithm is designed for a specific type of CFG called "singleton-loop graphs." These graphs have a structured loop hierarchy where each loop has a unique entry node and uniquely defined sub-loops. This structure is common in well-written real-time software that avoids constructs like
goto. - Recursive Decomposition: The algorithm works by identifying loops within the CFG. For each loop, it recursively computes the longest paths within that loop and to its "portal nodes" (nodes from which the loop exits).
- Graph Condensation: Loops are then "contracted" into single nodes in a condensed graph. This condensed graph is a Directed Acyclic Graph (DAG), allowing for efficient computation of longest paths.
- Symbolic Polynomials: Crucially, instead of numerical values, the algorithm computes path weights as symbolic polynomials over the loop bound variables. This allows it to handle symbolic loop bounds directly without relaxation.
- Combinatorial Approach: The algorithm avoids ILP solvers altogether, relying on a purely combinatorial method. This is a key differentiator from prior work.
Datasets
Not discussed in the paper. The paper focuses on the theoretical development of an algorithm and its properties, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Symbolic Bounds without Relaxation: The most significant insight is the development of an algorithm that can compute accurate symbolic WCET bounds without resorting to the accuracy-reducing relaxations typically required by ILP-based methods.
- Polynomial Time Complexity: The algorithm achieves a running time that is polynomial in both the size of the input graph and the size of the output (the symbolic polynomials representing path weights). This is a substantial improvement over the exponential complexity of previous ILP-based approaches.
- Structured Graphs for Efficiency: The algorithm's efficiency is partly due to its focus on "singleton-loop graphs," which represent a common and desirable structure in real-time software. This highlights the trade-off between generality and performance.
- Output Size Considerations: While the algorithm is efficient, the paper also delves into the complexity of the output size, showing that for certain structured graphs, the number of distinct longest paths can be minimized, and the number of terms in the weight polynomials is bounded.
Key Results
- Polynomial Time Algorithm: The paper presents the first algorithm capable of computing symbolic longest path weights in CFGs in polynomial time with respect to input and output size.
- Improved Accuracy: By avoiding the relaxation of non-linear constraints, the algorithm provides potentially tighter and more accurate symbolic WCET bounds compared to previous parametric ILP approaches.
- Theoretical Guarantees: The paper provides theoretical analysis of the algorithm's running time and the size of its output, demonstrating its efficiency and the minimality of the output for specific graph classes.
Limitations and Future Work
- Singleton-Loop Graph Assumption: The primary limitation is that the core algorithm is designed for "singleton-loop graphs." While this structure is common in well-written real-time code, it might not apply to all software. The paper does briefly mention an extension for "while-loop-graphs" which disallow
breakstatements. - Output Size for General Graphs: For general CFGs, the number of reported paths can still be exponentially large (up to $2^{2^{slbs(G)}}$ in the worst case), although the authors show that their algorithm is better than the theoretical worst-case for certain structured graphs.
- Future Work: The authors plan to investigate the difference between the upper and lower bounds on the minimal output size and compare their algorithm's output size with the minimal possible output size for programs that avoid
gotoconstructs but allowbreakandcontinuestatements. They also aim to explore the practical performance of their algorithm through experiments.
Summary updated