Holistically Budgeting Processing Graphs

To certify the schedulability of a system, valid per-task worst-case execution-time (WCET) estimates are almost always required. Unfortunately, on multicore machines, deriving WCET estimates through static analysis that is not highly pessimistic may never be a practical reality. The alternative is to determine WCETs via a measurement process, but such a process cannot correctly produce accurate WCET estimates with certainty. This lack of certainty necessitates the use of overrun-handling mechanisms, such as budget-enforcement techniques, to preserve temporal correctness at runtime. In many systems of interest today, tasks are interconnected to form processing graphs, which can be quite large. The simplest (and perhaps most common) approach to budget enforcement in this case is to abort an entire graph invocation whenever any node (task) overruns its budget. However, such an approach can result in a high abort rate at the graph level even when the per-node abort rate is low. To remedy this situation, this paper presents a holistic budget-management strategy for directed acyclic graphs (DAGs) that involves reallocating per-node budgets to overrunning nodes to avoid DAG-Ievel aborts. To enable the effects of aborts to be studied analytically, a probabilistic analysis is presented to derive a DAG's abort rate under the proposed budget-management strategy. Experimental results are also presented to demonstrate the utility of budgeting graphs holistically.