Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 3 » Kapitel 1   (Übersicht)

  • Prüfer: Prof. Fey
  • Beisitzer: Sebastian Rachuj

Kapitel 1

CISC/RISC

P: Was ist CISC und wie funktioniert es?

Viele mächtige Befehle, komplizierte Adressierungsarten. Bild mit IR → Decoder → Control Address Register → Control Memory → Control Buffer Register → Decoder und Sequencing Logic gemalt. Erklärt, wie Sprünge von Sequencing Logic erkannt werden (ALU Flags), warum Decoder nach CBR nötig (vertikale Mikroprogrammierung, siehe GRa).

P: Warum ist man von CISC abgekommen?

  • Patterson-Studie: Compiler emittieren nur Teilmenge aller CISC-Befehle.
  • Energieverbrauch: RISCs festverdrahtetes Leitwerk besser. [Anm.: Ich bin mir nicht sicher, ob es damals schon die Energieproblematik gab. Wahrscheinlich nicht, aber heutzutage schon ⇒ RISCs in Handys verbaut]

P: Was charakterisiert RISC?

  • Weniger, dafür elementare Befehle
  • Gleich langer Opcode (dafür Codedichte↓, aber leichtere Dekodierbarkeit in festverdrahtetem Leitwerk)
  • Befehle homogener (nicht so mächtig) ⇒ Erlaubt Pipelining mit Befehlsphaseneinteilung

Pipelining, Hazards

P: Erklären Sie mal das Pipeline-Prinzip.

Stufen BH, BD, BA, MEM, WB als Rechtecke hingemalt. Wenn Befehl in BD, kann gleichzeitig ein neuer Befehl in BH stecken usw. ⇒ Idealer Speedup von k bei k Stufen.

P: Wie kann BA direkt nach BD kommen? Fehlt da nicht etwas?

Ich wusste zuerst nicht, worauf er hinaus wollte. Er meinte die Operandenholphase. Ich entgegnete: Bei RISC sind das nur Register, also auch in BD machbar. [Anm.: Es gibt verschiedene akademische Pipeline-Modelle. Meine Variante ist die MIPS-Pipeline aus den Übungsblättern. Laut Folien ist sogar BH-BD in einer Stufe machbar.]

P: Wie viele Stufen hat denn eine aktuelle Intel Pipeline?

≈ 20

P: Sie haben den Speedup von k erwähnt. Warum wird er in der Realität nicht erreicht?

  • Strukturelle Hazards: FU schon belegt oder kein Multiportspeicher (BH und WB nicht gleichzeitig ausführbar).
  • Kontrollhazards: Nicht klar, wohin (Ziel) und ob (bedingter) Sprung eintritt.
  • Datenhazards: Gibt 3 Klasse, RAW kurz skizziert. RAW nicht verhinderbar, quasi nur durch Latency-Hiding (hier mit Out-of-Order Execution) versteckbar.
ld *$r1*, (0xCAFEBABE)
add $r2, *$r1*, $r3

P: Wie viele Zyklen verliere ich bei einem Kontrollhazard bei einem unbedingten Sprung?

1 Zyklus, da Ziel erst in BD feststeht, sowohl bei direkt als auch indirekt. [Anm.: Denn RISCs indirekte Sprünge können nur registerindirekt sein und Register in BD auslesbar.]

P: Skizzieren Sie mal die restlichen Datenhazards.

RAW oben schon gezeigt. WAW und WAR skizziert und erklärt. Skizzieren meint Assemblerprogramme

WAW:

div *$r1*, $r2, $r3
⋮
ld *$r1*, (0xCAFEBABE)
⋮

Das geht wegen Out-of-order Commit kaputt:

div |-------------|
⋮                 ↓
ld  |---------|   ↓
                  ↓

WAR:

div *$r1*, $r2, $r3
add $r4, *$1*, **$r5**
ld **$r5**, (0xCAFEBABE)

* kennzeichnet RAW und ** den eigentlichen WAR, der Operanden kaputt schreibt.

P: Wie heißen die Architekturen, die WAW zulassen?

WAW und WAR nur bei Superskalarität.

P: [Zeigt Blatt mit Scoreboard, im WS 16/17 Foliensatz ist das Kapitel 1 Folie 64]. Erklären Sie, wo welche Hazards beseitigt werden.

  • Scoreboard ist Datenstruktur, zweigeteilte Dekodierphase.
  • In-order Issue!
  • Dann erklärt, wo und warum strukturelle Hazards, WAW, und WAR beseitigt werden.
  • Erklärt, was die einzelnen Datenstrukturen enthalten, insbesondere warum man Rj, Rk benötigt, und warum sie auf „No“ gesetzt werden, nachdem man sie gelesen hat.

P: Skizzieren Sie doch mal Tomasulo. [Anm.: auf dem Blatt Papier, das man am Anfang bekam. Ohne jegliche Folie.]

Skizze: [Anm.: Ich hatte zuerst das Register File ausgelassen, Prof. hat es dann in der nächsten Frage selbst erwähnt.]

+----------+          +----------+
|    RS    |          |    RS    |
+----------+          +----------+
|    RS    |          |    RS    |
+----------+          +----------+
|    RS    +-----+----+    RS    |
+----------+     |    +----------+
|          |     |    |          |
|    FU    |     |    |    FU    |
|          |     |    |          |
|          |     |    |          |
+----------+     |    +----------+
                 |                                 +--------------------------+
                 |Common Data Bus (CDB)            |                          |
     +---------------------+-----------------------+      Reorder Buffer      |
     |                     |                       |                          |
+----+-----+          +----+-----+                 +--------------------------+
|    LW    |          |    SW    |                 |                          |
|          |          |          |                 +--------------------------+
+----------+          +----------+                 |                          |
|          |          |          |                 +--------------------------+
+----------+          +----------+                 |                          |
|          |          |          |                 +--------------------------+
+----------+          +----------+                 |                          |
|          |          |          |                 +-------------+------------+
+----------+          +----------+                               |
                                                                 |
                                                        +----------------+
                                                        |  Register File |
                                                        |                |
                                                        +----------------+
                                                        |                |
                                                        +----------------+
                                                        |                |
                                                        +----------------+
                                                        |                |
                                                        +----------------+

(mit http://asciiflow.com/ erstellt, dort auch Modifikationen nach Import möglich)

  • Erklärt, dass trotz belegter Funktionseinheit (FU) eine Instruktion in eine Reservierungsstation (RS) kopiert werden kann.
  • RS über Common Data Bus (CDB) verbunden, Sinn: wenn sie fertig sind, schicken sie auf den Bus „ich bin RS #123 und habe Ergebnis xyz“. So wird RAW dynamisch aufgelöst und WAR sowie WAW vermieden.
  • Load/Store Einheiten existieren.
  • Reorder Buffer (ROB) erklärt:
  • Einträge werden FIFO-mäßig vergeben, erlaubt Out-of-Order Completion, aber In-Order Commit
  • Vorteile
    • Präzises Trap/Interrupt-Modell, z. B. bei einer Exception bei einer Division: Exception wird, wenn sie auftritt, nur in ROB registriert. Wird erst ausgelöst, wenn der Befehl ganz oben im ROB an erster Stelle. Rest des ROBs wird geflushed.
    • Gleiches Vorgehen bei falscher Sprungvorhersage: ROB wird geflushed.
  • Siehe auch unten unter „Lernstil“ Literatur zum ROB.

P: Das heißt, der ROB hat welche Funktion bei falscher Sprungvorhersage?

Er verhindert Seiteneffekte, u. a. auf Register. Das ist nicht perfekt, da z. B. Cacheeffekte nicht vermieden werden und so die Sicherheitslücke Meltdown ermöglichten.

Kapitel 2

Manycore Beweggründe

P: Das soll für Kapitel 1 genügen. In Kapitel 2 haben wir uns mit Manycore beschäftigt. Warum haben wir überhaupt Manycore?

Generelles Ziel ist es, die Rechenleistung zu erhöhen. Wie?

  • Rechnerarchitektonische Maßnahmen: ausgereizt, Sprungvorhersage bei > 95%, Pollacks Regel arbeitet gegen uns.
  • Frequenz erhöhen: Grenzen der Physik erreicht. Hier habe ich dann die Dennard'sche Skalierung erwähnt und erklärt.

[Anm.: Als Prof. Fey die Prüfungsthemen in der letzten VL besprach, meinte er sinngemäß, dass die Dennard'sche Skalierung nicht unbedingt prüfungsrelevant ist, aber ein i-Tüpfelchen wäre. Wer also eine sehr gute Note reißen möchte, könnte sich das z. B. angucken. Ich vermute aber, dass Prof. Fey darauf nicht eingegangen wäre, hätte ich das nicht erwähnt. Man dürfte also nicht darauf warten, sondern müsste kommunizieren, dass man das weiß.]

P: Warum kann man [Anm.: in der Dennard'schen Skalierung] die Frequenz linear um κ erhöhen?

Habe gezögert.

P: Wenn weniger Elektronen bewegt werden müssen, dann …?

Ah, weil die Seitenlänge und der kritische Pfad auch mit 1/κ runtergehen. Dann habe ich weiter erklärt, dass die Leistungsdichte = 1 ist, also für den gleich großen Chip ungefähr dieselbe Kühlleistung veranschlagt werden muss. Heute ist das nicht mehr tragbar, in P = ρ ⋅ C ⋅ f ⋅ V_{dd}^2 sind f und V_{dd}^2 korreliert!

P: Das heißt, helfen kann uns nur noch …?

Echte Parallelität! Hier auch Amdahl's Law erwähnt, die charakteristische Kurve (Speedup über #Cores). Ob mehr Kerne wirklich besser sind, hängt auch von #Applikationen ab, wie in der VL auf dem TPT Diagramm besprochen. [Anm.: Kapitel 2 Folie 18 (Foliensatz WS 17/18, Schlagwort in der PDF: „Grenze gilt für eine auf allen Kernen laufende Applikation“, „Häufig jedoch: viele Applikationen“)]

P: [Holt seinen Ausdruck dieser Folie.] Ah, wenn Sie das auch noch erklären wollen, nur zu!

  • Erklärt, warum relative Performances 1, 0.5, 0.3 (Pollack'sche Regel rückwärts).
  • Erklärt, dass man mit wenigen Applikationen auf Amdahl's Kurve recht weit hinten herumhüpft (Speedup wird nur marginal besser, aber dafür relative Performanz der Kerne schlechter).
  • Erklärt, dass man mit vielen Applikationen auf Amdahl's Kurve recht weit vorne herumhüpft (Speedup wird deutlich besser, gleicht relativen Performanzverlust der schlechteren Kerne mehr als aus).

GPGPU Aufbau

P: Roofline lassen wir mal aus, da wir schon vertieft auf andere Sachen bisher eingegangen sind. Erklären Sie, wie eine GPGPU aufgebaut ist.

  • Skizze von Kapitel 2, Folie 84 (Foliensatz aus WS 17/18, Schlagwort in der PDF: „Allgemeiner Aufbau GPGPU“) gemalt.
  • Erklärt, wie Grid, Thread-Blöcke und Threads jeweils auf GPGPU, Multiprozessoren, Warps und Shaderprozessoren abgebildet werden. Stichwort Function Offloading, separierenden Compiler nvcc erwähnt.
  • Erwähnt, dass Shaderprozessoren „dumm“ sind, nur ein Leitwerk + Programmcodespeicher pro Multiprozessor.
  • Threads in Warp alle bei derselben Instruktion, werden quasiparallel ausgeführt.

P: Können Sie noch kurz etwas zur Speicherhierarchie sagen?

Register → Thread-lokaler Speicher (in GDDR, gecached im Shared Memory, dies konfigurierbar) → Shared Memory (für ganzen Threadblock) → L2 Cache → GDDR

Kapitel 3: Hierarchie von Rechensystemen

P: In Kapitel 3 haben wir die Hierarchie von GPP bis zu ASICs besprochen. Können Sie die aufzeigen?

Kapitel 3, Folie 2 (Foliensatz aus WS 17/18, Schlagwort in der PDF: „Kosten-/Leistungsvergleich verschiedener Implementierungsarten von Prozessoren“) skizziert. Insbesondere die Schlagworte an den Pfeilen wurden auf Nachfrage hin abgeprüft.

P: Nehmen wir das einfache Beispiel „if (a + b < c)“. Wie würde man das im GPP, im FPGA und im ASIC umsetzen?

  • Im GPP als Assembler; wird gepipelined.
  • Im FPGA mit LUTs; datenflussbasierter als GPP, hier Schaltmatrizen auch erwähnt.
  • Im ASIC mit Gattern, arbeitet ohne LUTs [auf Nachfrage hin]

Kapitel 4: Klassifikation von Multiprozessorsystemen

P: HOG lassen wir mal aus, da wir schon vertieft auf andere Sachen bisher eingegangen sind. Kapitel 4: Wie kann man Multiprozessoren klassifizieren?

Er wollte eigentlich Speicher- und Nachrichtenkopplung hören. Ich habe erstmal die Flynn'sche Klassifikation erwähnt und zu jeder Klasse ein Beispiel (insbesondere zu MISD: verzweigte Ausführung bei der Sprungvorhersage).

P: Nun aber zu Speicher- und Nachrichtenkopplung. Erklären Sie.

Speicherkopplung: ein virtueller Adressraum. Schwieriger zu programmieren, da man ein Speichermodell benötigt und eben urteilen muss, wann welche Variable wie sichtbar wird. Nicht so sehr skalierbar, da Adressraum beschränkt. Nachrichtenkopplung: Nachrichten. Mehr Overhead. Leichter zu programmieren. Skalierbar.

P: Der Adressraum ist bei Nachrichtenkopplung auch beschränkt. Warum ist Nachrichtenkopplung trotzdem skalierbarer? Wie genau?

Man verwende die Architekturen aus dem Internet: Switches und Router.

Prüfungsathmosphäre

  • Note: 1.0
  • Angenehme Prüfung, ähnelte eher einem Gespräch mit vielen „Erzählen Sie doch mal von Thema xyz“
  • Habt keine Scheu, das zur Verfügung gestellte Papier für Skizzen zu nutzen!
  • Prof. Fey lässt einen frei reden bei der Beantwortung einer Frage. Ich kann nur empfehlen, das auch zu tun und zu erzählen, was man alles so weiß - im Gegensatz zu einem abgehackten Hin-und-Her-Gespräch, wo dem Prüfling alles aus der Nase gezogen werden müsste :) Wenn er etwas genauer wissen möchte, dann fragt er auch nach. Durch freie Beantwortung kann man teilweise die Themen der Prüfung lenken, etwa wie bei mir, wenn man die Dennard'sche Skalierung erwähnt oder das TPT Diagramm. Das fand ich sehr nett!

Lernstil

  • 7 Tage Vorbereitung, unter dem Semester aber aktiv an VL und Übung teilgenommen.
  • VL Folien, Übungen + ein paar Begriffe im Internet nachschlagen fand ich ausreichend!
  • Zum ROB bei Tomasulo und seinen Vorteilen kann ich jedoch S. 187 ff. von Hennessy, Patterson, „Computer Architecture, A Quantitative Approach“, 5th Edition nur sehr empfehlen! Daraus habe ich auch die Vorteile, die ich oben als Antwort erwähnt habe.
  • Beim Durchgehen der VL Folien und Übungen unbedingt an der Liste der prüfungsrelevanten Themen orientieren (wird am Ende des Semesters immer herausgegegeben).
  • Manche Übungen sind zwar nett und hilfreich im Semester, lohnen aber nicht für die Prüfung: etwa Sezierung einer Speicheradresse zwecks Platzierung in den Cache oder Scoreboard und Tomasulo händisch in einer Tabelle ausführen. Die Prinzipien sollte man verstanden haben, insbesondere bei Scoreboard und Tomasulo (wann kann wie eine Instruktion weiterarbeiten?), aber in der Prüfung wird wohl nie abgefragt werden, 10 Instruktionen mal in einer Tabelle auszuführen. Das kostet viel zu viel Zeit!
  • Wenn man nur die genannten Themen in der Liste der prüfungsrelevanten Themen kann, ist man ziemlich sicher schon bei 1,x dabei. Da man aber recht frei reden kann, kann man mit zusätzlichen Details hier und da glänzen: Dennard'sche Skalierung oder ich könnte mir vorstellen, Echtzeiteigenschaften bei Kapitel 3 zu erwähnen oder Lockstep beim Infineon Aurix beim Flynn'schen MISD anzuschneiden.