Please use this identifier to cite or link to this item: doi:10.22028/D291-26603
Title: Processor pipelines in WCET analysis
Other Titles: Prozessor-Pipeline in WCET-Analyse
Author(s): Abdel Maksoud, Mohamed
Language: English
Year of Publication: 2015
SWD key words: Prozessor
Worst-Case-Laufzeit
Compiler
Free key words: WCET analysis
analysis efficiency
compiler optimization
analyzability
predictability
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
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.
Link to this record: urn:nbn:de:bsz:291-scidok-61284
hdl:20.500.11880/26659
http://dx.doi.org/10.22028/D291-26603
Advisor: Wilhelm, Reinhard
Date of oral examination: 24-Apr-2015
Date of registration: 11-Jun-2015
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
Thesis.pdf752,9 kBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.