Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Optimierungen in Übersetzern (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

--- pruefungen:hauptstudium:ls2:ueb2-2013-26-07 [26.07.2013 08:48] – angelegt emperorwilli
+++ pruefungen:hauptstudium:ls2:ueb2-2013-26-07 [22.08.2013 12:25] (aktuell) – errnosys
@@ Zeile 1: / Zeile 1: @@
 ====== Optimierungen in Übersetzern ======
+===== Kandidat 1 =====
   * Pruefer: Prof. Philippsen
@@ Zeile 24: / Zeile 25: @@
     * Was ist jetzt aber, wenn ich in C Code zu jeder Zeile ein neues Label einfuehre? -> Gemeint war hier, dass beim uebersetzen unangesprungene Label eliminiert werden
     * Welche Verfahren kann man auf dem KFG anwaenden? -> Dominanz, ImmDomm, ...
-    * Wozu wird die Domminanz / ImmDomms bestimmt? -> Schleifen, Phi-Fkt, ...
+    * Wozu wird die Dominanz / ImmDoms bestimmt? -> Schleifen, Phi-Fkt, ...
+    * Was sind Dominanzgrenzen, was bedeutet das? -> Neuer eingehender Kontrollfluss ...
+    * Wie bestimmt man Dominanzgrenzen? -> DGup / DGlocal Algorithmus erklaeren
+    * Wie werden Schleifen gefunden? -> Natuerliche Schleife bei Rueckkante, Dominanz, ...
+    * Was sind unnatuerliche Schleifen / Wie erkennt man das ein Programm solche hat? -> Reduzierbarkeit ...
     * Phi-Fkt: Warum... -> SSA Code, Vorteile SSA erlaeutert
     * Mach mal SSA Code -> Gemacht
@@ Zeile 36: / Zeile 41: @@
     * Stell mal den Richtungsvektor auf -> aufstellen
     * Kann man das ganze jetzt parallelsieren? -> ...
+===== Kandidat 2 =====
+  * Pruefer: Prof. Philippsen
+  * Beisitzer: Stefan Kempf
+  * Note 1.3
+  * ~ 30 min.
+  * Codebeispiel / Graphen + Bleistift
+Prof. Philippsen und Stefan Kempf haben ein gutes Pokerface, sollte aber jeder der Compilerbau 2 hoert von der vorherigen Pruefung schon wissen.
+Insgesamt ist in der Pruefung eine sehr angenehme Atmosphaere, es wird auch wirklich gut geholfen - der Code ist tricky, und es wird nicht erwartet alles gleich automatisch zu sehen.
+Aber schnell sollte man durchgehen, sonst koennte es am Ende knapp werden!
+Vorbereitend sollte man neben Skript und Uebungsblaetter den Uebungscompiler auch implementiert/optimiert haben, hilft ungemein.
+War vermutlich das gleiche Beispiel wie das ueber diesem Protokoll; zumindest der Pruefling nach mir hatte den gleichen Code vor sich ;)
+Man bekommt ein Stueck C-Code und den entsprechenden KFG.
+Meine Vorfreude ueber die fehlende &-Operatoren wurde doch etwas gedaempft, als ich die * gesehen hab ;)
+Der Code und der KFG sind frei aus dem Gedaechtniss, keine Garantie auf Richtigkeit!
+<code c>
+static int ArrayA[65536][65536];
+static int ArrayB[65536][65536];
+int *get_first_array(){ return ArrayA; };
+int *get_second_array() { return ArrayB; };
+int main(){
+	int *A = get_first_array();
+	int *B = get_second_array();
+	int c=0;
+	for (int i=0;i<1024;i++){
+		int j=0;
+		if (A==B){
+			c++;
+			goto append;
+		}
+	/* Maybe some code? */
+inside:
+		if (j<=1024){
+append:
+			A[i][j]=B[c][c]+A[i-1][j-2]*A[i][j+2048];
+			c = c * c;
+			j++;
+			goto inside;
+		}
+out:
+	}
+	return 0;
+}
+</code>
+{{:pruefungen:hauptstudium:ls2:kfg.png|:pruefungen:hauptstudium:ls2:kfg.png}}
+  * P: Da kann man ja viele Labels in C reinschreiben, wie wirkt sich das auf den KFG aus?
+  * A: Gar nicht so sehr, da unnuetze Labels vom RemoveGarbage (zumindest bei unserem E-Compiler) entfernt werden.
+  * P: Welche Optimierungen kann man auf dem KFG machen?
+  * A: Dominatoren, Dominanzgrenzen (usw mit Erklaerung)
+  * P: Wozu braucht mans?
+  * A: SSA, fuer "c" mit einem Algorithmus (egal ob Click oder Standard) durchfuehren, Vorteile von SSA erklaeren
+  * P: Welche Rueckwaertskanten gibts?
+  * A: nur die von der For-Schleife (gruen). Die andere (rot) wird nicht dominiert, wegen dem "goto append"
+  * P: Schauen sie sich mal das "if (A==B)" genau an!
+  * A: Ja, wird nie ausgefuehrt, da A und B (immer) unterschiedlich sind. Kann man loeschen (also alles was blau ist).
+  * (+ Erklaerung, dass die Zuweisung "A[i][j]=" nichts an der Adresse aendert)
+  * P: Intraprozeduale Aliasanlayse hilft nicht um das zu erkennen. Wie bekommt mans raus?
+  * A: Interprozedual, Beispiel Steensgard. A --> ArrayA, B --> Array B , nicht verknuepft, kein gemeinsamer Knoten, somit unabhaengig.
+  * P: Was kann man noch optimieren? Schauen sie sich mal "c" an
+  * A: c wird nun immer 0 bleiben. Bekommt man raus durch bedingte Konstantenfortschreibung (kurz erklaeren).
+  * P: Welche Schleifen gibts nun?
+  * A: Zwei (rot und gruen).
+  * P: Was sind alles Induktionsvariablen, was ist invariant, was kann man rausziehen, was sind die regeln dazu.
+  * A erklaert; Definitionen dazu sollte man gut koennen.
+  * Wichtig ist das man durch den C-Code die implizite Arrayberechnung nicht sieht - da ist noch "dim" in "(i-1)*dim+(j-2)"!
+  * P: Welche Datenbaehngigkeiten gibts
+  * A: Fluss+Anti, mit Vektor.
+  * P: Nun schauen sie sich die Arrayzuweisung an
+  * A: Da nun B[0][0] ist kann man es nun rausziehen.
+  * P: Weiter schaun!
+  * A: Da die schleife nur bis j<=1024 geht, interessiert der letzte Arrayzugriff nicht (j+2048 - somit keine Abhaengigkeiten)
+  * P: Wie macht mans paralell?
+  * A: erste Schleife traegt die Abhaengigkeit, man kann somit die innere paralell ausfuehren
+  * P: Geht auch die aeussere?
+  * A [stottert ergebnislos bei Schleifenneigung rum] - Richtig ist: ja, durch Schleifenneigung und vertauschen.
+===== Kandidat 3 =====
+  * Datum: 22.08.2013
+  * Pruefer: Prof. Philippsen
+  * Beisitzer: Jakob Krainz
+  * ~ 30 min.
+Fragen: (Antworten werden mit → eingeleitet)
+  * Was haben wir denn in der Vorlesung gelernt?
+  * Was ist KFG? Wie bestimmt man KFG? Dominatoren Wozu? → SSA-Form bestimmen. Wozu noch? → Regionen, insbesondere Schleifen erkennen.
+  * Was sind Dominatoren? Wie bestimme ich Dominatoren, ImDom und DominatorGrenze?
+  * Wie erkennt man Schleifen? Welche Arten gibt es?
+  * Was sind Induktionsvariablen? Welche Arten gibt es?
+  * Wie bringe ich in SSA-Form? Wozu? Wie komme ich wieder zurück?
+  * Wie kann man den Schleifenrumpf verkleinern?
+  * Wann kann man schleifen parallelisieren? Zeig das mal an dem beispiel.