E - Lehrstuhl 12

 Documents

 34 views
of 104
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Informatik 12 | DAES Compilerbau Wintersemester 2010 / 2011 Dr. Heiko Falk Technische Universität Dortmund Lehrstuhl Informatik 12 Entwurfsautomatisierung für…
Share
Transcript
Informatik 12 | DAES Compilerbau Wintersemester 2010 / 2011 Dr. Heiko Falk Technische Universität Dortmund Lehrstuhl Informatik 12 Entwurfsautomatisierung für Eingebettete Systeme Informatik 12 | DAES Kapitel 8 Code-Optimierung © H. Falk 8 – Code-Optimierung Folie 2 / 104 Informatik 12 | DAES Gliederung der Vorlesung  Kapitel 1: Compiler – Abhängigkeiten und Anforderungen  Kapitel 2: Interner Aufbau von Compilern  Kapitel 3: Lexikalische Analyse (Scanner)  Kapitel 4: Syntaktische Analyse (Parser)  Kapitel 5: Semantische Analyse  Kapitel 6: Instruktionsauswahl  Kapitel 7: Register-Allokation  Kapitel 8: Code-Optimierung  HIR: Parallelisierung für Homogene Multi-DSPs  LIR: Generierung von Bit-Paket Operationen für NPUs  LIR: Optimierungen für Scratchpad-Speicher  Kapitel 9: Ausblick © H. Falk 8 – Code-Optimierung Folie 3 / 104 Informatik 12 | DAES Parallelisierung für Multi-DSPs  Material freundlicherweise zur Verfügung gestellt von: Björn Franke und Michael O’Boyle University of Edinburgh, UK School of Informatics © H. Falk 8 – Code-Optimierung Folie 4 / 104 Informatik 12 | DAES Parallelisierung für Multi-DSPs  Motivation:  Performance-Anforderungen eines gesamten Systems über- steigen oft Fähigkeiten eines einzelnen Prozessors. (z.B. Radar, Sonar, medizinische Bildverarbeitung, HDTV, ...)  Parallel arbeitende DSPs stellen hinreichend Performance zur Verfügung, aber...  Wenig bis keine Hardware-Unterstützung für parallele Ausführung  Noch weniger Unterstützung paralleler Programmier- techniken durch Entwurfswerkzeuge.  Existierende Quellcodes oft in low-level Stil programmiert, welcher Parallelisierung erschwert. © H. Falk 8 – Code-Optimierung Folie 5 / 104 Informatik 12 | DAES Parallelisierende Compiler  Spezialgebiet „High Performance Computing”:  Seit über 25 Jahren Forschung zu Vektorisierenden Compilern  Traditionell Fortran-Compiler  Derartige Vektorisierende Compiler i.d.R. für Multi-DSPs nicht geeignet, da Annahmen über Speicher-Modell unrealistisch:  Kommunikation zwischen Prozessen via gemeinsamen Speicher (shared memory)  Speicher hat nur einen einzelnen gemeinsamen Adressraum  Caches können dezentral vorkommen, Cache-Kohärenz aber in HW gelöst  De Facto keine parallelisierenden Compiler für Multi-DSPs © H. Falk 8 – Code-Optimierung Folie 6 / 104 Informatik 12 | DAES Multi-DSPs DSP Core 0 DSP Core X Mem Mem Mem Mem Bank 1 Bank 2 Bank 1 Bank 2 Bus  Mehrfache Adressräume: Intern 1 & 2, Extern, Entfernter DSP-Core Externer  Nutzung interner Speicher: Speicher Höhere Bandbreite, geringere Latenzzeit  Nutzung entfernter Speicher: ID des entfernten DSPs muss bekannt sein © H. Falk 8 – Code-Optimierung Folie 7 / 104 Informatik 12 | DAES Ablauf der Parallelisierung  Programm-Wiederherstellung  Entfernen „ungewünschter” low-level Konstrukte im Code  Ersetzung durch high-level Konstrukte  Entdeckung von Parallelität  Identifizierung parallelisierbarer Schleifen  Partitionierung und Zuordnung von Daten  Minimierung des Kommunikations-Overheads zwischen DSPs  Erhöhung der Lokalität von Speicherzugriffen  Minimierung der Zugriffe auf Speicher entfernter DSPs  Optimierung der Speicher-Transfers  Nutzung von Direct Memory Access (DMA) für Block-Transfers © H. Falk 8 – Code-Optimierung Folie 8 / 104 Informatik 12 | DAES Code-Beispiel für 2 parallele DSPs /* Array-Deklarationen */ int A[16], B[16], C[16], D[16]; /* Deklaration & Initialisierung von Zeigern */ int *p_a = A, *p_b = &B[15], *p_c = C, *p_d = D; /* Schleife über alle Array-Elemente */ for (i = 0; i < 16; i++) *p_d++ = *p_c++ + *p_a++ * *p_b--;  Low-level Array-Zugriffe über Zeiger; explizite Zeiger- Arithmetik (Auto-Increment Adressierung, vgl.  Kapitel 1)  Nachteilig für Parallelisierung, da ad hoc keine Struktur in Array-Zugriffen erkenn- und analysierbar. © H. Falk 8 – Code-Optimierung Folie 9 / 104 Informatik 12 | DAES Programm-Wiederherstellung /* Array-Deklarationen */ int A[16], B[16], C[16], D[16]; /* Schleife über alle Array-Elemente */ for (i = 0; i < 16; i++) D[i] = C[i] + A[i] * B[15-i];  Ersetzen der Zeiger-Zugriffe durch explizite Array-Operatoren []  Struktur der Array-Zugriffe besser erkennbar, für nachfolgende Analysen zugänglicher © H. Falk 8 – Code-Optimierung Folie 10 / 104 Informatik 12 | DAES Programm-Wiederherstellung /* Array-Deklarationen */ int A[16], B[16], C[16], D[16]; /* Schleife über alle Array-Elemente */ for (i = 0; i < 16; i++) D[i] = C[i] + A[i] * B[15-i];  Eindimensionale „flache” Arrays für Parallelisierung für Multi- DSP Architektur zu unstrukturiert.  Aufteilung der Arrays auf verfügbare parallele DSPs unklar. © H. Falk 8 – Code-Optimierung Folie 11 / 104 Informatik 12 | DAES Daten-Partitionierung /* Partitionierte Array-Deklarationen */ int A[2][8], B[2][8], C[2][8], D[2][8]; /* Schleife über alle Array-Elemente */ for (i = 0; i < 16; i++) D[i/8][i%8] = C[i/8][i%8] + A[i/8][i%8] * B[(15-i)/8][(15-i)%8];  Neue zweidimensionale Array-Deklarationen  Erste Dimension entspricht Anzahl paralleler DSPs  Ursprüngliche flache Arrays in disjunkte Bereiche zerlegt, die unabhängig voneinander bearbeitet werden können. © H. Falk 8 – Code-Optimierung Folie 12 / 104 Informatik 12 | DAES Daten-Partitionierung /* Partitionierte Array-Deklarationen */ int A[2][8], B[2][8], C[2][8], D[2][8]; /* Schleife über alle Array-Elemente */ for (i = 0; i < 16; i++) D[i/8][i%8] = C[i/8][i%8] + A[i/8][i%8] * B[(15-i)/8][(15-i)%8];  Sehr kostspielige, komplexe Adressierung notwendig.  Grund: Arrays sind mehrdimensional; Schleifenvariable i, mit der Arrays indiziert werden, läuft aber sequenziell.  Sog. Zirkuläre Adressierung (circular buffer addressing). © H. Falk 8 – Code-Optimierung Folie 13 / 104 Informatik 12 | DAES Strip Mining der i-Schleife /* Partitionierte Array-Deklarationen */ int A[2][8], B[2][8], C[2][8], D[2][8]; /* Verschachtelte Schleife über alle Array-Elemente */ for (j = 0; j < 2; j++) for (i = 0; i < 8; i++) D[j][i] = C[j][i] + A[j][i] * B[1-j][7-i];  Aufteilen des sequenziellen Iterationsraums von i in zwei unabhängige zweidimensionale Iterationsräume  Iterationsräume der neuen verschachtelten Schleifen spiegeln Daten-Layout wieder  Nur noch lineare Ausdrücke zur Array-Adressierung © H. Falk 8 – Code-Optimierung Folie 14 / 104 Informatik 12 | DAES Strip Mining der i-Schleife /* Partitionierte Array-Deklarationen */ int A[2][8], B[2][8], C[2][8], D[2][8]; /* Verschachtelte Schleife über alle Array-Elemente */ for (j = 0; j < 2; j++) for (i = 0; i < 8; i++) D[j][i] = C[j][i] + A[j][i] * B[1-j][7-i];  Wie kann dieser Code für zwei DSPs parallelisiert werden? © H. Falk 8 – Code-Optimierung Folie 15 / 104 Informatik 12 | DAES Parallelisierung (für Prozessor 0) /* Definition der Prozessor-ID */ #define MYID 0  Einfügen einer expli- /* Partitionierte Array-Deklarationen */ ziten Prozessor-ID int A[2][8], B[2][8], C[2][8], D[2][8]; /* Simple Schleife über alle Array-Elemente für DSP Nr. MYID */ for (i = 0; i < 8; i++) D[MYID][i] = C[MYID][i] + A[MYID][i] * B[1-MYID][7-i];  Array-Adressierung unter Verwendung der Prozessor-ID  Bei N parallelen Prozessoren Generierung von N verschiede- nen HIR-Codes mit jeweils unterschiedlichen Prozessor-IDs © H. Falk 8 – Code-Optimierung Folie 16 / 104 Informatik 12 | DAES Parallelisierung (für Prozessor 0) /* Definition der Prozessor-ID */ #define MYID 0 /* Partitionierte Array-Deklarationen */ int A[2][8], B[2][8], C[2][8], D[2][8]; /* Simple Schleife über alle Array-Elemente für DSP Nr. MYID */ for (i = 0; i < 8; i++) D[MYID][i] = C[MYID][i] + A[MYID][i] * B[1-MYID][7-i];  Mit dieser Struktur ist klar, welcher Code auf welchem DSP läuft.  Unklar ist, wie die Arrays auf lokale Speicherbänke der DSPs oder auf externe Speicher verteilt werden, und wie Zugriffe auf Speicherbänke entfernter DSPs geschehen. © H. Falk 8 – Code-Optimierung Folie 17 / 104 Informatik 12 | DAES Feld-Deskriptoren  Zweidimensionales Feld A[2][8] wird entlang erster Dimension in 2 Teil-Arrays A0 und A1 zerlegt.  Jedes Teil-Array An wird in Speicher von Prozessor n abgelegt.  Ursprüngliche 2-dimensionale Array-Zugriffe müssen mit Hilfe von Deskriptoren auf A0 und A1 umgelenkt werden. A[0][5] A[0][5] DSP 0 DSP 1 Feld-Deskriptoren A0 | A1 A0 | A1 Teil-Array Teil-Array A0[0...7] A1[0...7] © H. Falk 8 – Code-Optimierung Folie 18 / 104 Informatik 12 | DAES Speicher-Aufteilung (für Prozessor 0) /* Definition der Prozessor-ID */  Felder in DSP-internem #define MYID 0 und entferntem Speicher /* Partitionierte Array-Deklarationen & Feld-Deskriptoren */ int A0[8]; extern int A1[8]; int *A[2] = { A0, A1 }; int B0[8]; extern int B1[8]; int *B[2] = { B0, B1 }; ... /* Simple Schleife über alle Array-Elemente für DSP Nr. MYID */ for (i = 0; i < 8; i++) D[MYID][i] = C[MYID][i] + A[MYID][i] * B[1-MYID][7-i];  Array-Zugriffe über Deskriptoren in unveränderter Syntax © H. Falk 8 – Code-Optimierung Folie 19 / 104 Informatik 12 | DAES Speicher-Aufteilung (für Prozessor 0) /* Definition der Prozessor-ID */ #define MYID 0 /* Partitionierte Array-Deklarationen & Feld-Deskriptoren */ int A0[8]; extern int A1[8]; int *A[2] = { A0, A1 }; int B0[8]; extern int B1[8]; int *B[2] = { B0, B1 }; ... /* Simple Schleife über alle Array-Elemente für DSP Nr. MYID */ for (i = 0; i < 8; i++) D[MYID][i] = C[MYID][i] + A[MYID][i] * B[1-MYID][7-i];  Deskriptor-Zugriff auf lokale Arrays wegen zus. Indirektion ineffizient.  Scheduling-Probleme: A[i][j] kann unterschiedliche Latenzzeit haben, wenn i lokalen oder entfernten Speicher referenziert. © H. Falk 8 – Code-Optimierung Folie 20 / 104 Informatik 12 | DAES Lokalitätserhöhung von Feld-Zugriffen /* Definition der Prozessor-ID */ #define MYID 0 /* Partitionierte Array-Deklarationen & Feld-Deskriptoren */ int A0[8]; extern int A1[8]; int *A[2] = { A0, A1 }; int B0[8]; extern int B1[8]; int *B[2] = { B0, B1 }; ... /* Simple Schleife über alle Array-Elemente für DSP Nr. MYID */ for (i = 0; i < 8; i++) D0[i] = C0[i] + A0[i] * B[1-MYID][7-i];  Direkte Zugriffe auf lokale Felder; wann immer möglich, auf Zugriff via Deskriptoren verzichten.  Maximale Ausnutzung der hohen Bandbreite lokaler Speicher. © H. Falk 8 – Code-Optimierung Folie 21 / 104 Informatik 12 | DAES Lokalitätserhöhung von Feld-Zugriffen /* Definition der Prozessor-ID */ #define MYID 0 /* Partitionierte Array-Deklarationen & Feld-Deskriptoren */ int A0[8]; extern int A1[8]; int *A[2] = { A0, A1 }; int B0[8]; extern int B1[8]; int *B[2] = { B0, B1 }; ... /* Simple Schleife über alle Array-Elemente für DSP Nr. MYID */ for (i = 0; i < 8; i++) D0[i] = C0[i] + A0[i] * B[1-MYID][7-i];  8 sequenzielle Zugriffe auf aufeinanderfolgende Array- Elemente in entferntem Speicher  Ineffizient, da 8 komplette Bus-Zyklen benötigt werden © H. Falk 8 – Code-Optimierung Folie 22 / 104 Informatik 12 | DAES Einfügen von DMA Block-Transfers /* Definition der Prozessor-ID */ #define MYID 0 /* Partitionierte Array-Deklarationen & Feld-Deskriptoren */ int A0[8]; extern int A1[8]; int *A[2] = { A0, A1 }; int B0[8]; extern int B1[8]; int *B[2] = { B0, B1 }; ...  Blockweises Laden eines /* Temporärer Puffer für DMA */ lokalen Puffers aus ent- int temp[8]; ferntem Speicher per DMA DMA_get( temp, &(B[1-MYID]), 8 * sizeof( int ) ); /* Simple Schleife über alle Array-Elemente für DSP Nr. MYID */ for (i = 0; i < 8; i++)  Feld-Zugriffe in Schleife nur D0[i] = C0[i] + A0[i] * temp[7-i]; noch auf lokalen Speicher © H. Falk 8 – Code-Optimierung Folie 23 / 104 Informatik 12 | DAES Durchführung der Parallelisierung  Multi-DSP Hardware  4 parallele Analog Devices TigerSHARC TS-101 @250 MHz  768 kB lokales SRAM pro DSP, 128 MB externes DRAM  Parallelisierte Benchmark-Programme  DSPstone: kleine DSP-Routinen, geringe Code-Komplexität  UTDSP: komplexe Anwendungen, rechenintensiver Code  Ergebnisse: Laufzeiten  für rein sequenziellen Code auf 1 DSP laufend  für Code nach Programm-Wiederherstellung  für Code nach Daten-Partitionierung und Zuordnung  für Code nach Erhöhung der Lokalität & DMA © H. Falk 8 – Code-Optimierung Folie 24 / 104 Informatik 12 | DAES Ergebnisse – DSPstone 7 Sequenziell 6 Programm-Wiederherstellung Partitionierung & Zuordnung 5 Lokalität & DMA Speedup 4 3 2 1 0 fir s im 1 2 n es lm s rix rix io te 2d at ut at at da pd fir ol m m up nv _u _ co al ex re pl n_ m co n_ © H. Falk 8 – Code-Optimierung Folie 25 / 104 Informatik 12 | DAES Ergebnisse – UTDSP 6 Sequenziell Programm-Wiederherstellung 5 Partitionierung & Zuordnung Lokalität & DMA 4 Speedup 3 2 1 0 IIR R IR m s er l) t e) ec es FI al ra SF lt rg m et Fi pr og (la LM (s D m EG st ge T Co T Hi UL UL JP Ed M M © H. Falk 8 – Code-Optimierung Folie 26 / 104 Informatik 12 | DAES Diskussion der Ergebnisse  Durchschnittliche Gesamt-Speedups:  DSPstone: Faktor 4,28  UTDSP: Faktor 3,65  Alle Benchmarks: Faktor 3,78  Sehr erstaunlich: Wie kann für DSPstone ein Speedup über Faktor 4 erzielt werden, wenn eine Parallelisierung für 4 DSPs erfolgt? © H. Falk 8 – Code-Optimierung Folie 27 / 104 Informatik 12 | DAES Gründe für Super-Lineare Speedups  Super-Lineare Speedups > 4 bei 4 parallelen DSPs:  Parallelisierter Code ist nachfolgenden Compiler-Optimierun- gen evtl. besser zugänglich als originaler sequentieller Code.  Beispiel: Sequenzielle i-Schleife (Folie 13): 16 Iterationen. Auf 2 DSPs parallelisierte i-Schleife (Folie 14): 8 Iterationen. Parallelisierte Schleifen u.U. Kandidaten für Loop Unrolling: ; for (i = 0; i < 8; i++) ; 8-mal ; ... ;  Abgerollte Schleife ohne Sprünge! Keine Delay-Slots, Sprung-Vorhersage liegt stets richtig. © H. Falk 8 – Code-Optimierung Folie 28 / 104 Informatik 12 | DAES Gliederung der Vorlesung  Kapitel 1: Compiler – Abhängigkeiten und Anforderungen  Kapitel 2: Interner Aufbau von Compilern  Kapitel 3: Lexikalische Analyse (Scanner)  Kapitel 4: Syntaktische Analyse (Parser)  Kapitel 5: Semantische Analyse  Kapitel 6: Instruktionsauswahl  Kapitel 7: Register-Allokation  Kapitel 8: Code-Optimierung  HIR: Parallelisierung für Homogene Multi-DSPs  LIR: Generierung von Bit-Paket Operationen für NPUs  LIR: Optimierungen für Scratchpad-Speicher  Kapitel 9: Ausblick © H. Falk 8 – Code-Optimierung Folie 29 / 104 Informatik 12 | DAES Wiederholung: Datenflussgraphen Datenflussgraph:  Knoten repräsentiert eine Operation  Kanten zwischen Knoten repräsentieren Definitionen (DEFs) und Benutzungen (USEs) von Daten. Genauigkeit eines DFGs:  Auf LIR-Ebene repräsentiert ein DFG-Knoten eine Maschinen- Operation  Da die Operanden von Maschinen-Operationen i.d.R. Prozessor- Register sind, repräsentieren Kanten den Datenfluss durch ganze Register. © H. Falk 8 – Code-Optimierung Folie 30 / 104 Informatik 12 | DAES DFGs & Bit-Pakete Bit-Pakete:  Menge aufeinanderfolgender Bits  beliebiger Länge  an beliebiger Position startend  u.U. Wortgrenzen überschreitend DFGs und Bit-Pakete:  DFGs modellieren Datenfluss auf Basis von atomaren Registern  Information über unregelmäßig angeordnete Teilbereiche von Registern werden nicht bereitgestellt.  Klassische DFG-basierte Verfahren i.d.R. ungeeignet zur Erzeugung von Bit-Paket Operationen! © H. Falk 8 – Code-Optimierung Folie 31 / 104 Informatik 12 | DAES Beispiel: TPM und Bit-Pakete  Zusammengesetzte Regel dreg: tpm_BinaryExpAND( tpm_BinaryExpSHR( dreg, const ), const ) kann Ausdruck (c >> 4) & 0x7 überdecken und effiziente Operation EXTR.U d_0, d_c, 4, 3 generieren.  Aber: TPM stößt an Grenzen, wenn Muster komplexer werden: Zahlen 4 / 0x7 nicht als Konstanten, sondern als Inhalt von Variablen vorliegend? Andere Operator-Kombinationen als & / >> zum Erzeugen und Einfügen von Bit-Paketen in C? Baum-Grammatik würde schnell ausufern und trotzdem relativ schlechten Code erzeugen! © H. Falk 8 – Code-Optimierung Folie 32 / 104 Informatik 12 | DAES Lösungsansatz  Durchführen einer konventionellen Instruktionsauswahl:  Baum-Grammatik erzeugt LIR mit Maschinen-Operationen, die atomare Register als Operanden verwenden  Baum-Grammatik erzeugt keine Bit-Paket Operationen  Über Regeln dreg: tpm_BinaryExpAND( dreg, const ) dreg: tpm_BinaryExpSHR( dreg, const ) würde Ausdruck (c >> 4) & 0x7 naiv überdeckt durch SH d_0, d_c, -4; AND d_1, d_0, 7;  Nachträgliche LIR-Optimierung:  Erkennt Operationen, die Bit-Pakete extrahieren / einfügen und erzeugt entsprechende extr / insert Bit-Paket Operationen © H. Falk 8 – Code-Optimierung Folie 33 / 104 Informatik 12 | DAES Klassische Datenfluss-Analyse Problem:  Klassische Datenfluss-Analysen (DFA) erlauben Aussagen über Fluss von Information, bezogen auf die Register-Ebene:  Welche Operation benutzt / definiert ein bestimmtes Datum, vorliegend in einem bestimmten Register?  Zwischen welchen Operationen bestehen Daten- Abhängigkeiten?  Klassische Datenfluss-Analysen treffen keinerlei Aussage über den Wert von Information, d.h. den potenziellen Wert, den ein Register zu einem bestimmten Zeitpunkt haben kann. den potenziellen Wert, den ein Teil eines Registers zu einem bestimmten Zeitpunkt haben kann. © H. Falk 8 – Code-Optimierung Folie 34 / 104 Informatik 12 | DAES Bitgenaue Wertfluss-Analyse Wertfluss-Analyse (WFA):  Analysiert ebenso wie DFA den Datenfluss,  nimmt aber zusätzlich Abschätzungen über den Inhalt der an der Datenverarbeitung beteiligten Speicherzellen vor. Bitgenaue Daten- und Wertfluss-Analyse (BDWFA):  Wertfluss-Abschätzung wird für jedes einzelne Bit der an der Datenverarbeitung beteiligten Speicherzellen vorgenommen.  Erlaubt Aussagen über den potenziellen Wert jedes einzelnen Bits einer Speicherzelle zu einem bestimmten Zeitpunkt.  Im folgenden: Präsentation einer BDWFA mit mehrwertiger Logik für Register als Speicherzellen. © H. Falk 8 – Code-Optimierung Folie 35 / 104 Informatik 12 | DAES Daten- und Wertflussgraph (DWFG) Definition (Daten- und Wertflussgraph): Sei F eine LIR-Funktion. Der Daten- und Wertflussgraph (DWFG) zu F ist ein gerichteter Graph DWFG = (V, E, d, u) mit  Knotenmenge V identisch mit DFG-Definition (vgl.  Kapitel 6)  Seien opi(pi,1, ..., pi,n) und opj(pj,1, ..., pj,m) zwei Operationen aus F mit Parametern pi,x bzw. pj,y, und vi und vj die zu opi und opj gehörenden Knoten. Für jede Benutzung eines Registers r durch pj,y, das von pi,x definiert wird, existiert eine Kante e = (vi, vj)  E.  d und u stellen bitgenaue Wert-Informationen zu Kanten e  E bereit (Down- und Up-Werte). Sei r das Register, das durch e modelliert wird, und r sei k Bits breit. Dann sind d und u Abbildungen d | u: E  L4k mit L4 als Halbordnung zur Darstellung des potenziellen Wertes eines einzelnen Bits. © H. Falk 8 – Code-Optimierung Folie 36 / 104 Informatik 12 | DAES Die Halbordnung L4 (1) Pro Bit eines Registers wird mit einem Element aus X L4 gespeichert, welche Werte das Bit haben kann:  0 – Das betrachtete Bit hat den Wert 0 0 1  1 – Ein Bit hat den Wert 1  U – Der Wert eines Bits ist völlig unbekannt  X – Der Wert eines Bits ist irrelevant (don’t care) L N  L – Der Wert eines Bits ist unbekannt, aber dessen Herkunft (Location) ist bekannt. U  N – Wie L, nur ist das Bit bei bekannter Herkunft einmal negiert worden (negated Location) © H. Falk 8 – Code-Optimierung Folie 37 / 104 Informatik 12 | DAES Die Halbordnung L4 (2) L4 ist eine Halbordnung: X  Es gibt einen Operator ‘<‘, der die Elemente in L4 gemäß gerichteter Kanten in Relation setzt. 0 1  U hat geringsten Informationsgehalt und ist gemäß <-Operator am kleinsten.  X hat höchsten Informationsgehalt und ist L N gemäß <-Operator am größten. Diagramm links enthält vier horizontale Ebenen U  L4 © H. Falk 8 – Code-Optimierung Folie 38 / 104 Informatik 12 | DAES Beispiele zu L4 (1) Für eine Kante e sei r ein 8-Bit Register, das durch e modelliert wird. Graphische Notation: repräsentiert Up-Wert, Down-Wert Little Endian Darstellung (höchstwertiges Byte links geschrieben) Beispielhafte Kanten-Informationen für e und deren Interpretation: UU
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks