On worst-case execution time analysis and optimization

Abstract

Die Zuverlässigkeit von eingebetteten Systemen ist durch deren große Verbreitung und Einsatz in sicherheitskritischen Bereichen, zu einem wichtigen Thema in Forschung und Entwicklung geworden. Hierbei spielt nicht nur die funktionale Korrektheit, sondern auch das Zeitverhalten einer Anwendung eine ausschlaggebende Rolle. Aus Messungen des Zeitverhaltens eines solchen Echtzeitsystems können Schätzungen, aber keine garantierten Schranken zu dessen Zeitverhalten in sämtlichen Szenarien abgeleitet werden. Die Verwendung von statischer Analyse zur Bestimmung von garantierten oberen Laufzeitschranken, kurz WCET Analyse, wird zum Beispiel bereits in der Auto- und Flugzeugindustrie eingesetzt. Primär steht bei der statischen Analyse die Generierung einer sicheren Schranke im Vordergrund. Sekundär soll die Analyse in möglichst kurzer Zeit ihr Ergebnis liefern und eine möglichst genaue Schranke berechnen, das heißt sich möglichst nah an die tatsächliche längste Ausführungszeit annähern. Ein Problem dieser Analysemethode ist jedoch die stetig steigende Komplexität von Computerprogrammen und Hardwarearchitekturen, auf denen diese Programme ausgeführt werden. Beides wirkt sich negativ auf die Analyselaufzeit, sowie deren Genauigkeit aus. Hohe WCET-Schranken in Relation zum Normalverhalten (programminherent oder durch Überschätzung während der Analyse) bedingen wiederum, dass mehr Leistung für die Ausführung zur Verfügung gestellt werden muss. Hier setzen die Optimierungen, die in dieser Dissertation ausgeführt werden, an. Die Patmos Plattform erlaubt uns Analysen an eine Architektur anzupassen, die für die Vorhersagbarkeit von Ausführungszeiten entworfen wird. Der negative Einfluss von in Hardware implementierten Optimierungen (z.B. Caches, Pipelining), die im allgemeinen Fall zwar die Ausführungszeit steigern können, jedoch die Berechnung von oberen Schranken für diese erschweren, wird mit der Patmos Architektur vermieden. In dieser Dissertation beschreiben wir, wie das neue Konzept eines Stack Cache, präzise Analysen ermöglicht, deren Ergebnisse sich einfach in ein bestehendes Berechnungsmodell für WCET-Schranken integrieren lassen. Durch die Trennung von Zugriffen auf andere Speicherbereiche und das vorhersagbare Zeitverhalten des Stack Cache können genauere Schranken berechnet werden. Die Qualität von WCET-Schranken, die mittels statischer Analyse gefunden werden können, hängt grundlegend mit der Struktur eines Programms und des Maschinencodes, der dafür erzeugt wird, zusammen. Werkzeuge, welche die Entwicklung von Echtzeit-Programmen erleichtern, zum Beispiel dafür optimierte Übersetzer, sind zu diesem Zeitpunkt noch kaum ausgereift. Zur Unterstützung des Entwicklungsprozesses, sowohl auf Seiten des Programmierers als auch des Übersetzers, entwerfen wir eine Metrik, die über die Längste-Pfad-Sicht, die zur Berechnung einer Schranke herangezogen wird, hinausgeht. Diese Metrik gibt Aufschluss darüber, wie kritisch alle Teile eines Programms im Hinblick auf dessen WCET-Schranke sind und ermöglicht eine vollständige Sicht auf dessen Verhalten im schlechtesten Fall der Ausführung. Wir beschreiben die Meta-Analyse zur Berechnung von criticality mit Hilfe von effizienten Algorithmen und evaluieren deren Verhalten für Echtzeit-Programme, die als Standard-Testfälle im Bereich der WCET Analyse verwendet werden. Um präzisere Schranken für die Ausführungszeit jeder Art von Hardware Architektur zu berechnen, beschreibt diese Dissertation schlussendlich ein Verfahren, das auf dem Separieren von Knoten in der Graphen-Darstellung eines Programms basiert. Das Ziel dieser Optimierung ist wiederum, durch das Ausschließen von Interferenzen und unter Erhalt der Sicherheit, eine genauere obere Schranke für das Zeitverhalten berechnen zu können. Unsere ersten Experimente mit dieser Methode, ergeben vielversprechende Verbesserungen der Schranken um bis zu 6%. Hierbei ist anzumerken, dass die Verbesserung der Analysegenauigkeit durch Graph Pruning mit der Größe des analysierten Programms ansteigt.

Embedded systems have become a prevalent part of our daily lives. We can find them often more than one, connected to each other in our cars, phones and appliances. We rely on their availability for convenience, and in other, safety-critical areas, we rely on their correctness, sometimes with our lives. When such an embedded system has to perform a task (e.g. respond) in real-time, its correctness is not limited to functional requirements. In this case, we also want to verify its timing correctness. Timing mea- surements of the target system given a series of different inputs can lead to an estimation of its worst-case behaviors. But for any non-trivial application, it is impossible to reliably trigger the actual worst case. Static analysis of the system and its software can provide a safe upper bound of all possible timing results. We refer to this technique as worst-case execution time (WCET) analysis. Tools for static WCET analysis have recently become mature enough to be adopted by the avionics and automotive industries. But as soft- ware becomes more complex, the effort of performing static WCET analysis grows as well. This affects the computational effort caused by the analysis, as well as the effort spent by the engineer working with the analysis tool. In this thesis we describe methods to adapt static WCET analysis in light of above noted problems and needs. With the Patmos platform, we have a hardware environment that heeds predictable execution as a primary design goal. This extends to the modeling of caches, which are a major factor of unpredictability in universal comput- ing systems. For a cache architecture dedicated to the program stack, we describe the algorithms required to extend WCET analysis to accurately determine its worst-case be- havior. Our evaluation reveals that the analysis of such a stack cache architecture, scales to large applications with complex calling behavior, while remaining efficient to com- pute and yielding precise results at the same time. A worst-case-aware transformation of code is another possibility to reduce the WCET bound. Seeing that compiler support for WCET optimization is in its infancy, it is left to the programmer to avoid generating code that is hard to analyze and to do ad-hoc optimization of regions that analysis has shown to trigger the longest execution time. In this context, we further adapt WCET analysis to anticipate the need of programmers and compilers to get a more complete picture of a program¿s worst-case timing behavior. Through a meta-analysis approach, we create a novel metric that classifies code by its worst-case criticality. We formally define this metric and investigate some of its prop- erties with respect to dominance in control-flow graphs. Exploiting these, we propose algorithms that reduce the overhead of computation by inference. Experiments using a set of real-time benchmarks show the feasibility of our WCET profiling approach and reveal considerable amounts of highly critical as well as uncritical code in these pro- grams. From the beginnings of static WCET analysis, research has addressed methods to re- duce the amount of overestimation. Overestimation is a necessary evil, which is applied in various forms, when the state space that would have to be tracked for precisely ana- lyzing a program¿s behavior on a specific hardware platform grows too large. With our final contribution, we adapt the inner workings of the state-of-the-art path-based WCET analysis technique to follow a pruning approach. Our method is based on the notion of Criticality, we introduced before, and can eliminate potential sources of overestimation. Pruning approaches for program analysis have been proposed before, but to the best of our knowledge, this is the first time, pruning is done on the low-level representation of the program graph. Our first experiments with graph pruning use a commercial WCET analysis tool and show that our approach is feasible in practice and can improve the WCET bound up to 6% compared to the commercial tool as a baseline.