[Back]

A. Jordan:
"On Worst-Case Execution Time Analysis and Optimization";
Supervisor, Reviewer: A. Krall, M. Schöberl; Inst. für Computersprachen, 2014; oral examination: 2014-03-27.

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 measurements
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 software
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 computing
systems. For a cache architecture dedicated to the program stack, we describe the
algorithms required to extendWCET analysis to accurately determine its worst-case behavior.
Our evaluation reveals that the analysis of such a stack cache architecture, scales
to large applications with complex calling behavior, while remaining efficient to compute
and yielding precise results at the same time.
Aworst-case-aware transformation of code is another possibility to reduce theWCET
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 adaptWCET 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
itsworst-case criticality. We formally define this metric and investigate some of its properties
with respect to dominance in control-flow graphs. Exploiting these, we propose
v
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 programs.
From the beginnings of staticWCET analysis, research has addressed methods to reduce
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 analyzing
a program´s behavior on a specific hardware platform grows too large. With our
final contribution, we adapt the innerworkings of the state-of-the-art path-basedWCET
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.

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, kurzWCET 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 Programmeausgeführtwerden.
Beides wirkt sich negativ auf die Analyselaufzeit, sowie deren Genauigkeit aus. HoheWCET-
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 vonAusführungszeiten entworfen wird. Der negative Einfluss von
in Hardware implementiertenOptimierungen (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ürWCET-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 vonWCET-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
vii
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 dessenWCET-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 derWCET Analyse verwendet werden.
Umprä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.