https://www.mdu.se/

mdu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Identification and validation of markov models with continuous emission distributions for execution times
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-7431-5529
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0002-1364-8127
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.ORCID iD: 0000-0001-6132-7945
2020 (English)In: 2020 IEEE 26th International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2020, Institute of Electrical and Electronics Engineers Inc. , 2020Conference paper, Published paper (Refereed)
Abstract [en]

It has been shown that in some robotic applications, where the execution times cannot be assumed to be independent and identically distributed, a Markov Chain with discrete emission distributions can be an appropriate model. In this paper we investigate whether execution times can be modeled as a Markov Chain with continuous Gaussian emission distributions. The main advantage of this approach is that the concept of distance is naturally incorporated. We propose a framework based on Hidden Markov Model (HMM) methods that 1) identifies the number of states in the Markov Model from observations and fits the Markov Model to observations, and 2) validates the proposed model with respect to observations. Specifically, we apply a tree-based cross-validation approach to automatically find a suitable number of states in the Markov model. The estimated models are validated against observations, using a data consistency approach based on log likelihood distributions under the proposed model. The framework is evaluated using two test cases executed on a Raspberry Pi Model 3B+ single-board computer running Arch Linux ARM patched with PREEMPT_RT. The first is a simple test program where execution times intentionally vary according to a Markov model, and the second is a video decompression using the ffmpeg program. The results show that in these cases the framework identifies Markov Chains with Gaussian emission distributions that are valid models with respect to the observations.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers Inc. , 2020.
Keywords [en]
Markov Chain Model, Probabilistic Timing Analysis, Real-time systems, Computer operating systems, Embedded systems, Hidden Markov models, Real time systems, Software testing, Trellis codes, Appropriate models, Continuous emission, Cross validation, Data consistency, Emission distribution, Gaussian emission, Robotic applications, Single board computers, Markov chains
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:mdh:diva-51883DOI: 10.1109/RTCSA50079.2020.9203594Scopus ID: 2-s2.0-85092687388ISBN: 9781728144030 (print)OAI: oai:DiVA.org:mdh-51883DiVA, id: diva2:1479839
Conference
26th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2020; Virtual, Gangnueng; South Korea; 19 August 2020 through 21 August 2020; Category numberCFP20066-ART; Code 163272
Available from: 2020-10-27 Created: 2020-10-27 Last updated: 2022-11-08Bibliographically approved
In thesis
1. Timing and Schedulability Analysis of Real-Time Systems using Hidden Markov Models
Open this publication in new window or tab >>Timing and Schedulability Analysis of Real-Time Systems using Hidden Markov Models
2022 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

In real-time systems functional requirements are coupled to timing requirements, a specified event needs to occur at the appropriate time.  In order to ensure that timing requirements are fulfilled, there are two main approaches, static and measurement-based. The static approach relies on modeling the hardware and software and calculating upper bounds for the timing behavior. On the other hand, measurement-based approaches use timing data collected from the system to estimate the timing behavior.

The usability of static and measurement-based approaches is limited in many modern systems due to the increased complexity of hardware and software architectures. Static approaches to timing and schedulability analysis are often infeasible due to their complexity. Measurement-based approaches require that design-time measurements are representative of the timing behavior at runtime, which is problematic to ensure in many cases. Designing systems that guarantee the timing requirements without excessive resource overprovisioning is a challenge.

A Hidden Markov Model (HMM) describes a system where the behavior is state-dependent.  In this thesis, we model the execution time distribution of a periodic task as an HMM where the states are associated with continuous emission distributions. By modeling the execution times in this manner with a limited number of parameters, a step is taken on the path toward tracking and controlling timing properties at runtime. 

We present a framework for parameter identification of an HMM with Gaussian emission distributions from timing traces, and validation of the identified models. In evaluated cases, the parameterized models are valid in relation to timing traces.

For cases where design-time measurements are not representative of the system at runtime we present a method for the online adaptive update of the emission distributions of an HMM. Evaluation with synthetic data shows that the estimate tracks the ground truth distribution. 

A method for estimating the deadline miss probability for a task with execution times modeled by an HMM with Gaussian emission distributions, in a Constant Bandwidth Server (CBS) is proposed. The method is evaluated with simulation and for a synthetic task with a known Markov Chain structure running on real hardware.

Abstract [sv]

I realtidssystem är funktionella krav kopplade till tidskrav – en viss händelse måste inträffa vid rätt tid. För att försäkra sig om att tidskrav är uppfyllda finns två huvudsakliga metoder – statisk eller mätningsbaserad. En statisk analys baseras på modeller av hårdvara och mjukvara, och beräknar en övre gräns för tidsbeteendet. Mätningsbaserade analyser använder insamlat data från systemet för att uppskatta tidsbeteendet.

Användbarheten av både statiska och mätningsbaserade metoder är begränsad i många moderna system eftersom komplexiteten hos hårdvara och mjukvara ökat. Statiska metoder är ofta omöjliga att genomföra på grund av komplexiteten. För mätningsbaserade metoder krävs att mätningarna som insamlats vid design är representativa för tidsbeteendet i drift, vilket är svårt att garantera i många fall. Att designa system som garanterar tidskraven utan överdriven resurstilldelning är en utmaning.

En Hidden Markov Model (HMM) beskriver ett system med beteende som är tillståndsberoende. I denna avhandling modellerar vi exekveringstidens fördelning hos en periodisk task (uppgift) som en HMM där tillstånden är kopplade till kontinuerliga emissionsfördelningar. Genom att modellera exekveringstiderna på detta vis med ett begränsat antal parametrar, tar vi ett steg på vägen mot att följa och kontrollera tidsbeteendet i drift.

Vi presenterar ett ramverk för parameteridentifiering för en HMM med Gaussiska emissionsfördelningar från tidsdata, och validering av de identifierade modellerna. De parametriserade modellerna är giltiga i relation till tidsdata i de fall som utvärderats.

För fall när mätningar vid design inte är representativa för systemet i drift presenterar vi en metod för direkt adaptiv uppdatering av emissionsfördelningarna i en HMM. Utvärdering med syntetiska data visar att uppskattningen följer den sanna fördelningen.

En metod föreslås för att uppskatta sannolikheten för att missa en deadline när exekveringstiden modelleras som en HMM med Gaussiska emissionsfördelningar hos en task i en Constant Bandwidth Server (CBS). Metoden utvärderas med simulering och med syntetiska program med känd Markov-struktur som körs på verklig hårdvara.

Place, publisher, year, edition, pages
Västerås: Mälardalens universitet, 2022
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 325
National Category
Embedded Systems Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-58194 (URN)978-91-7485-555-5 (ISBN)
Presentation
2022-06-21, Delta + Zoom, Mälardalens universitet, Västerås, 14:00 (English)
Opponent
Supervisors
Available from: 2022-05-10 Created: 2022-05-10 Last updated: 2022-06-01Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Papadopoulos, AlessandroNolte, Thomas

Search in DiVA

By author/editor
Friebe, AnnaPapadopoulos, AlessandroNolte, Thomas
By organisation
Embedded Systems
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 111 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf