A Generic Graph Model for WCET Analysis of Multi-Core Concurrent Applications

Author(s):Robert Mittermayr, Johann Blieberger

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.


Journal: Journal of Software Engineering and Applications
DOI: 10.4236/jsea.2016.95015

Paper Id: 66661 (metadata)

See also: Comments to Paper

About scirp

(SCIRP: http://www.scirp.org) is an academic publisher of open access journals. It also publishes academic books and conference proceedings. SCIRP currently has more than 200 open access journals in the areas of science, technology and medicine. Readers can download papers for free and enjoy reuse rights based on a Creative Commons license. Authors hold copyright with no restrictions. SCIRP calculates different metrics on article and journal level. Citations of published papers are shown based on Google Scholar and CrossRef. Most of our journals have been indexed by several world class databases. All papers are archived by PORTICO to guarantee their availability for centuries to come.
This entry was posted in JSEA and tagged , , , . Bookmark the permalink.

Comments are closed.