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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:hauptstudium:ls2:ueb2-2013-26-07 [26.07.2013 09:02] – emperorwilli | pruefungen:hauptstudium:ls2:ueb2-2013-26-07 [22.08.2013 12:25] (aktuell) – errnosys | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
====== Optimierungen in Übersetzern ====== | ====== Optimierungen in Übersetzern ====== | ||
+ | ===== Kandidat 1 ===== | ||
* Pruefer: Prof. Philippsen | * Pruefer: Prof. Philippsen | ||
Zeile 40: | Zeile 41: | ||
* Stell mal den Richtungsvektor auf -> aufstellen | * Stell mal den Richtungsvektor auf -> aufstellen | ||
* Kann man das ganze jetzt parallelsieren? | * 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, | ||
+ | Aber schnell sollte man durchgehen, sonst koennte es am Ende knapp werden! | ||
+ | |||
+ | Vorbereitend sollte man neben Skript und Uebungsblaetter den Uebungscompiler auch implementiert/ | ||
+ | |||
+ | 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 & | ||
+ | Der Code und der KFG sind frei aus dem Gedaechtniss, | ||
+ | <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; | ||
+ | int j=0; | ||
+ | if (A==B){ | ||
+ | c++; | ||
+ | goto append; | ||
+ | } | ||
+ | |||
+ | /* Maybe some code? */ | ||
+ | |||
+ | inside: | ||
+ | if (j< | ||
+ | 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; | ||
+ | } | ||
+ | </ | ||
+ | {{: | ||
+ | * P: Da kann man ja viele Labels in C reinschreiben, | ||
+ | * 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, | ||
+ | |||
+ | * P: Wozu braucht mans? | ||
+ | * A: SSA, fuer " | ||
+ | |||
+ | * 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)" | ||
+ | * A: Ja, wird nie ausgefuehrt, | ||
+ | * (+ Erklaerung, dass die Zuweisung " | ||
+ | |||
+ | * P: Intraprozeduale Aliasanlayse hilft nicht um das zu erkennen. Wie bekommt mans raus? | ||
+ | * A: Interprozedual, | ||
+ | |||
+ | * P: Was kann man noch optimieren? Schauen sie sich mal " | ||
+ | * 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, | ||
+ | * A erklaert; Definitionen dazu sollte man gut koennen. | ||
+ | * Wichtig ist das man durch den C-Code die implizite Arrayberechnung nicht sieht - da ist noch " | ||
+ | |||
+ | * 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, | ||
+ | |||
+ | * 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 erkennt man Schleifen? Welche Arten gibt es? | ||
+ | * Was sind Induktionsvariablen? | ||
+ | * Wie bringe ich in SSA-Form? Wozu? Wie komme ich wieder zurück? | ||
+ | * Wie kann man den Schleifenrumpf verkleinern? | ||
+ | * Wann kann man schleifen parallelisieren? | ||