tailieunhanh - Digitale Hardware/ Software-Systeme- P23

Digitale Hardware/ Software-Systeme- P23:Getrieben durch neue Technologien und Anwendungen wird der Entwurf eingebetteter Systeme zunehmend komplexer. Dabei ist eine Umsetzung als Hardware/Software- System heutzutage der Stand der Technik. Die Minimierung von Fehlern im Entwurf dieser Systeme ist aufgrund deren Komplexit¨at eine der zentralen Herausforderungen unserer heutigen Zeit. | 434 7 Software-Verifikation rungsreihenfolge der Instruktionen zu einem bestmöglichen bzw. schlechtestmogli-chen Zeitverhalten fuhrt. Für die Analyse wird angenommen dass der Prozess den Prozessor exklusiv belegt der Prozessor lediglich eine skalare Funktionseinheit besitzt keine Interrupts unterstützt und kein Betriebssystem auf dem Prozessor ausgeführt wird. Weiterhin wird angenommen dass das Programm keine rekursiven Funktionsaufrufe beinhaltet keine dynamische Speicherallokation durchführt und die Schleifen im Programm beschrankt sind bzw. beschrankt werden. Grundlage für die Programmpfadanalyse bildet der Kontrollflussgraph GC VC EC eines Prozesses. Die Knoten in dem Kontrollflussgraphen stellen Berechnungen Grundblocke dar wahrend Kanten Kontrollflussabhangigkeiten darstellen. Auf Basis des Kontrollflussgraphen eines Prozesses lasst sich die engl. Worst Case Execution Time WCET formal definieren Definition WCET . Ein Prozess besteht aus n Grundblöcken wobei jeder Grundblock bi eine Ausführungszeit 8i hat und maximal x mal ausgeführt wird. Dann ist die WCET n nax 8i Xi i 1 Somit besteht die Aufgabe der Programmpfadanalyse darin herauszufinden wie oft jeder Grundblock auf einem Pfad der zu einer maximal langen Ausführungszeit gehort ausgeführt wird. Die Bestimmung der BCET kann analog formuliert werden Wie oft wird jeder Grundblock auf einem Pfad der zu einer minimalen Ausführungszeit gehort ausgeführt. Aufgrund dieser Analogie wird im Folgenden lediglich das WCET-Problem weiter betrachtet. Die zentrale Herausforderung bei der Programmpfadanalyse besteht allerdings darin dass die Anzahl der moglichen Ausführungspfade exponentiell anwachst. Ohne weitere Beschränkungen würde Gleichung beliebig anwachsen d. h. 3max rc. Aus diesem Grund wird die Anzahl der Ausführungen xi eines Basisblocks Bi beschrankt. Dabei werden zwei Arten von Beschränkungen unterschieden 1. Strukturelle Beschränkungen ergeben sich aus der Struktur des Kontrollflussgraphen. 2. .