A Safe and Tight Estimation of the Worst-Case Execution Time of Dynamically Scheduled Parallel Applications
Petros Voudouris, Risat Mahmud Pathan, Per Stenström · Chalmers Publication Library (Chalmers University of Technology) · 2016
Estimating a safe and tight upper bound on the Worst-Case Execution Time (WCET) of a parallel program is a major challenge for the design of real-time systems. This paper, proposes for the first time, a framework to estimate the WCET of dynamically scheduled parallel applications. Assuming that the WCET can be safely estimated for a sequential task on a multicore system, we model a parallel application using a directed acyclic graph (DAG). The execution time of the entire application is computed using a breadth-first scheduler that simulates non-preemptive execution of the nodes of the DAG (called, the BFS scheduler). Experiments using Fibonacci application from the Barcelona OpenMP Task Suite (BOTS) show that timing anomalies are a major obstacle to estimate safely the WCET of parallel applications. To avoid such anomalies, the estimated execution time of an application computed under the simulation of BFS scheduler is multiplied by a constant factor to derive a safe bound on WCET. Finally, an anomaly-free priority-based new scheduling policy (called, the Lazy-BFS scheduler) is proposed to estimate safely the WCET. Experimental results show that the bound on WCET computed using Lazy-BFS is not only safe but also 30% tighter than that computed for BFS.