Change search
ReferencesLink to record
Permanent link

Direct link
Static Timing Analysis of Parallel Systems Using Abstract Execution
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. (IS (WCET analysis of parallel systems))ORCID iD: 0000-0001-8882-2292
2014 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

The Power Wall has stopped the past trend of increasing processor throughput by increasing the clock frequency and the instruction level parallelism.Therefore, the current trend in computer hardware design is to expose explicit parallelism to the software level.This is most often done using multiple processing cores situated on a single processor chip.The cores usually share some resources on the chip, such as some level of cache memory (which means that they also share the interconnect, e.g. a bus, to that memory and also all higher levels of memory), and to fully exploit this type of parallel processor chip, programs running on it will have to be concurrent.Since multi-core processors are the new standard, even embedded real-time systems will (and some already do) incorporate this kind of processor and concurrent code.

A real-time system is any system whose correctness is dependent both on its functional and temporal output. For some real-time systems, a failure to meet the temporal requirements can have catastrophic consequences. Therefore, it is of utmost importance that methods to analyze and derive safe estimations on the timing properties of parallel computer systems are developed.

This thesis presents an analysis that derives safe (lower and upper) bounds on the execution time of a given parallel system.The interface to the analysis is a small concurrent programming language, based on communicating and synchronizing threads, that is formally (syntactically and semantically) defined in the thesis.The analysis is based on abstract execution, which is itself based on abstract interpretation techniques that have been commonly used within the field of timing analysis of single-core computer systems, to derive safe timing bounds in an efficient (although, over-approximative) way.Basically, abstract execution simulates the execution of several real executions of the analyzed program in one go.The thesis also proves the soundness of the presented analysis (i.e. that the estimated timing bounds are indeed safe) and includes some examples, each showing different features or characteristics of the analysis.

Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2014. , 240 p.
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 186
Keyword [en]
WCET analysis, parallel systems, multi-core, multicore, threaded programming language
National Category
Computer Systems Embedded Systems
Research subject
Computer Science
URN: urn:nbn:se:mdh:diva-26125ISBN: 978-91-7485-170-0OAI: diva2:756862
2014-12-15, Omega, Mälardalens högskola, Västerås, 10:00 (English)
Worst-Case Execution Time Analysis of Parallel SystemsRALF3 - Software for Embedded High Performance Architectures
Swedish Research CouncilSwedish Foundation for Strategic Research
Available from: 2014-10-20 Created: 2014-10-20 Last updated: 2014-11-19Bibliographically approved

Open Access in DiVA

fulltext(2920 kB)87 downloads
File information
File name FULLTEXT01.pdfFile size 2920 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Gustavsson, Andreas
By organisation
Embedded Systems
Computer SystemsEmbedded Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 87 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 667 hits
ReferencesLink to record
Permanent link

Direct link