liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Analysis and Optimisation of Real-Time Systems with Stochastic Behaviour
Linköping University, Department of Computer and Information Science, ESLAB - Embedded Systems Laboratory. Linköping University, The Institute of Technology.
2005 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

Embedded systems have become indispensable in our life: household appliances, cars, airplanes, power plant control systems, medical equipment, telecommunication systems, space technology, they all contain digital computing systems with dedicated functionality. Most of them, if not all, are real-time systems, i.e. their responses to stimuli have timeliness constraints.

The timeliness requirement has to be met despite some unpredictable, stochastic behaviour of the system. In this thesis, we address two causes of such stochastic behaviour: the application and platform-dependent stochastic task execution times, and the platform-dependent occurrence of transient faults on network links in networks-on-chip.

We present three approaches to the analysis of the deadline miss ratio of applications with stochastic task execution times. Each of the three approaches fits best to a different context. The first approach is an exact one and is efficiently applicable to monoprocessor systems. The second approach is an approximate one, which allows for designer-controlled trade-off between analysis accuracy and analysis speed. It is efficiently applicable to multiprocessor systems. The third approach is less accurate but sufficiently fast in order to be placed inside optimisation loops. Based on the last approach, we propose a heuristic for task mapping and priority assignment for deadline miss ratio minimisation.

Our contribution is manifold in the area of buffer and time constrained communication along unreliable on-chip links. First, we introduce the concept of communication supports, an intelligent combination between spatially and temporally redundant communication. We provide a method for constructing a sufficiently varied pool of alternative communication supports for each message. Second, we propose a heuristic for exploring the space of communication support candidates such that the task response times are minimised. The resulting time slack can be exploited by means of voltage and/or frequency scaling for communication energy reduction. Third, we introduce an algorithm for the worst-case analysis of the buffer space demand of applications implemented on networks-on-chip. Last, we propose an algorithm for communication mapping and packet timing

for buffer space demand minimisation.

All our contributions are supported by sets of experimental results obtained from both synthetic and real-world applications of industrial size.

Place, publisher, year, edition, pages
Institutionen för datavetenskap , 2005. , 214 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 983
Keyword [en]
Embedded systems, Real-time systems, System level design and optimisation, Stochastic execution times, Performance analysis, Networks-on-chip
National Category
Computer Science
URN: urn:nbn:se:liu:diva-7374ISBN: 91-85457-60-4OAI: diva2:22392
Public defence
2005-12-16, Visionen, Hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Available from: 2006-09-15 Created: 2006-09-15 Last updated: 2009-11-25Bibliographically approved

Open Access in DiVA

fulltext(1303 kB)1166 downloads
File information
File name FULLTEXT01.pdfFile size 1303 kBChecksum SHA-1
Type fulltextMimetype application/pdf

Other links

Link to Licentiate Thesis

Search in DiVA

By author/editor
Manolache, Sorin
By organisation
ESLAB - Embedded Systems LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 1166 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: 496 hits
ReferencesLink to record
Permanent link

Direct link