Minimal preconditions for timing anomalies in WCET calculations

Abstract

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.<br />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.<br />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.

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.<br />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.<br />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.<br />