Processor pipelines in WCET analysis

Abstract

Due to their nature, hard real-time embedded systems (e.g. flight control systems) must be guaranteed to satisfy their time constraints under all operating conditions. The provision of such guarantee relies on safe and precise estimates of the worst-case execution time (WCET) of tasks. As the execution time depends on both the program and the architecture running it, the growing sophistication of architectures complicates the task of timing analyses. This work studies the impact of the design of the microprocessor’s pipeline on the precision and efficiency of WCET analysis. We study the influence of the design of the load-store unit (LSU) in a modern microprocessor, the PowerPC 7448, on WCET analysis. To this end, we introduce a simplified variant of the existing design of the LSU by reducing its queue sizes. The study contributes empirical evidence supporting the argument that micro-architectural innovations do not improve, and sometimes harm, a processor’s worst-case timing behavior. Building on this evidence, we introduce a compiler optimization to reduce analysis time and memory consumption during the two most-computationally-demanding steps of WCET analysis. With our prototype implementation of the optimization, we observe an analysis speedup of around 635% at the cost of an increase in the WCET bound of 6%. Moreover, under a less precise yet significantly faster variant of the analysis, the WCET bound is decreased by 5% while the analysis is sped up by 350%.

Eingebettete harte Echtzeitsysteme (wie z.B. Flugkontrollsysteme) müssen ihre vorgegebenen Laufzeitgarantien erfüllen. Diese Laufzeitgarantien basieren auf sicheren und präzisen Schranken für die maximale Ausführungszeit (WCET) der Programme. Die Ausführungszeit von Programmen hängt sowohl von dem Programm selbst ab als auch von der Hardware-Plattform, auf der das Programm ausgeführt wird. Die wachsende Komplexität der Hardware-Architekturen erschwert die Berechnung sicherer und präzier Laufzeitschranken (WCET-Analyse). Diese Arbeit untersucht den Einfluss der Pipeline eines Mikroprozessors auf die Präzision und Effizienz einer WCET-Analyse. Wir untersuchen den Einfluss der Load-Store-Unit (LSU) eines modern Mikroprozessors, des PowerPC 7448, auf eine WCET-Analyse. Wir entwickeln eine vereinfachte Variante der LSU, in der die Warteschlangen verkleinert wurden. Unser Experiment stützt die These, dass mikroarchitektonische Innovationen keinen generellen Fortschritt darstellen, sondern manchmal auch schaden können, wie hier im Beispiel der Bestimmung des Worst-Case-Zeiterhaltens eines Prozessors. Weiterhin schlagen wir eine Compiler-Optimierung zur Reduzierung der Analysezeit und des Speicherverbrauchs der WCET Analyse vor. Mit unserer Prototyp-Implementierung dieser Optimierung ist eine Reduzierung der Analysezeit von ca. 635% auf Kosten einer 6%-Erhöhung in der WCET-Schranken zu beobachten. Unter einer schnellere Variante der Analyse wird die WCET-Schranke um 5% verringert während die Analyse um 350% beschleunigt werden kann.