Mittermayr, Robert ;
Blieberger, Johann
Timing Analysis of Concurrent Programs
Abstract
Worstcase execution time analysis of multithreaded software is still a challenge. This comes mainly from the fact that the number of thread interleavings grows exponentially in the number of threads and that synchronization has to be taken into account. In particular, a suitable graph based model has been missing. The idea that thread interleavings can be studied with a matrix calculus is a novel approach in this research area. Our sparse matrix representations
of the program are manipulated using Kronecker algebra. The resulting graph represents the multithreaded program and plays a similar role for concurrent systems as control flow graphs do for sequential programs. Thus a suitable graph model for timing analysis of multithreaded software has been set up. Due to synchronization it turns out that often only very small parts of the resulting graph are actually needed, whereas the rest is unreachable. A lazy implementation of the matrix operations ensures that the unreachable parts are never calculated. This speeds up processing significantly and shows that our approach is very promising.
BibTeX  Entry
@InProceedings{mittermayr_et_al:OASIcs:2012:3557,
author = {Robert Mittermayr and Johann Blieberger},
title = {{Timing Analysis of Concurrent Programs}},
booktitle = {12th International Workshop on WorstCase Execution Time Analysis},
pages = {5968},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783939897415},
ISSN = {21906807},
year = {2012},
volume = {23},
editor = {Tullio Vardanega},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3557},
URN = {urn:nbn:de:0030drops35570},
doi = {http://dx.doi.org/10.4230/OASIcs.WCET.2012.59},
annote = {Keywords: Worstcase execution time analysis (WCET), Concurrency, Thread Synchronization, Kronecker Algebra, Program Analysis}
}
2012
Keywords: 

Worstcase execution time analysis (WCET), Concurrency, Thread Synchronization, Kronecker Algebra, Program Analysis 
Seminar: 

12th International Workshop on WorstCase Execution Time Analysis

Related Scholarly Article: 


Issue date: 

2012 
Date of publication: 

2012 