CB2 7.5 ECTS Prüfung 2023-08-02

Prüfer: Prof. Phillipsen Beisitzer: Tobias Heineken

Beisitzer stellt Fragen, Prof. Phillipsen fragt ab und zu mal nach. Insgesamt herrscht eine angenehme Prüfungsathmosphäre.

Das Prüfungsprotokoll hat keinen Anspruch auf Vollständigkeit und bestimmt wurden kleinere Fragen oder Nachfragen vergessen, es gibt jedoch zumindest einen Überblick über den Ablauf der Klausur.

Generell nicht verunsichern lassen, ich hab während der Klausur mehrere kleinere Fehler gemacht und auch manche Dinge nicht sofort gesehen und die Note war trotzdem sehr gut. Mir wurde gut angerechnet, dass ich viel von mir aus gesagt hab, ohne das eine Nachfrage nötig war (hatte aber eigentlich gar nicht den Eindruck, hab immer versucht kurz und präzise zu antworten). Wichtig ist vorallem, dass man zeigt wie man an ein Problem herangeht und bearbeitet (laut denken). Bin zwar dann auch mal (mehrmals) auf das falsche Ergebnis/falschen Schluss gekommen, war aber kein Problem, das es anscheinend als „Falle“ angelegt war. Mir wurde zu gute gelegt, dass ich direkt strategisch an das Problem herangegangen bin.

Trotzdem ist es wichtig sich für die Klausur gut vorzubereiten, wichtig ist es die Sachen zu verstehen und nicht nur auswendig zu lernen. Am besten klappt das meiner Meinung nach in einer Lerngruppe.

Einstiegsfrage:

* Wir haben uns ja mit Optimierungen beschäftigt, warum machen wir Optimierungen?

Programme effizient laufen lassen, Speicherverbrauch, Laufzeit, …

* Ok, hier haben wir ein Codebeispiel (selbes Codebeispiel wie um 8 Uhr) und IR-Code wir wollen jetzt eine Spezialoperation für Minus mit positiven Endergebnis verwenden was müssen dafür machen?

Datenflussanlyse, brauchen aber erst Kontrollflussanalyse

* Was ist eine Kontrollflussanalyse?

Kontrollflussanalyse erklärt

* Wie bekommt man die Grundblöcke?

Erklärt und am IR-Code gezeigt, hab dann den fertigen KFG bekommen.

Dann ging es um Dominanz und was ein ImmDom ist, danach um die eigentliche Datenflussanalyse. Hab dafür alles erklärt und musste auch am KFG das Datenflusswissen als Schreibtischlauf propagieren. Wollte zuerst das ganze über Bitvektoren lösen, allerdings wurde ich darauf hingewiesen, dass dies im konkreten Beispiel nicht praktikabel sei und mir wurde ein alternativer Vorschlag für Mengen gemacht. Es kam noch eine Nachfrage was wir jetzt mit den bereits besuchten Knoten machen, in dem konkreten Fall ergab sich aber keine Änderung. Prof. Phillipsen hat irgendwo noch gefragt warum das ganze funktioniert und wann man fertig ist. → Fixpunkt und Terminierung erklärt. Nach der Prüfung wurde mir noch gesagt, dass ich hier meine Datenflussanalyse falsch initialisiert habe, da (auf den gegebenen Zettel, auf dem die möglichen Mengen standen) das Bottom-Element gefehlt hat und ich dann einfach ein anderes (falsches) verwendet hab. War aber nicht offensichtlich und auch ok.

* Wie rechnet man eigentlich Dominanz aus?

Iterativer Fixpunktalgorithmus oder Lengauer-Tarjan, musste aber nichts vorführen. Hab direkt einen DomTree bekommen

Weiter ging es mit Schleifen:

* Warum wollen wir Schleifen optimieren?

Großes Optimierungspotential, da mehrmals ausgeführter Code

* Kann man Schleifen irgendwie formaler fassen?

Natürliche Schleifen erklärt, musste noch im DomTree zeigen, wie ich die Dominanz erkenne.

* Gibt es auch nicht natürliche Schleifen?

Ja, wenn man direkt in den Schleifenrumpf springen kann.

* Wie erkenne ich dann ob eine Schleife natürlich ist?

Reduzierbarkeit prüfen, musste auch T1/T2 Algorithmus erklären, allerdings nicht ausführen.

Ok hier haben wir eine andere Schleife.

Code sah ca. so aus:

  int A[120];
  int B[120];
  int C[120];

  func foo() {
      for (int i=1; i<20; i++) {
          for (int j=1; j<20; j++) {
              A[i][j] = B[i] + C[i*3][i*3] + A[i-1][i-1] + j;
          }
      }
  }

* Was kann man hier machen?

Invariante Ausdrücke aus der inneren Schleife rausziehen, dabei erklärt wann etwas invariant ist und wann es herausziehbar ist.

War hier auch kurz wegen dem A[i-1][i-1] Ausdruck verwirrt, sollte dann erstmal die Datenabhaengigkeiten aufstellen.

* Welche Datenabhängigkeiten gibt es und wie kann ich sie darstellen, Distanzvektor wird hier ja schwer.

Richtungsvektor aufgestellt (<,*)

Dann aber festgestellt, dass der Ausdruck in der inneren Schleife trotzdem schleifeninvariant ist. Hab dann den Code für die herausgezogenen invarianten Teile bekommen.

Code sah ca. so aus:

  int A[120];
  int B[120];
  int C[120];
  
  func foo() {
      for (int i=1; i<20; i++) {
          t = B[i] + C[i*3][i*3] + A[i-1][i-1]; 
          for (int j=1; j<20; j++) {
              A[i][j] = t + j;
          }
      }
  }

* Was kann man jetzt machen?

Schleifenrumpfteilen um wieder auf kanonische Form zu kommen

* Das machen wir später, was kann man noch machen?

Sehe gerade nichts weiter

* Wie ist das mit dieser Multiplikation?

Ah ja, man kann eine Reduzierung der Ausdrucksstärke machen.

* Ok mach mal.

Am Beispiel i*3 vorgeführt und dabei ausversehen alle i durch meine frische Variable ersetzt, nach einem Hinweis bin ich aber dann darauf gekommen, dass ich hier konkret nur i*3 ersetzen darf.

      i' = 3 * i; // i' = 3
      for (int i ...) {
          t = B[i] + C[i'][i'] + A[i-1][i-1]; 
          for (int j ...) {
              ...
          }
          i' = i' + 3*1;
      }

* Und was ist mit i-1?

Ja, da kann ich das ganze auch machen.

* (Prof. Phillipsen) Ja dann machen sie mal.

Fange gerade an mit frischer Variable a = i-1 und werde direkt wieder unterbrochen, „ok das könnnen sie“, bekommen jetzt den Code mit Reduktion der Ausdrucksstärke.

Ca. so:

      for (int i=1, m=3, n=0; i<20; i++, m+=3, n++) {
          t = B[i] + C[i'][i'] + A[i-1][i-1]; 
          for (int j ...) {
              A[i][j] = t + j;
          }
      }

Bekomme wieder den Code dazu.

* Wie sieht es jetzt mit Schleifenrumpfteilen aus?

Haben noch Abhaengigkeiten: auf jeden Fall zwischen t und möglicherweise auf den A's. Hab dazu auch den Abhängigkeitsgraphen gemalt und erklärt, dass es einen Starke Zusammenhangskomponente gibt und es deshalb nicht möglich ist.

* Kann man bei den t's was machen?

Ja Skalarvervielfachung und das ganze eben erkärt. Dann fällt die eine Kante weg und man könnte es wieder machen.

Bekomme Schleifenrumpfteilen-Code.

* Sieht dann also so aus?

War mir nicht sicher und hab ja geantwortet, allerdings gibt es zwischen den A's noch eine Abhängigkeit und die starke Zusammenhangskomponente lässt sich nicht auflösen.

* Da haben sie sich jetzt [durch die Nachfragen] von mir ins Bockshorn jagen lassen, aber ihre Erklärungen waren sonst alle korrekt.

War dann anscheinend durch, aber es waren noch 3 Minuten Zeit.

* Was ist ein Alias?

Alias erklärt

* Also Alias bedeutet immer es besteht die Möglichkeit?

Nein gibt auch must-Aliase

* Warum stören die beim Optimieren?

Muss alle Alias beachten

* Was muss man jetzt bei einer Sprache wie C verglichen mit E2 beachten?

Es gibt Ptr und somit auch Aliase

* Gibt es in C noch andere Möglichkeiten Aliase zu erzeugen?

Ja, z.B. structs

Zeit um.