Precise measurement-based worst-case execution time estimation

Abstract

Ein Echtzeitcomputersystem ist ein Computersystem, bei dem die Korrektheit des Systemverhaltens nicht nur von den logischen Berechnungsergebnissen abhängt, sondern auch vom physikalischen Zeitpunkt, zu dem die Resultate erzeugt werden. Heutzutage werden die meisten Echtzeitcomputersysteme als Ansammlungen von Software-Tasks implementiert, welche parallel auf einer passenden Hardware-Plattform mit einem oder mehreren Mikroprozessoren oder Mikroprozessorkernen ausgeführt werden. Das Ermitteln der Worst-Case Execution Time (WCET) der einzelnen Echtzeit-Tasks ist ein essentieller Schritt bei der Sicherstellung der Korrektheit eines solchen Systems.<br />Die Messbasierte Zeitanalyse (MBTA) ist ein einfach retargierbarer Ansatz zur Abschätzung der WCET eines gegebenen Tasks, der auf einer bestimmten Hardware- Plattform ausgeführt wird. Bei diesem Ansatz werden die Ausführungszeiten einzelner Task-Fragmente gemessen, während der Task auf der vorgesehenen Target-Hardware ausgeführt wird. Die beobachteten lokalen Ausführungszeiten werden anschließend zu einer globalen WCET-Abschätzung für den Gesamt-Task zusammengesetzt.<br />Die Industrie fordert WCET-Abschätzungen, die nahe an der tatsächlichen WCET liegen. Um diese Forderung zu erfüllen, müssen wir zwei gegensätzliche Einflüsse auf die Nähe der mit MBTA ermittelten WCET-Abschätzungen beschränken: (1) die konservative Berechnung von WCET-Abschätzungen, bekannt als Pessimismus, und (2) die unvollständige Messabdeckung, bekannt als Optimismus.<br />Vorläufige Versionen einzelner Forschungsergebnisse in dieser Dissertation wurden bereits im Rahmen unterschiedlicher wissenschaftlicher Formate publiziert. In dieser Dissertation erweitere ich die folgenden originären Beiträge:<br />Kontextsensitives IPET: Ich diskutieren kontextsensitives IPET als Strategie zur Verringerung des Pessimismus in Standard-IPET.<br />Integration von Methoden: Ich diskutiere, wie die Methoden zur Verringerung von Optimismus und Pessimismus, die in Rahmen des FORTAS-Projekts entwickelt wurden, zu einem vollständigen MBTA-Ansatz zusammengefügt wurden, der nährere WCET-Abschätzungen liefern kann, als dies mit Standard-IPET-Ansätzen möglich ist.<br />Experimentelle Evaluierung: Ich stellen eine experimentelle Evaluierung des FORTAS-Ansatzes vor. Die Evaluierung umfasst insbesondere einen quantitativen Vergleich zwischen den Analyseergebnissen des FORTAS-Werkzeugs und der entsprechenden Analyseergebnisse des statischen WCET Analyseswerkzeugs aiT.<br />

A real-time computer system is a computer system in which the correctness of the system behavior depends not only on the logic results of the computations, but also on the physical instant at which these results are produced. Today, most real-time computer systems are implemented as collections of software tasks that are executed concurrently on a suitable hardware platform consisting of one or multiple microprocessors or microprocessor cores. Obtaining the worst-case execution time (WCET) of each real-time task is an essential step in ensuring the correctness of such a system.<br />Measurement-based timing analysis (MBTA) is an easily retargetable analysis approach for estimating the WCET of a given task running on a particular target platform. In this approach, the execution times of individual task fragments are measured while the task is being executed on the intended target hardware. The observed local execution times of the individual task fragments are subsequently combined into a global WCET estimate for the task as a whole.<br />Industry demands WCET estimates that are close to the actual WCET. To fulfill this requirement, we must limit two opposed influences on the closeness of WCET estimates obtained by MBTA: (1) conservative WCET estimate calculation, otherwise known as pessimism, and (2) incomplete measurement coverage, also known as optimism.<br />Preliminary versions of individual research results found in this thesis have been published in various scientific formats. In this thesis I strengthen the following original contributions:<br />Context-sensitive IPET: I discuss context-sensitive IPET as a strategy for reducing the pessimism found in standard IPET. Integration of methods: I discuss how the methods for reducing optimism and pessimism that have been developed within the FORTAS project have been tied together to form a complete MBTA approach that can provide closer WCET estimates than possible with standard MBTA approaches.<br />Experimental evaluation: I present an experimental evaluation of the FORTAS approach. The results indicate the effectiveness of the approach.<br />Most importantly, the evaluation includes a quantitative comparison between analysis results obtained by the FORTAS tool and the corresponding results of the industrial-strength static WCET analysis tool aiT.<br />