An Abstract Interpretation-Based Framework for WCET Analysis of Parallel Programs

Estimating the Worst-Case Execution Time (WCET) of programs in an embedded multi-core environment is fundamental for schedulability analysis. In this paper, we propose a framework for calculating the WCET of programs originally designed for single-core systems when migrated to and executed in parallel on multi-core environments. First, we decompose single-core tasks and convert them into parallel programs using OpenMP. Our approach extends the task dependency graph to describe relevant information for parallel tasks (such as execution time estimation, core allocation, and inter-task dependencies). Finally, we present an iterative algorithm based on abstract interpretation. This algorithm takes the parallel task dependency graph as input and uses fixed-point analysis to determine the WCET of parallel programs. We conducted experiments on a physical machine to verify the feasibility of our solution.