Digitale Hardware/ Software-Systeme - Part 21

594 Sachverzeichnis

relatives Komplement, 523 Mikroarchitektur 291 konstantes, 276 lineares, 276 Momentengraph mit Ausnahmebehandlung, 293, 311–312 mit dynamischer Instruktionsablaufpla- bin¨arer, siehe BMD nung, 293, 313–322 103, 107, 189, 323 323 mit Fließbandverarbeitung, 293–308 mit Multizyklen-Funktionseinheit, 293, 308–311 2 Monitor Monitorschaltung MPSoC 2 MTBDD 275 Multi-Processor System-on-Chip 530 Multigraph mit Sprungvorhersage, 293, 312–313 superskalare, 293 246

24 siehe MoC 43 Miter MoC 16 Modallogik model of computation Modell Nachbedingung st¨arkste, 431 Nebenl¨aufigkeit 531 Netzwerk heterogenes, 56 Modellpr¨ufer Boolesches, 525 Interpretation 526 508 Netzwerkkalk¨ul NFA 47 Definition, 47 247, 543 Normalform, konjunktive Null- ¨Aquivalenzproblem 129

OBDD 535 reduziertes, siehe ROBDD OBMD 277 CBMC, 449 CMC, 449 F-Soft, 450 Java Pathfinder, 449 SATABS, 449 SLAM, 449 SPIN, 449 VeriSoft, 449 ZING, 449 Modellpr¨ufung 26, 106, 156, 178–207 reduzierter, siehe ROBMD OFDD 538 Abstraktionsverfeinerung 425 reduziertes, siehe ROFDD 137 Off-Testfall OIDD 460 reduziert, siehe ROIDD OKFDD 539

reduziertes, siehe ROKFDD 137 6 382 331–345 On-Testfall open fault Operandenbereich Operator 422–425

modellogischer, siehe Pfadquantor temporaler, 73, 76 76 von Programmen BDD-basierte, 156 CTL, 179–185 existentielle, 200 explizite, 106, 156, 178–188 implizite, 106, 185 LTL, 185–188 SAT-basierte, 156 von Hardware von Programmen SE-LTL, 473–474 simulative, 27 symbolische, 106, 156, 197–207 76 76 197–199 199–207 76 Finally Globally Next Release Until 76

BDD-basierte SAT-basierte TCTL, 211–222 TLM, 476–484 universelle, 200 von Programmen, 422–431 14, 15 p-use 410, 412 Pareto-Optimum 9, 18 Partialordnung 524 Modulebene Moment

Sachverzeichnis 595

158, 172–178 Partialordnungsreduktion Partition 207–214 einer Menge, 523 Modellpr¨ufung 211–214 Pr¨ufung des Zeitverhaltens Zustandsklassen 523 208 Zustandsgleichung, 168 436 PEUF 357 Pfad Partitionsblock path segment simulation Periode 349 Petri-Netz 41, 91

135 138 135 138 134–139 138

definitionsfreier, 412 kritischer, 346 l¨angster, 346 Pr¨afix, 74 Suffix, 74 Pfadberechnung Pfadberechnungsanpassung Pfadbereich Pfadbereichsanpassung Pfadbereichstest Pfaderg¨anzung Pfadgewicht Pfadquantor 531 78

existentieller, 78 universeller, 78

17 449 Plattformmodell point to analysis Polynom 117

sparse recursive representation, 118 verschwindendes, 291 119 542 523 426 462 Anfangsmarkierung, 41 Beschr¨anktheit, 44, 164 Definition, 41 Dynamisierungsvorschrift, 41 Erreichbarkeitsmenge, 44 Flussrelation, 41 Folgemarkierung, 43 Grundzustand, 157, 165, 167 Inzidenzmatrix eines, 168 Kanten, 41 Kantengewichte, 41 Konflikt, 43 Konservativit¨at, 45, 170 Lebendigkeit, 44 Marke, 42 Markierung, 42 Markierungsfunktion, 42 Nachbereich eines Knotens, 42 Netzgraph, 41 Reversibilit¨at, 45, 156, 165, 167, 171 Schaltregel, 43 schwache Lebendigkeit, 44 Sicherheit, 44, 156 starke Lebendigkeit, 44, 167 Stelle, 41 528 Kapazit¨at einer 41

totes, 44 Transition, 41

174 43 528 174 298 nicht sichtbare Schalten einer sichtbare unabh¨angige 172 Polynomfunktion polynomieller Algorithmus Potenzmenge Pr¨adikatenabstraktion Pr¨adikatenintervall Pr¨adikatenlogik Alphabet, 528 Definitionen, 528–529 erster Ordnung, 23, 528 Formel, 528 atomare Terme, 528 Pr¨adikatensymbol Verifikation Ordnung eines, 298 uninterpretiertes, 298 Pr¨afix aufz¨ahlende strukturelle 157–167 157, 167–172

L¨ange, 90 Latenz, 90 Verklemmungsfreiheit, 44, 164 Vorbereich eines Knotens, 41 zeitbehaftetes, 45–47 526 526 45 prim¨arer Ausgang prim¨arer Eingang Problemgraph 208 348 iterativer, 349, 442 Produktautomat 143, 187 Definition Erreichbarkeitsgraph Feuerbereich Latenz 208 213–214

596 Sachverzeichnis

Programm Boolesches, 427 216 Programmabh¨angigkeitsgraph 375 217

Definition, 375 Programmanalyse siehe RTL siehe RTL 103, 131–132 statische, 416–422 Programmiersprache 132 Referenztestfall Regionen- ¨Aquivalenz Regionenautomat register transfer level Registertransferebene Regressionstest regul¨arer Ausdruck 59 Ausf¨uhrungsmodell, 59 sequentiell erweiterter, siehe SERE 11 control-driven demand-driven 59 59 Rekonvergenzmodell Relation

C, 59 deklarative, 59 imperative, 59 26, 416–431 524 antisymmetrische, 524 reflexive, 524 symmetrische, 524 transitive, 524

55 siehe Anforderung 548 Programmverifikation Prototyp 100 Prozesskalk¨ul Prozessor 439 superskalarer, 313 Pseudo-Boolesche Funktion requirement Resolution Ressourcenauslastung RMS-Algorithmus 444 ROBDD 150, 237, 535

Isomorphie, 535 ITE-Operator, 537

Belegung, 274 PSL 72, 83–88, 188 ¨Uberdeckung, 192 Boolesche Ebene, 83–84 einfache Teilmenge, 85 Monitor, 192–197 temporale Ebene, 83–87 Verifikationsebene, 83, 87–88 ROBMD 277 5 Robustheit ROFDD 538 ROIDD 460 ROKFDD 237, 243, 539 round robin siehe Round-Robin- 85 PSL-Eigenschaft Ptolemy 91 446 Algorithmus Round-Robin-Algorithmus RSM 453–454 430

8

8, 17, 18

QBF-Solver Qualit¨at 8 Qualit¨atsanforderung Qualit¨atsmaß 9, 17 Qualit¨atsmerkmal funktionales, 9 nichtfunktionales, 9 Quellknoten eines polaren Graphen 531 Distanzvektor, 453 dynamische Transitionen, 454 dynamische Zust¨ande, 453 Indexmenge, 453 Pfad, 454 Pr¨adikat, 453 Semantik, 454 Zustandsdiagramm 453 R¨ucksprungverfahren 545 453 konfliktgetriebenes, 549 147 dynamisches statisches RTC 508–514 RTL 15 R¨uckw¨artstraversierung rate-monotonic scheduling siehe RMS-Algorithmus siehe Gefahrlosigkeit siehe SMT siehe RTC 269 26, 113, 246, 356, 542–551 107, 132 safety SAT modulo theories SAT-Problem 542 SAT-Solver Schaltbereitschaft 43 103 Definition, 43, 46 real time calculus Record&Play-Algorithmus Referenzergebnis Referenzmodell Referenzstimulus 132

Sachverzeichnis 597

43 449 236 Schalten Schaltnetz Schaltung 536 53 asynchrone, 41 kombinatorische, 236, 242 shape analysis Sicherheit 44 sifting Signalverarbeitung Simulation Schaltungsmodell 27, 101–105 symbolische, 105, 237, 259, 357, 362 zuf¨allige iteratives, 259, 331 Schaltungsvereinfachung gesteuerte 102, 111–114 Simulator 104–105

dynamische, 358 168 236, 242 ereignisgesteuerter, 104 hybrider, 104 zyklenbasierter, 104 177–178 Schaltvektor Schaltwerk 26 Schleifeninvariante Schleifenkonstrukt 56 Schleifentransformation Sleep-Set-Methode SMT 26, 365, 552 SMT-Solver 551–556 indirekte, 552 14

globale, 380 Schnitt 152 Schnittmenge Schnittpunkt SDF-Graph Software-Entwurfsprozess Spannbaum 530 Spezifikation

523 152, 369 53 Definition als Petri-Netz, 53 Iteration, 226 Konsumptionsrate, 53 Produktionsrate, 53 Repetitionsvektor, 226 zeitbehafteter, siehe TSDF-Graph 91 SDF-Modell SE-LTL 472 5 15, 16, 37 ausf¨uhrbare, 38, 39, 59 Definition, 37 eindeutige, 38 formale, 37 informale, 37 korrekte, 38 vollst¨andige, 38 Spezifikationsfehler Sprache

Modellpr¨ufung, 473–474 Semantik, 472 Syntax, 472 einer temporalen Struktur, 467 eines B¨uchi-Automaten, 186 30 531 106 siehe SE-LTL Semaphore Senkeknoten eines polaren Graphen sequential extended regular expression 41

siehe SERE 43 358 101 Sequentialit¨at Sequenzautomat SERE 84, 192 17 175–177 siehe Haftfehler Sprachinklusion state/event-LTL Stellen-Transitions-Netz 171 Stelleninvariante Steuerbarkeit 109, 110 Stimulation Strukturmodell Stubborn-Set-Methode stuck-at fault stuck-at fault model siehe Haftfehlermo- dell 548

Subsumtion SUV 102 synchroner Datenflussgraph siehe Abz¨ahlungswiederholung, 85 Bereichswiederholung, 85 Definition, 84 Fusion, 84 GOTO-Operator, 85 Konkatenation, 84 L¨angendurchschnitt, 84 SDF-Graph 43 516 518 Synchronisation synchronous dataflow graph siehe SDF-Graph Servicefunktion Servicekennlinie obere, 510 untere, 510 Synthese 4, 15–18 Shannon-Zerlegung 243, 276, 534

598 Sachverzeichnis

System

siehe SUV 376 latenzinsensitives, 345 system under verification Systemabh¨angigkeitsgraph SystemC 28, 60–67, 451

Interpretation, 120 Kanonizit¨at, 124 Kompositionsoperatoren, 284–286 Minimalit¨at, 125 Multiplikation, 285–286 normalisiert, 123 Normalisierung, 122 Reduktion, 120 reduziertes, 122 Verschmelzungsregel, 122 523 Teilmenge

echte, 523 nichtnegative, 523 positive, 523 als LTS, 468–472 Ereignis, 66 Kanal, 62, 63 Methode, 62 Modellpr¨ufung, 466–476 Modul, 60 Port, 60, 61 Prozess, 62 Signal, 62 Thread, 62 191, 196 68 Teilmengenkonstruktion Temporale Struktur 73–75, 163

SystemCoDesigner Systemebene 15 SysteMoC 60, 68–72

als B¨uchi-Automat, 186 attributierte, siehe LTS Definition, 73 Pfad, 74, 467 Sprache der, 467 zeitbehaftete, siehe TTS 25 Aktion, 68 Anfangsmarke, 69 Konsumptionsrate, 68 Modellpr¨ufung, 452–466 Produktionsrate, 68 Repr¨asentation des Zustandsraums, 452–464 102 Temporallogik Test 5 Testbench Testfall 101

W¨achterfunktion, 68 Zustand, 453 Systemsynthese 15

192, 233 334 Tableau-Technik Taktdom¨ane Taktzustand

globaler, 336 440 datenflussorientierter, 391, 400, 410–415 funktionsorientierter, 391–400 gerichteter, 102 kontrollflussorientierter, 391, 400–410 strukturorientierter, 391, 400–415 zuf¨alliger, 102 zustandsorientierter, 396–400 101–102 528

118

tardiness Tautologie Taylor-Expansions-Diagramm siehe TED Taylor-Reihen-Entwicklung Taylorsches Theorem 124 TCTL 89 Testfallgenerierung gerichtete, 102 zuf¨allige, 102 zur Hardware-Verifikation, 246 zur Software-Verifikation, 391–415 siehe ATPG 253 112 Testmustergenerierung Testvektor Testvorschrift Theorembeweis 447 automatischer, 25 106–107 Theorembeweiser Theorie

447 siehe TCTL Semantik, 90 Syntax, 89 Zeitschranke, 89 TDMA-Ablaufplanung TED 120–129, 283 Addition, 284–285 Definition, 120 Eindeutigkeit, 124 Eliminationsregel, 121 geordnetes, 122 Hintergrund-, 26, 365, 551 time division multiple access timed computation tree logic TLM 28, 476

Sachverzeichnis 599

103, 391 401 Definition, 478 Eigenschaftspr¨ufung, 484–490 Initiatormodul, 478 Modellpr¨ufung, 476–484 Targetmodul, 478 Transaktion, 476–478 Transaktion 20

blockierende, 476 nichtblockierende, 476 452 siehe TLM 515 346 Transaktionsebene Transaktionsebenenmodell Transferfunktion Transferzeit Transition einfacher strukturorientierte, 103 Zustands-, 397 Zweig-, 402 ¨Uberdeckungsmaß ¨Uberdeckungstest all c-uses-, 414 all c-uses/some p-uses-, 414–415 all p-uses/some c-uses-, 415 all defs-, 413 all p-uses-, 414 all p-uses/some c-uses-, 415 all uses-, 415 Anweisungs-, 401–402 Bedingungs-, 404–406 404–405 Bedingungs-/Entscheidungs-, 405 modifizierter 448

222–232 Aktivierbarkeit, 44, 165 Lebendigkeit, 44 neuaktivierte, 46 Schaltbereitschaft, 43 tote, 44 TSDF-Graph Aktor, 222 Datenkontext-, 448 defs/uses-, 413–415 Mehrfach-Bedingungs-, 406 406 einfache 223 Pfad-, 407–410 strukturierter 408–410

required k-tuples, 448 Zweig-, 402–404 225

47, 49 103 ¨Ubereinstimmungsproblem 294 ¨Ubergangsfunktion 48, 220, 295 erweiterte, 142 ¨Ubergangsrelation ¨Uberpr¨ufungsstrategien ¨Uberdeckung Zusicherungs-, 391 Verz¨ogerungszeit Aktordurchsatz, 226 Anfangsmarkierung, 223 Ausf¨uhrung, 225 selbstplanende Durchsatz, 226–228 Kanal, 222 Konsumptionsrate, 223 Pr¨ufung des Zeitverhaltens, 222–232 Produktionsrate, 223 Zustand, 223 TTS 89, 213

siehe II minimale Latenz, 213 mit exakten Verz¨ogerungen, 89 UIP 550 UML 91 Unabh¨angigkeitsintervall Unabh¨angigkeitsintervallpartition siehe 55 Turing- ¨Aquivalenz Turing-Maschine 24 544 98, 344 ¨Uberapproximation ¨Uberdeckung 392–396 IIP unit propagtion 342 Unterapproximation Unvollst¨andigkeitssatz 24 Ursache-Wirkungs-Analyse Ursache-Wirkungs-Graph 393

13 5, 38, 109 ¨Ubergangs-, 397 Anweisungs-, 401 Bedingungs-/Entscheidungs-, 405 Ereignis-, 397 funktionsorientierte, 103 Mehrfach-Bedingungs-, 406 406 minimale Pfad-, 407 V-Modell Validierung Variablendefinition globale, 412 lokale, 412 Variablenordnung 119 strukturierte 408

600 Sachverzeichnis

Architekturmodellierung, 436–438 Programmpfadanalyse, 433–436 Variablenzugriff globaler, 412 lokaler, 411 Wertebereich 523 abstrakter, 419 17, 18 422 37 Vereinigungsmenge Verfeinerung Verhalten Verhaltensmodell 16 419 419, 421

15 5

21, 95–97 374 536 ausf¨uhrbares, 59 formales, 41 Verhaltenssynthese Verifikation Verifikationsaufgabe Verifikationsbereich Verifikationsmethode 22, 99–107 siehe WCET lineare Kongruenzen nichtrelationaler relationaler Intervall-, 419 Kongruenz-, 419, 421 konkreter, 419 Parit¨ats-, 421 Vorzeichen-, 419 window permutation worst case execution time

X-Diagramm 35 der Synthese, 16 f¨ur die Verifikation, 20–22

Y-Diagramm 35, 490

Zeitanalyse 95 11–22 345 auf Systemebene, 490–520 103–104, 400 499–508 95, 97–99 kompositionale modulare 508–520 44

dynamische, 348 f¨ur Hardware, 345 348–351 diversifizierende, 130 formale, 99, 105–107 hybride, 101, 107 simulative, 100–105 unvollst¨andige, 99, 100 vollst¨andige, 99 Verifikationsmethodik Verifikationsprozess Verifikationsvollst¨andigkeit Verifikationsziel Verklemmung Verschmelzungspunkt Verschmelzungsregel Versetzungsfunktion 271 535, 538 462 auf Architekturebene auf Logikebene 345–348 inverse, 466 Verzweigung 53

Hardware, 356 kompositionale, 499–508 Schaltung als Kontrollstruktur, 56 544 synchroner 345–351 Verzweigungsliteral Verzweigungsstrategie

Software, 431–448 statische, 345 symbolische, siehe SymTA/S System latenzinsensitives 351–356 1

Systemebene simulative 492–499 DLCS, 545 DLIS, 545 MOM, 546 VSIDS, 546 Vielzweckrechner Volladdierer 29 Vollst¨andigkeitskriterium 400 Vorbedingung WCET, 432–436 Zeitschranke, 491 145 obere untere 491 491 schw¨achste, 431 Vorw¨artstraversierung VPC 492 Zeitbewertungsmodell 530 439 Zeitbewertungsnetzwerk, 512 45 259 Wald Wartezeit WCET 432 WCET-Analyse 432–438 Zeitschranke Zeitschrittsimulation Zeitstruktur 220

Sachverzeichnis 601

219 Zeitzone Zerlegung momentenbasierte, 275 219 105, 172 Zonenautomat Zur¨uckverfolgung 249, 545 regul¨arer, siehe RSM Zustandsdiagramm 48 Zustandsexplosion 32 Zustandsraumexplosion Zustandsraumreduktion

chronologische, 548 nichtchronologische, 545, 549 durch Schleifenabwicklung, 424–425 144–151

27, 88, 111, 391 92, 188 Zusicherung Zusicherungssprache Zustand Zustandsraumtraversierung r¨uckw¨artsgerichtete, 147 symbolische, 148–151 vorw¨artsgerichtete, 145

Zuverl¨assigkeit 6 Zuweisungsfunktion 462 ablehnender, 190 abstrakter, 427 akzeptierender, 186, 190 inverse, 466 142, 143 Zweig 48 Zustands¨aquivalenz Zustands¨ubergang Zustandsautomat primitiver, 403