INHALTSVERZEICHNIS
xix
6.2.3 Periodisches Scheduling ohne Reihenfolgebeschränkungen . 338
6.2.4 Periodisches Scheduling mit Reihenfolgebeschränkungen . . 346
6.2.5 Sporadische Ereignisse . . . . . . . . . . . . . . . . . . . . 346
6.3 Scheduling für unabhängige Jobs auf identischen Multiprozessoren . 346
6.3.1 Partitioniertes Scheduling . . . . . . . . . . . . . . . . . . 347
6.3.2 Globales Scheduling mit dynamischen Prioritäten . . . . . 350
6.3.3 Globales Scheduling für feste Job-Prioritäten . . . . . . . . 353
6.3.4 Globales Scheduling für feste Task-Prioritäten . . . . . . . . 356
6.4 Abhängige Jobs auf homogenen Multiprozessor-Systemen . . . . . 358
6.4.1 As-Soon-As-Possible-Scheduling . . . . . . . . . . . . . . . 358
6.4.2 As-Late-As-Possible-Scheduling . . . . . . . . . . . . . . . 360
6.4.3 List-Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 361
6.4.4 Optimales Scheduling mit Ganzzahliger Programmierung . . 363
6.5 Abhängige Jobs auf heterogenen Multiprozessoren . . . . . . . . . 365
6.5.1 Problem-Beschreibung . . . . . . . . . . . . . . . . . . . . 365
6.5.2 Statisches Scheduling mit lokalen Heuristiken . . . . . . . . 365
6.5.3 Statisches Scheduling mit Ganzzahliger Programmierung . . 369
6.5.4 Statisches Scheduling mit Evolutionären Algorithmen . . . . 369
6.5.5 Dynamisches und Hybrides Scheduling . . . . . . . . . . . 374
6.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
7 Optimierung
379
7.1 High-Level-Optimierungen . . . . . . . . . . . . . . . . . . . . . . 380
7.1.1 Einfache Schleifentransformationen . . . . . . . . . . . . . 380
7.1.2 Kachel-/Blockweise Verarbeitung von Schleifen . . . . . . . 382
7.1.3 Aufteilen von Schleifen . . . . . . . . . . . . . . . . . . . . 384
7.1.4 Falten von Feldern . . . . . . . . . . . . . . . . . . . . . . 386
7.1.5 Wandlung von Gleitkomma- in Festkommadarstellung . . . 387
7.2 Nebenläufigkeit von Tasks . . . . . . . . . . . . . . . . . . . . . . 388
7.3 Compiler für eingebettete Systeme . . . . . . . . . . . . . . . . . . 392
7.3.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
7.3.2 Energiegewahre Übersetzung . . . . . . . . . . . . . . . . . 393
7.3.3 Speicherarchitektur-gewahre Übersetzung . . . . . . . . . . 394
7.3.4 Zusammenführung von Compilern und Zeitanalyse . . . . . 403
7.4 Energieverwaltung und thermisches Management . . . . . . . . . . 405
7.4.1 Dynamische Spannungsskalierung (DVS) . . . . . . . . . . 405
7.4.2 Dynamische Leistungsverwaltung (DPM) . . . . . . . . . . 409
7.4.3 Verwaltung des thermischen Verhaltens . . . . . . . . . . . 409
7.5 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
8 Test
413
8.1 Anwendungsbereich . . . . . . . . . . . . . . . . . . . . . . . . . . 413
8.2 Testverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
8.2.1 Testmustererzeugung für Modelle auf Gatterebene . . . . . 415
8.2.2 Selbsttestprogramme . . . . . . . . . . . . . . . . . . . . . 416
xix
6.2.3 Periodisches Scheduling ohne Reihenfolgebeschränkungen . 338
6.2.4 Periodisches Scheduling mit Reihenfolgebeschränkungen . . 346
6.2.5 Sporadische Ereignisse . . . . . . . . . . . . . . . . . . . . 346
6.3 Scheduling für unabhängige Jobs auf identischen Multiprozessoren . 346
6.3.1 Partitioniertes Scheduling . . . . . . . . . . . . . . . . . . 347
6.3.2 Globales Scheduling mit dynamischen Prioritäten . . . . . 350
6.3.3 Globales Scheduling für feste Job-Prioritäten . . . . . . . . 353
6.3.4 Globales Scheduling für feste Task-Prioritäten . . . . . . . . 356
6.4 Abhängige Jobs auf homogenen Multiprozessor-Systemen . . . . . 358
6.4.1 As-Soon-As-Possible-Scheduling . . . . . . . . . . . . . . . 358
6.4.2 As-Late-As-Possible-Scheduling . . . . . . . . . . . . . . . 360
6.4.3 List-Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 361
6.4.4 Optimales Scheduling mit Ganzzahliger Programmierung . . 363
6.5 Abhängige Jobs auf heterogenen Multiprozessoren . . . . . . . . . 365
6.5.1 Problem-Beschreibung . . . . . . . . . . . . . . . . . . . . 365
6.5.2 Statisches Scheduling mit lokalen Heuristiken . . . . . . . . 365
6.5.3 Statisches Scheduling mit Ganzzahliger Programmierung . . 369
6.5.4 Statisches Scheduling mit Evolutionären Algorithmen . . . . 369
6.5.5 Dynamisches und Hybrides Scheduling . . . . . . . . . . . 374
6.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
7 Optimierung
379
7.1 High-Level-Optimierungen . . . . . . . . . . . . . . . . . . . . . . 380
7.1.1 Einfache Schleifentransformationen . . . . . . . . . . . . . 380
7.1.2 Kachel-/Blockweise Verarbeitung von Schleifen . . . . . . . 382
7.1.3 Aufteilen von Schleifen . . . . . . . . . . . . . . . . . . . . 384
7.1.4 Falten von Feldern . . . . . . . . . . . . . . . . . . . . . . 386
7.1.5 Wandlung von Gleitkomma- in Festkommadarstellung . . . 387
7.2 Nebenläufigkeit von Tasks . . . . . . . . . . . . . . . . . . . . . . 388
7.3 Compiler für eingebettete Systeme . . . . . . . . . . . . . . . . . . 392
7.3.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
7.3.2 Energiegewahre Übersetzung . . . . . . . . . . . . . . . . . 393
7.3.3 Speicherarchitektur-gewahre Übersetzung . . . . . . . . . . 394
7.3.4 Zusammenführung von Compilern und Zeitanalyse . . . . . 403
7.4 Energieverwaltung und thermisches Management . . . . . . . . . . 405
7.4.1 Dynamische Spannungsskalierung (DVS) . . . . . . . . . . 405
7.4.2 Dynamische Leistungsverwaltung (DPM) . . . . . . . . . . 409
7.4.3 Verwaltung des thermischen Verhaltens . . . . . . . . . . . 409
7.5 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
8 Test
413
8.1 Anwendungsbereich . . . . . . . . . . . . . . . . . . . . . . . . . . 413
8.2 Testverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
8.2.1 Testmustererzeugung für Modelle auf Gatterebene . . . . . 415
8.2.2 Selbsttestprogramme . . . . . . . . . . . . . . . . . . . . . 416