<  Back to the Polytechnique Montréal portal

Static Probabilistic Timing Analysis for Real-Time Embedded Systems in Presence of Faults

Chao Chen

Ph.D. thesis (2017)

Open Access document in PolyPublie
[img]
Preview
Open Access to the full text of this document
Terms of Use: All rights reserved
Download (2MB)
Show abstract
Hide abstract

Abstract

A cache is typically the bridge between a processor and its main memory. It significantly reduces the access latencies to memory blocks and its timing behavior. Random caches—caches with a random replacement policy—have been proposed to improve timing behavior estimates in critical real-time embedded systems (CRTESs) by reducing pathological cases due to systematic cache misses. Measurement Based Probabilistic Timing Analysis (MBPTA)and Static Probabilistic Timing Analysis (SPTA) aim at providing safe probabilistic Worst Case Execution Time (pWCET) estimates for random caches. In this dissertation, we present research work on timing estimation based on SPTA. State-of-the-art SPTA methodologies produce safe and tight pWCET estimates. However, as semiconductor technology scales down, CRTES components—especially their on-chip caches—become prone to faults. Consequently,we developed SPTA methodologies to estimate pWCETs in the presence of faults, and evaluated the impacts of faults on timing behaviors. To investigate faults, we first defined transient and permanent fault models. A transient fault represents a temporary change of state. The system with transient faults can be recovered using fault detection and correction techniques. A permanent fault represents a permanent change of state. It persists after its occurrence and affects the system's behavior afterwards. Additionally, we proposed a Markov chain method to model memory layout states. For each memory block access, the state changes are calculated using a transition matrix. The transient fault impacts were integrated into the transition matrix computation, and we used different groups of Markov chain models to represent the system with different number of permanent faults. Experiments showed that our SPTA method provided accurate results in the presence of both transient and permanent faults.

Résumé

Une mémoire cache est le lien entre le processeur et la mémoire principale. Elle permet de réduire considérablement les temps d'accès aux blocs de mémoire dans un système embarqué temps-réel et critique (CRTES), ce qui influence énormément son comportement temporel. Des caches à accès aléatoire—caches avec une politique de remplacement aléatoire—ont été proposées dans le but d'améliorer les estimations du comportement temporel des CRTES, et cela en diminuant les cas pathologiques. Les Measurement Based Probabilistic Timing Analysis (MBPTA) et Static Probabilistic Timing Analysis (SPTA) sont deux méthodes qui ciblent à estimer le pire temps d'exécution (Worst Case Execution Time probabiliste - pWCET) d'une façon probabiliste et sécuritaire pour les caches aléatoires. À travers cette dissertation, on présente des travaux de recherche concernant l'estimation temporelle basée sur la méthode SPTA. L'état de l'art sur les méthodologies SPTA fournissent des estimations sécuritaires et strictes. En revanche, au vu de la réduction d'échelle des technologies des semiconducteurs utilisés pour la mise en oeuvre des composants faisant partie des CRETS, les caches sur puce sont de plus en plus prédisposés aux pannes. Par conséquent, nous avons développé des méthodologies SPTA pour l'estimation des pWCETs en présence de pannes. Nous avons effectué également des évaluations de l'impact de ces fautes sur les comportements temporels. Afin d'examiner les pannes, nous avons modélisé dans un premier temps les pannes transitoires et permanentes. Une panne transitoire représente un changement d'état temporaire. Le système peut ainsi être restauré en utilisant des techniques de détection et de correction des pannes. D'un autre côté, une panne permanente introduit un changement permanent. Elle persiste après son apparition et affecte en conséquence le comportement général du système. Nous avons alors proposé une méthode basée sur les chaînes de Markov afin de modéliser les états de disposition de la mémoire. Pour chaque accès à un bloc de mémoire, le changement de l'état est calculé en utilisant une matrice de transition, tout en tenant compte des impacts des fautes transitoires. Nous avons également utilisé différents types de modèles de la chaîne de Markov pour représenter le système ayant subi un nombres différent de pannes permanentes. Les expériences montrent que notre méthode SPTA assure des résultats précis en présence des pannes transitoires et permanentes.

Department: Department of Computer Engineering and Software Engineering
Program: Génie informatique
Academic/Research Directors: Giovanni Beltrame
PolyPublie URL: https://publications.polymtl.ca/2686/
Institution: École Polytechnique de Montréal
Date Deposited: 30 Oct 2017 15:39
Last Modified: 30 Apr 2023 03:25
Cite in APA 7: Chen, C. (2017). Static Probabilistic Timing Analysis for Real-Time Embedded Systems in Presence of Faults [Ph.D. thesis, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/2686/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item