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

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:hauptstudium:ls2:ueb2-2013-26-07 [26.07.2013 09:02] – emperorwillipruefungen:hauptstudium:ls2:ueb2-2013-26-07 [22.08.2013 12:24] – 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, 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.
 +  * Wie erkennt man Schleifen? Welche Arten gibt es?
 +  * Was sind Induktionsvariablen? Welche Arten gibt es?
 +  * Wie kann man den Schleifenrumpf verkleinern?
 +  * Wann kann man schleifen parallelisieren? Zeig das mal an dem beispiel.