A Generic Graph Model for WCET Analysis of Multi-Core Concurrent ApplicationsReport as inadecuate




A Generic Graph Model for WCET Analysis of Multi-Core Concurrent Applications - Download this document for free, or read online. Document in PDF available to download.

Worst-case execution time WCET analysisof multi-threaded software is still a challenge. This comes mainly from thefact that synchronization has to be taken into account. In this paper, we focuson this issue and on automatically calculating and incorporating stalling timese.g. caused by lock contention in a generic graph model. The idea that threadinterleavings can be studied with a matrix calculus is novel in this researcharea. Our sparse matrix representations of the program are manipulated using anextended Kronecker algebra. The resulting graph represents multi-threadedprograms similar as CFGs do for sequential programs. With this graph model, weare able to calculate the WCET of multi-threaded concurrent programs includingstalling times which are due to synchronization. We employ a generatingfunction-based approach for setting up data flow equations which are solved bywell-known elimination-based dataflow analysis methods or an off-the-shelfequation solver. The WCET of multi-threaded programs can finally be calculatedwith a non-linear function solver.

KEYWORDS

Worst-Case Execution Time Analysis, Program Analysis; Concurrency, Multi-Threaded Programs, Kronecker Algebra

Cite this paper

Mittermayr, R. and Blieberger, J. 2016 A Generic Graph Model for WCET Analysis of Multi-Core Concurrent Applications. Journal of Software Engineering and Applications, 9, 182-198. doi: 10.4236-jsea.2016.95015.





Author: Robert Mittermayr, Johann Blieberger

Source: http://www.scirp.org/



DOWNLOAD PDF




Related documents