TITLE:
A Generic Graph Model for WCET Analysis of Multi-Core Concurrent Applications
AUTHORS:
Robert Mittermayr, Johann Blieberger
KEYWORDS:
Worst-Case Execution Time Analysis, Program Analysis; Concurrency, Multi-Threaded Programs, Kronecker Algebra
JOURNAL NAME:
Journal of Software Engineering and Applications,
Vol.9 No.5,
May
23,
2016
ABSTRACT: Worst-case execution time (WCET) analysis
of multi-threaded software is still a challenge. This comes mainly from the
fact that synchronization has to be taken into account. In this paper, we focus
on this issue and on automatically calculating and incorporating stalling times
(e.g. caused by lock contention) in a generic graph model. The idea that thread
interleavings can be studied with a matrix calculus is novel in this research
area. Our sparse matrix representations of the program are manipulated using an
extended Kronecker algebra. The resulting graph represents multi-threaded
programs similar as CFGs do for sequential programs. With this graph model, we
are able to calculate the WCET of multi-threaded concurrent programs including
stalling times which are due to synchronization. We employ a generating
function-based approach for setting up data flow equations which are solved by
well-known elimination-based dataflow analysis methods or an off-the-shelf
equation solver. The WCET of multi-threaded programs can finally be calculated
with a non-linear function solver.