Đang chuẩn bị liên kết để tải về tài liệu:
Digitale Hardware/ Software-Systeme- P9

Digitale Hardware/ Software-Systeme- P9: 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. Bereits heute wird mehr Aufwand in die Verifikation, also in die U¨ berpru¨fung der Korrektheit, eines eingebetteten Systems gesteckt als in den eigentlichen Entwurf | 232 5 Eigenschaftsprüfung Beispiel 5.4.13. Gegeben sei der markierte Graph in Abb. 5.34. Die Verzögerungszeit der Aktoren sei 3max ao 3max a4 2. Der Graph besitzt zwei Zyklen a0 a1 a2 a0 und a1 a2 a3 a1 . Die Iterationsintervallschranke Pmjn ergibt sich zu n 2 2 2 2 2 21 o Pmin max ---------3 3 Ein periodischer Ablaufplan mit P Pmjn ist in Abb. 5.34 zu sehen. Abb. 5.34. a markierter Graph und b periodischer Ablaufplan 5.5 Literaturhinweise Aufzählende und strukturelle Verfahren zur Verifikation von Petri-Netzen werden z. B. in 87 und 189 vorgestellt. In 189 sind auch Partialordnungsreduktionen und eine Erweiterung auf Modellprüfung für Petri-Netze ausführlich diskutiert. Dabei werden Verfahren unterschieden die auf der Auswahl von Referenzschaltfolgen basieren sowie auf entfaltungsbasierten Verfahren. Verfahren zur Auswahl von Referenzschaltfolgen sind u. a. die Stubborn-Set- und Sleep-Set-Methoden. Die Stubborn-Set-Methode wurde von Valmari vorgeschlagen 446 447 448 Die SleepSet-Methode wird ausführlich in 194 diskutiert. Weitere Arbeiten zur Partialordnungsreduktion durch Auswahl von Referenzschaltfolgen sind in 196 252 197 357 358 zu finden. Andere Verfahren zur Partialordnungsreduktion basierend auf der Entfaltung des Petri-Netzes sind in 155 317 318 265 beschrieben. 5.5 Literaturhinweise 233 Modellprüfung für temporale Logiken sind in 107 39 ausführlich beschrieben. CTL-Modellprüfung wurde unabhängig von Clarke und Emerson 97 und Queille und Sifakis 369 entwickelt. Der von Clarke und Emerson vorgeschlagene Algorithmus besitzt eine polynomielle Zeitkomplexitat in Formellange und Modellgroße. Einen verbesserten Algorithmus mit linearer Zeitkomplexitat stellten Clarke Emerson und Sistla in 98 vor. Einen ersten Algorithmus zur LTL-Modellprüfung stellten Lichtenstein und Pnueli 1985 in 304 vor. Ein alternativer Ansatz der auf Büchi-Automaten und Sprachinklusion basiert wurde von Vardi und Wolper vorgestellt 449 183 . Zusicherungsbasierte Eigenschaftsprüfung ist .