Please use this identifier to cite or link to this item: doi:10.22028/D291-26418
Title: Cache persistence analysis for embedded real-time systems
Other Titles: Cache Persistenz Analyse für eingebettete Echtzeit Systeme
Author(s): Cullmann, Christoph
Language: English
Year of Publication: 2013
SWD key words: Cache-Speicher
Persistenz <Informatik>
Analyse
Hartes Echtzeitsystem
Free key words: cache
persistence
analysis
real-time systems
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
Abstract: To compute a worst-case execution time (WCET) estimate for a program running on a safety-critical hard real-time system, the effects of the architecture of the underlying hardware have to be modeled. The classical cache analysis distinguishes three categories for memory references to cached memory: always-hit, always-miss and not-classified. The cache persistence analysis tries to classify memory references as persistent thereby improving the classical cache analysis by limiting the number of misses for not-classified memory references. We present several new abstract interpretation based cache persistence analyses. Two are based on the concept of conflict counting, one on the may cache analysis, and one combines both concepts. All analyses also fix a correctness issue of the original cache persistence analysis by Ferdinand and Wilhelm. For non-fully-timing-compositional architectures using the persistence information is not straightforward. A novel path analysis enables the use of persistence information also for state-of-the-art architectures that exhibit timing anomalies / domino effects. The new analyses are practically evaluated within the industrially used WCET analyzer aiT on a series of standard benchmark programs and a series of real avionic examples.
Um eine obere Schranke für die Laufzeit eines Programms (WCET) auf einem sicherheitskritischen harten Echtzeit-System zu berechnen, müssen die Effekte der Architektur der zugrunde liegenden Hardware modelliert werden. Die klassische Cache-Analyse unterscheidet drei Kategorien für Speicherreferenzen: always-hit, always-miss und not-classified. Die Cache-Persistenz-Analyse versucht, die klassische Cache-Analyse zu verbessern, in dem sie not-classified Speicherreferenzen als persistent klassifiziert und damit die Zahl der möglichen Cache-Fehlzugriffe beschränkt. Wir stellen mehrere neuartige auf abstrakter Interpretation basierende Cache-Persistenz-Analysen vor. Zwei basieren auf dem Konzept des Zählens von Konflikten, eine auf der May-Cache Analyse und die letzte kombiniert beide Ansätze miteinander. Alle Analysen korrigieren auch einen Fehler in der ursprünglichen Cache-Persistenz-Analyse von Ferdinand und Wilhelm. Für non-fully-timing-compositional Architekturen ist die Persistenz nicht einfach zu benutzen. Eine neue Pfadanalyse erlaubt die Benutzung der Persistenz auch für aktuelle Architekturen, bei denen sowohl Timing-Anomalien als auch Domino-Effekte auftreten können. Die vorgestellten Analysen werden innerhalb des industriell verwendeten WCET-Analysators aiT auf einer Reihe von Standard-Benchmark-Programmen und realen Avionic-Anwendungen evaluiert.
Link to this record: urn:nbn:de:bsz:291-scidok-50847
hdl:20.500.11880/26474
http://dx.doi.org/10.22028/D291-26418
Advisor: Wilhelm, Reinhard
Date of oral examination: 14-Feb-2013
Date of registration: 26-Feb-2013
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 
final.pdf1,12 MBAdobe PDFView/Open


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