Worst Case Execution Time

Die maximale Ausführungszeit (englisch Worst Case Execution Time, WCET) gibt die längste Zeit an, die ein Computerprogramm oder Programmteil auf einer bestimmten Plattform zur Ausführung benötigen kann. Sie wird bestimmt durch:

• die Programmlogik an sich (Kontrollflussgraph),
• die Eingabedaten (Auswirkungen auf Schleifendurchlaufzahlen etc.),
• der Compiler (Optimierungsstufe), und
• die Architektur und Taktfrequenz des Ausführungsrechners (Ausführungsgeschwindigkeit unter Berücksichtigung von Cache- und Pipelining-Effekten).

Die Kenntnis der WCET oder zumindest einer sicheren oberen Schranke ist ein notwendiges Kriterium zur Implementierung eines harten Echtzeitsystems. Bei Echtzeitsystemen ist es sehr wichtig das logisch richtige Ergebnis zu exakten Zeitpunkten zu erhalten. Nur kurze Verzögerungen könnten katastrophale Auswirkungen haben. Die wichtigsten Anwendungsgebiete für Echtzeitsysteme sind z. B. Autoairbagsteuerungen, Flugzeugsteuerungen, Steuerungen in Kraftwerken. Bei Autosteuerungen kann das verspätete Herausschleudern des Airbags tödliche Folgen für die Insassen des Kraftfahrzeuges haben. Daher ist es wichtig, dass Echtzeitsysteme das richtige Ergebnis in einer bestimmten Zeit bereitstellen.

Die Ausführungszeit

Grundsätzlich wird zwischen BCET (best case execution time) und WCET (worste case execution time) unterschieden. Die BCET ist die schnellste Ausführungsdauer indem das Programm ein Ergebnis liefert, d. h. das Programm kann unter keinen Umständen schneller ausgeführt werden. Die WCET ist die längstmögliche Ausführungsdauer in dem der Programmcode ein Ergebnis bereitstellt.

Grundsätzliche Probleme der Laufzeitbestimmung

Theoretische Grenzen

Im allgemeinen Fall ist es unmöglich die maximale Ausführungszeit für ein beliebiges Programm zu bestimmen.

Um die maximale Ausführungszeit zu bestimmen, müsste man folgendes Problem lösen: Gegeben ist ein Programm P. Gesucht ist ein weiteres Programm WCET, das die maximale Ausführungszeit von P, also WCET(P), berechnet. Da alle jene Programme, die in eine Endlosschleife laufen, eine maximale Ausführungszeit $\infty$ haben, könnte man das Programm WCET benutzen, um zu entscheiden, ob das zugrundeliegende Programm überhaupt terminiert und somit das Halteproblem lösen. Das Halteproblem ist jedoch nachweislich unentscheidbar, somit kann es das Programm WCET nicht geben.

Die WCET kann aber für eine relevante Untermenge aller möglichen Programme bestimmt werden.

Praktische Probleme

Die Schedulingstrategien moderner Betriebssysteme verhindern eine zuverlässige Voraussage zu welchem Zeitpunkt ein Task dran kommt. Abhilfe schaffen hier Echtzeitbetriebssysteme oder Direktimplementierungen ohne Betriebssystemschicht.

Auf modernen Prozessorarchitekturen hängt die Ausführungszeit eines Tasks mitunter stark von dem Zustand des Prozessorcaches ab. Selbst bei Verwendung eines Echtzeitbetriebssystems kann so zu Beeinflussungen zweier Tasks über den Cache kommen.

Methoden zur Bestimmung

Es gibt verschiedene Methoden die WCET zu berechnen, die sich allerdings nur durch Genauigkeit und Anwendbarkeit unterscheiden. Eine wichtige Bedeutung ist es, wie genau die WCET abgeschätzt werden kann. Die Methoden versuchen daher so nahe wie möglich an die wirkliche Ausführungszeit heranzukommen, das Ergebnis darf aber nie kleiner als die tatsächliche Ausführungszeit sein.

Eine Möglichkeit zur Abschätzung der WCET sind Messmethoden. Bei diesen Methoden wird durch verschiedenste Testläufe auf der Zielhardware die Zeit gemessen, welche der Code benötigt, um ein Ergebnis zu liefern. Diese Methode gibt ist sehr aufwändig, da nie alle Zustände getestet werden können (Kombinatorische Explosion).

Bei der WCET-Analyse wird hingegen der längste Ausführungsweg ermittelt und die Ausführungszeit für eine bestimmte Zielhardware so errechnet.

Messbasierte Ansätze

Die messbasierten Ansätze führen statt einer Analyse des Codes das Programm einfach auf der Zielhardware aus und messen die Ausführungszeit. Messbasierte Ansätze führen jedoch im Allgemeinen zu einer Unterschätzung der WCET, da die Ausführungszeit von Programmen generell von den Eingabedaten abhängt. Durch Analyse des Sourcecodes können jedoch Eingabedatensätze erzeugt werden, welche alle Pfade des zu testenden Programms abdecken. Diese Methode vereinfacht zwar die Portierung einer Software, leidet aber ebenfalls unter komplexen Prozessorarchitekturen.

WCET-Analyse

Die WCET-Analyse berechnet den schlechtesten Fall der Ausführungszeit eines bestimmten Codes einer Anwendung, jedoch besteht keine Garantie der Richtigkeit der Ergebnisse des Codes. Weiter ist die WCET vom Programmcode und von der zugrundeliegenden Hardware abhängig, d. h. verschiedene Programmcodes haben auf verschiedenen Rechnerarchitekturen unterschiedliche Worst Case Execution Times. Daher sollte die Analyse immer mit den Hardwarekomponenten durchgeführt werden die auch das Echtzeitsystem besitzt. Bei dieser Methode wird der Programmcode untersucht und der tatsächlich längste Ausführungsweg ermittelt. Der längste Weg durch den Programmcode wird gesucht, dann addiert man für jeden Maschinencodebefehle die jeweils benötigten Prozessorzyklen und man erhält die WCET.

Probleme bei der WCET-Analyse

Es gibt drei Problemdomänen bei der WCET-Analyse. Einerseits das Herausfinden des auszuführenden Pfades, die Übersetzung des Sourcecodes in den Maschinencode und die Maschinencodeanalyse.

Bestimmung des auszuführenden Pfades (Programmfluss): Ein Problem der WCET-Analyse ist es, den längsten Weg bezüglich der Laufzeit des Sourcecodes herauszufinden. Ein gutes Beispiel dafür sind Schleifen, die nach Abhängigkeit der Eingabe eine andere Ausführungszeit benötigen. Hierbei muss jeder Eingabefall durchgespielt werden. Allerdings ist das bei komplexeren Systemen unmöglich, weil es zu viele verschiedene Eingabemöglichkeiten gibt.

Übersetzung vom Sourcecode in den Maschinencode: Wenn der Pfad bekannt ist, kann der Sourcecode in den Maschinencode übersetzt werden. Das Problem in diesem Fall ist, dass bei neuen Übersetzern sich auch der Programmfluss im Maschinencode ändert. Daraus folgt dann, dass der gefundene Programmfluss mit übersetzt werden muss damit er mit dem Maschinencode übereinstimmt.

Maschinencodeanalyse: Die Dauer der Ausführung ist auch von der verwendeten Hardware abhängig. Der Cache und die Befehlspipelines bestimmen den Zustand der Hardware. Dabei hängt der Cache wieder vom gesamten bis dahin ausgeführten Programm ab. Es kann somit nicht angenommen werden, dass kein Cache existiert. Des Weiteren können auch keine statischen Werte verwendet werden, da sonst die WCET zu ungenau werden würde.

Lösungsansätze der Probleme

Es gibt Lösungsansätze für jedes der drei Probleme die bei der WCET-Analyse auftreten.

Programmflussanalyse: bei der Programmflussanalyse gibt es mehrere Lösungsansätze. Einer davon wäre, Programmiersprachen zu verwenden, die keinen unüberschaubaren Code erlauben, wie z. B. Rekursionen oder zeitlich unbegrenzt laufende Schleifen. Ein anderer Lösungsansatz wäre es, dem Programmierer im Sourcecode eine Möglichkeit zu geben, Informationen über den Sourcecode zu vermerken. Für diesen Vorschlag müsste jedoch ein spezieller Compiler entwickelt und verwendet werden. Falls man keine speziellen Compiler dafür verwenden will, kann der Programmierer auch seine Informationen außerhalb des Sourcecodes in einer Beschreibungssprache angeben. Eine Bestimmung der Ausführungszeit ist aber nur auf Maschinencodeebene möglich. Somit muss ein WCET-Analyse Tool eine Abbildung von Sourcecodeannotationen auf Maschinencode vornehmen, was nur unter genauer Kenntnis des Compilerverhaltens möglich ist. Dies erfordert eine enge Zusammenarbeit mit der Analysetool- und Compilerhersteller.

Übersetzung vom Sourcecode in den Maschinencode: das größte Problem liegt jedoch in der Umwandlung des Programmflusses des Sourcecodes in den Programmfluss des Maschinencodes. Ein Lösungsansatz in diesem Fall wäre es, den Programmfluss erst im Maschinencode zu ermitteln. Dadurch fällt die Übersetzung weg. Jedoch ist diese Variante nur schwer lösbar, da der Maschinencode schwer lesbar ist. Die Qualität der WCET-Abschätzung leidet auch darunter, da genaue Informationen zur Ausführungszeit nur im Sourcecode vermerkt werden können.

Maschinencodeanalyse: Einer der sichersten Ansätze um die WCET zu ermitteln ist es, immer einen Cache-Miss anzunehmen bis die Variable im Datencache steht. Bei der Maschinencodeanalyse wird die Zeit einzelner Befehle und die Beeinflussung anderer Befehle bestimmt. Meistens ist bekannt wie lange ein Prozessor benötigt um bestimmte Befehle abzuarbeiten.

Berechnungsmethoden

Die Berechnung der WCET erfolgt aus den Informationen aus Maschinencodeanalyse und Programmflussanalyse. Es gibt verschiedene Möglichkeiten, die WCET zu berechnen. Bei der pfadbasierenden Methode werden alle möglichen Pfade im Programm ermittelt und ihre Ausführungszeit berechnet. Danach wird das Maximum der Ausführungszeit ermittelt. Eine weitere Methode zur Berechnung der WCET ist die baumbasierende Methode. Hierbei wird das gesamte Programm durch einen Parse-Baum ersetzt. Dann wird zu jeder Gruppe von Befehlen eine Ausführungszeit ermittelt. Mit dieser Methode können Programmflussinformationen nur schwer eingebaut werden. Die letzte Methode verwendet einen Integer-Linear-Programm-Solver. Bei dieser Methode wird in jeder möglichen Programmverzweigung eine Integervariable angegeben. Diese Variable bestimmt, wie oft der bestimmte Codeteil ausgeführt wurde. Die Zeit für einen bestimmten Pfad im Programm wurde durch die Maschinencodeanalyse ermittelt. Mit dieser Methode wird zusätzlich auch noch der längste Pfad ermittelt.

Siehe auch

• Komplexitätstheorie
• Landau-Notation
• Zeitkomplexität

Literatur

• A. Burns, P. Puschner: Review of worst-case execution-time analysis (editorial). Technical Report 1, September 1999.
• Ch. Koza, P. Puschner: Calculating the maximum execution time of real-time programs. Technical Report 1, April 1989.
• Günther Raidl, Petra Mutzel: Algorithmen und Datenstrukturen 1. Institut für Computergraphik und Algorithmen, Technische Universität Wien, 3. Auflage.
• P. Puschner: Is worst-case execution-time analysis a non-problem? – towards new software and hardware architectures. Technical Report 44, Juni 2002.
• B. Rieder, R. Kirner, I. Wenzel, P. Puschner: Using measurements as a complement to static worstcase execution time analysis. Technical Report 42, Dezember 2005.
• P. Puschner, R. Kirner: International workshop on wcet analysis – summary. Technical Report 12, 2002.
• P. Puschner R. Kirner, P. Atanassov: Using real hardware to create an accurate timing model for execution-time analysis. Technical Report 46, Dezember 2001.
• Robert Sedgewick: Algorithmen. 2. Auflage. Addison-Wesley, 1992.
• Ronald Rives, Clifford Stein, Thomas H. Cormen, Charles E. Leiserson: Algorithmen – Eine Einführung. 2. Auflage. Oldenbourg Verlag, München Wien 2001.
• Christian Wagenknecht: Algorithmen und Komplexität. Carl Hanser Verlag, München Wien 2003.
• B. Rieder, I. Wenzel, R. Kirner, P. Puschner: Measurement-based worst-case execution time analysis. Technical Report 33, Mai 2005.
• Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, and Per Stenström: The Determination of Worst-Case Execution Times-Overview of the Methods and Survey of Tools. ACM Transactions on Embedded Computing Systems (TECS), 7(3), 2008.
• Christian Ferdinand, Florian Martin, Christoph Cullmann, Marc Schlickling, Ingmar Stein, Stephan Thesing, and Reinhold Heckmann: New Developments in WCET Analysis. In: T. Reps, M. Sagiv, J. Bauer (Hrsg.): Program Analysis and Compilation. Theory and Practice. Essays Dedicated to Reinhard Wilhelm on the Occasion of His 60th Birthday. Volume 4444 of LNCS, Springer Verlag, 2007, S. 12–52.
• Lili Tan: The Worst Case Execution Time Tool Challenge 2006: The External Test. In: Tiziana Margaris, Anna Philippou, and Bernhard Steffen (Hrsg.): 2nd International Symposium on Leveraging Applications of Formal Methods (ISOLA'06)- Paphos, Cyprus November 2006.
• Reinhold Heckmann, Marc Langenbach, Stephan Thesing, Reinhard Wilhelm: The Influence of Processor Architecture on the Design and the Results of WCET Tools. Proceedings of the IEEE, 91(7):1038–1054, July 2003.
• Stephan Thesing, Jean Souyris, Reinhold Heckmann, Famantanantsoa Randimbivololona, Marc Langenbach, Reinhard Wilhelm, Christian Ferdinand: An Abstract Interpretation-Based Timing Validation of Hard Real-Time Avionics. In: Proceedings of the International Performance and Dependability Symposium (IPDS). IEEE Computer Society Press, June 2003, S. 625–632.
• Christian Ferdinand, Reinhold Heckmann, Marc Langenbach, Florian Martin, Michael Schmidt, Henrik Theiling, Stephan Thesing, Rheinhard Wilhelm: Reliable and Precise WCET Determination for a Real-Life Processor. In Embedded Software Workshop. Volume 2211, Lake Tahoe, USA October 2001, S. 469–485.