Budgeting Processing Graphs Under Restricted Parallelism

Certifying graph-based workloads on multicore systems requires valid worst-case execution time (WCET) estimates, which are challenging to obtain. This warrants a method to enforce execution budgets at runtime. Allowing a node in a processing graph to overrun its budget can delay future in-vocations of that node due to data dependencies. Conversely, preventing overruns may lead to high rates of graph invocation aborts. This paper presents a budget-enforcement method that allows nodes to overrun with limited effect on future node invocations. Additionally, analysis is presented for bounding the abort probability of each graph invocation. Experimental results are given to demonstrate the efficacy of the presented method.