Startseite > Messen + Testen > Testsysteme > Zeitanalyse komplexer eingebetteter Systeme

Systemdesign / Echtzeitbenchmarks

Zeitanalyse komplexer eingebetteter Systeme

29. August 2018, 13:48 Uhr | Prof. Dr. Reinhard Wilhelm, Compiler Design Lab, Universität des Saarlandes

▶ Diesen Artikel anhören

Fortsetzung des Artikels von Teil 1

Die Ursache des Problems

Betrachten wir, wodurch die Ausführungszeiten eines Programms bestimmt sind. Da ist erstens die Eingabe in das Programm. Sie bestimmt den Pfad, welchen die Ausführung durch das Programm nimmt. Verschiedene Eingaben führen i.A. zu verschiedenen Pfaden. Da nur terminierende Programme verwendet werden sollen, müssen die Iterationszahlen von Schleifen und die Rekursionstiefe von Funktionen begrenzt sein. Sonst können wir keine endlichen oberen Schranken für die Ausführungszeiten bestimmen.

Die Anforderung: Alle Schleifen im Programm müssen aus dem Programm ersichtliche, aus ihm ableitbare oder vom Entwickler spezifizierte maximale Iterationszahlen haben, und sämtliche Funktionen begrenzte Rekursionstiefe. Bei einfachen Mikrocontrollern ergibt diese Forderung eine einfache Methode zur Bestimmung der Zeitschranken. Ihre Befehle haben konstante Ausführungszeiten. Man suche also einen längsten Pfad durch das Programm, setze für alle Befehle auf diesem Pfad die entsprechenden Ausführungszeiten ein, summiere auf, fertig! Dazu müsste aber, wie oben gesagt, zumindest die Eingabe im schlechtesten Fall bekannt sein.

Alternativ könnte man obere Schranken für die Laufzeiten gemäß der Programmstruktur zusammensetzen. Die Schranke für eine bedingte Anweisung, etwa aus dem Maximum der Schranken beider Fälle, plus der Schranke für Auswertung der Bedingung. Diese sogenannte Zeitschemata-Methode war die Methode der Wahl bis Anfang der 90er Jahre. Statt die Menge aller Pfade erschöpfend auszuführen, um die exakte Ausführungszeit im schlechtesten Fall zu bestimmen, schätzen korrekte und effiziente Methoden die Ausführungszeiten sicher nach oben ab.

Auch die Zeitschemata-Methode ist nicht mehr verwendbar, seit eingebettete Systeme auf leistungsorientierten Prozessoren mit Caches, tiefen Pipelines, out-of-order-Ausführung von Befehlen und Spekulation realisiert werden. Diese Prozessoren wurden von den Rechnerarchitekten für die Verwendung in PCs und Hochleistungsrechnern entworfen. Das Ziel war und ist hohe Leistung im Durchschnitt. Die eben geschilderten Errungenschaften der Rechnerarchitektur wie Caches und Pipelines führten dazu, dass die Ausführungszeiten von Befehlen jetzt nicht mehr konstant sind, sondern vom jeweiligen Ausführungszustand des Prozessors abhängen. Die Ausführungszeit eines Speicherzugriffs hängt jetzt entscheidend davon ab, ob der Inhalt der zugegriffenen Speicherzelle gerade im Cache liegt oder nicht. Der Unterschied zwischen dem schnellsten Zugriff, der Fall eines Cache-Hits, und dem langsamsten Zugriff, dem Cache-Miss, kann mehr als den Faktor 100 betragen.

Ähnlich ist die Größenordnung der Variabilität der Ausführungszeiten von Befehlen. In den meisten Fällen werden die Ausführungen schnell sein. Aber eine solche stochastische Argumentation reicht für harte Echtzeitsysteme nicht aus! Sie brauchen eine Garantie für jede Ausführung. Wenn man für alle Befehle jeweils ihre längste Ausführungszeit annimmt, hätte man natürlich eine solche Garantie. Nur leider würde diese die tatsächlich schlechteste Ausführungszeit i.A. sehr stark überschätzen. Die Schranken wären nicht präzise genug.

Für Programme auf Prozessoren mit variablen Befehlsausführungszeiten ist eine effiziente Methode gesucht, mit der zuverlässige und präzise obere Laufzeitschranken bestimmt werden können.