Title: Minimal preconditions for timing anomalies in WCET calculations
Language: English
Authors: Martinek, Christoph 
Qualification level: Diploma
Keywords: Serielle Zeitanomalien; Parallele Zeitanomalien; Worst-Case Execution Time; WCET Analyse; Pipeline Architekturen; Cache Architekturen
Series Timing Anomalies; Parallel Timing Anomalies; Worst-Case Execution Time; WCET Analysis; Pipeline Architectures; Cache Architectures
Advisor: Puschner, Peter
Issue Date: 2011
Number of Pages: 72
Qualification level: Diploma
Abstract: 
Bei Echtzeitsystemen ist die Analyse der Worst-Case-Execution-Time (WCET) von entscheidender Bedeutung. Die Kenntnis über diese maximale Ausführungszeit führt zu einer notwendigen Vorhersage des Zeitverhaltens bei zeitkritischen Systemen. Um eine detaillierte Untersuchung des Zeitverhaltens eines Programms durchzuführen, ist in modernen Echtzeitsystemen, in denen unterschiedliche Cache- und Pipeline-Architekturen vorkommen, das Wissen über den Verlauf einer Ausführung von Wichtigkeit. Mit diesen Informationen können Besonderheiten, nämlich sogenannte Zeitanomalien, analysiert und notwendige Bedingungen dafür hergeleitet werden. Beim Auftreten von Zeitanomalien wird im Verlauf einer Ausführung die Eigenschaft Proportionalität im zeitlichen Verhalten verletzt.
In dieser Diplomarbeit werden die wichtigsten Zeitanomalien charakterisiert und Methoden vorgestellt, mit denen sich gewisse Anomalien bezüglich der Berechnung der WCET berechnen lassen. Darunter fallen serielle Zeitanomalien, welche über eine Anzahl von unterschiedlichen Pfaden auftreten können, und parallele Anomalien, bei denen der timing-relevant dynamic computer state (TRDCS) in unterschiedliche Hardwarekomponenten aufgeteilt wird.
Für eine aussagekräftige Analyse ist eine genaue Erforschung von Zeitanomalien in verschiedenen Cache- sowie in Pipeline-Architekturen erforderlich. Es werden hier die Cache-Ersetzungsstrategien FIFO, Pseudo Round Robin und Pseudo LRU genauer betrachtet. Bei Pipeline-Architekturen werden Simple Scalar-, Scalar-, Superscalar In-Order und Super-scalar Out-of-Order-Pipelines untersucht. Es werden Vorbedingungen für Zeitanomalien ausgearbeitet, die in diesen Architekturen auftreten können. Darüber hinaus wird gewissermaßen eine Checkliste erarbeitet, mit der Prozessoren betreffend der eintretenden Zei- tanomalien eingestuft werden können.

In real-time systems it has an important relevance to analyse the worst-case-execution-time (WCET). With the knowledge of the maximum execution time it is possible to predict the behaviour of time-critical systems. To get a detailed analysis of the timing behaviour, it is necessary to know about the control flow of a program in modern real-time systems, in which different cache- and pipeline-architectures are used. So called timing anomalies could get analysed with the information of the control flow and the instructions. Along with this, necessary conditions for their appearance could be determined. If timing anomalies occur, the attribute proportionality in timing behaviour is violated during an execution.
In this thesis the most important timing anomalies are characterized and techniques to calculate the WCET are presented. There are series timing anomalies, which appear on a number of different paths along an execution, and parallel timing anomalies, where the timing-relevant dynamic computer state (TRDCS) is partitioned into different hardware components.
It is necessary for a strong analysis to investigate timing anomalies in cache- and pipeline-architectures. Timing anomalies combined with the cache replacement strategies FIFO, pseudo round robin and pseudo LRU are observed. Also pipeline-architectures like simple scalar-, scalar-, superscalar in-order and superscalar out-of-order-pipelines in association with timing anomalies are explored. For timing anomalies, which occur in these architectures, preconditions are elaborated. To classify a specific processor with a potential timing anomaly a checklist is created.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-38427
http://hdl.handle.net/20.500.12708/14803
Library ID: AC07810266
Organisation: E182 - Institut für Technische Informatik 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

12
checked on Feb 18, 2021

Download(s)

53
checked on Feb 18, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.