Masterprojekt Rechnerarchitektur - Exam

Aufgabe 1)

Pipeline-Design und -OptimierungDer Prozess zur Minimierung von Konflikten und Maximierung des Durchsatzes in Pipeline-Architekturen ist ein zentraler Bestandteil moderner Prozessorentwicklung. Dabei geht es um die effiziente Gestaltung der Pipeline, um die Instruktionsrate (throughput) zu erhöhen und die Latenz zu reduzieren. Dies umfasst mehrere Aspekte:

• Branch Prediction: Vermeidung von Pipeline-Stalls durch Wahrscheinlichkeitsberechnung zur Vorhersage von Sprüngen.
• Hazard-Mitigation: Adressierung von Daten-, Steuer- und strukturellen Hazards, die den reibungslosen Ablauf von Instruktionen stören könnten.
• Datenweiterleitung (Forwarding/Bypassing): Direktes Weiterleiten der Ergebnisse aus vorgelagerten Pipeline-Stufen, um auf Speicherzugriffe zu verzichten und so die Effizienz zu steigern.
• Superskalare Ausführung: Fähigkeit mehrere Instruktionen pro Taktzyklus auszuführen, um die maximale Nutzung der verfügbaren Ressourcen zu gewährleisten.

a)

a) Beschreibe den Prozess der Branch Prediction und erkläre, wie dieser hilft, Pipeline-Stalls zu vermeiden. Diskutiere die Herausforderungen und Limitationen, die mit der Implementierung einer effektiven Branch Prediction verbunden sind.

Lösung:

a) Branch Prediction: Der Prozess der Branch Prediction spielt eine entscheidende Rolle in der Pipeline-Architektur eines Prozessors. Er zielt darauf ab, Pipeline-Stalls zu minimieren, indem vorhergesagt wird, welcher Weg (Branch) bei einer Verzweigungsinstruktion (z.B. 'if', 'for') genommen wird.

• Funktionsweise: Bei der Branch Prediction versucht der Prozessor zu berechnen, wohin der Programmfluss bei einer bedingten Verzweigung geht, bevor die Entscheidung tatsächlich bekannt ist (d.h. bevor die zugehörige Bedingung ausgewertet wurde). Dies geschieht häufig durch historische Daten, d.h., wie sich der Prozessor in ähnlichen Situationen zuvor verhalten hat.
• Typen der Branch Prediction:
  • Statische Branch Prediction: Bei dieser Methode wird eine einfache Regel verwendet, wie z.B. 'Branch never taken' oder 'Branch always taken'.
  • Dynamische Branch Prediction: Hierbei werden komplexe Algorithmen genutzt, die historische Ausführungsverläufe berücksichtigen, um Vorhersagen zu treffen. Ein Beispiel ist die Verwendung von Branch-History-Tables, die Informationen darüber speichern, wie oft ein Branch in der Vergangenheit genommen wurde.
• Vorteile: Durch die exakte Vorhersage von Branches kann der Prozessor die nächste Instruktion vorbereiten und ausführen, ohne auf die Entscheidungsergebnisse warten zu müssen. Dies minimiert Pipeline-Stalls erheblich und verbessert die Instruktionsrate (Throughput).
• Herausforderungen und Limitationen:
  • Vorhersagegenauigkeit: Eine hohe Vorhersagegenauigkeit ist notwendig, um tatsächliche Leistungsgewinne zu erzielen. Falsche Vorhersagen führen zu schweren Stalls, da der Prozessor den falschen Pfad ausführen und alle falschen Instruktionen verwerfen muss.
  • Kompromisse zwischen Komplexität und Leistung: Komplexe Branch Prediction-Methoden können zwar genauer sein, erfordern jedoch mehr Hardware und können den Energieverbrauch erhöhen. Ein Gleichgewicht zwischen Genauigkeit, Aufwand und Energieverbrauch zu finden, ist daher eine Herausforderung.
  • Branch-Misprediction: Wenn der Prozessor einen Branch falsch vorhersagt (Branch Misprediction), muss die Pipeline geleert werden, und es entsteht eine Verzögerung, bis der richtige Pfad ausgeführt werden kann. Dies kann die Effizienz der Pipeline signifikant reduzieren.

b)

b) Erkläre den Unterschied zwischen Daten-, Steuer- und strukturellen Hazards. Gib für jede Art von Hazard ein Beispiel und beschreibe, wie diese Hazards mithilfe unterschiedlicher Techniken in der Pipeline-Architektur minimiert werden können.

Lösung:

b) Unterschied zwischen Daten-, Steuer- und strukturellen Hazards:

• Datenhazard: Ein Datenhazard tritt auf, wenn eine Instruktion auf Daten zugreifen muss, die noch nicht von einer vorhergehenden Instruktion bereitgestellt wurden. Beispiel:

   ADD R1, R2, R3  // Berechnet R1 = R2 + R3 SUB R4, R1, R5  // Möchte R4 = R1 - R5 berechnen 

  Die zweite Instruktion benötigt den Wert von R1, der jedoch erst während der Ausführung der ersten Instruktion berechnet wird. Technik zur Minimierung:
  • Datenweiterleitung (Forwarding/Bypassing): Charakterisiert sich durch das direkte Weiterleiten der Ergebnisse aus einer vorgelagerten Pipeline-Stufe in eine nachgelagerte, um auf Speicherzugriffe zu verzichten und so die Effizienz zu steigern.
  • Pipeline-Stalls: Die Pipeline wird angehalten, bis die benötigten Daten verfügbar sind.
• Steuerhazard: Ein Steuerhazard tritt auf, wenn der Prozessor nicht weiß, welche Instruktion als nächstes ausgeführt werden soll, da die Entscheidung darüber noch nicht gefällt wurde (z.B. bei einem Branch). Beispiel:

   BEQ R1, R2, Label // If R1 == R2, then jump to Label ADD R3, R4, R5 // Anweisung nach BEQ 

  Der Prozessor weiß nicht sofort, ob das Label genommen wird oder die nächste Befehlsadresse verwendet wird. Technik zur Minimierung:
  • Branch Prediction: Wahrscheinlichkeitsbasierte Vorhersagen, ob ein Sprung durchgeführt wird oder nicht, um die richtigen Instruktionen vorauszuladen.
  • Delay Slots: Einfügen von Anweisungen, die immer ausgeführt werden, unabhängig davon, ob der Branch genommen wird oder nicht.
• Struktureller Hazard: Ein struktureller Hazard tritt auf, wenn mehrere Instruktionen gleichzeitig auf dieselben Hardware-Ressourcen zugreifen und diese zur selben Zeit benötigen. Beispiel:

   Z.B. zwei Instruktionen möchten gleichzeitig auf dieselbe Speicherbank zugreifen. 

  Technik zur Minimierung:
  • Vergrößerung der Ressourcen: Zum Beispiel durch Hinzufügen zusätzlicher ALUs oder Speicherbänke.
  • Pipeline-Stalls: Eine Instruktion muss warten, bis die Ressource verfügbar ist.

c)

c) Erläutere das Prinzip der Datenweiterleitung (Forwarding/Bypassing) und wie es dabei hilft, die Performance der Pipeline zu erhöhen. Berechne, wie sich die Latenz einer Pipeline verändert, wenn Forwarding eingesetzt wird. Gegeben sei eine 5-stufige Pipeline ohne Forwarding: Fetch (1 Taktzyklus), Decode (1 Taktzyklus), Execute (1 Taktzyklus), Memory (1 Taktzyklus), Writeback (1 Taktzyklus). Wie ändert sich die Latenz, wenn ein Ergebnis direkt von der Execute- zur Decode-Stufe weitergeleitet wird?

Lösung:

c) Prinzip der Datenweiterleitung (Forwarding/Bypassing):

• Definition: Datenweiterleitung, auch als Forwarding oder Bypassing bekannt, ist eine Technik in der Pipeline-Architektur, bei der das Ergebnis einer Instruktion direkt aus der Ausführungsstufe (Execute) an eine nachfolgende Instruktion gesendet wird, die diese Daten benötigt, bevor sie den Speicher erreicht oder in das Register geschrieben wird.
• Funktionsweise: Angenommen, eine Instruktion berechnet einen Wert in der Execute-Stufe, und eine darauf folgende Instruktion benötigt diesen Wert in der Decode-Stufe. Ohne Forwarding müsste die nachfolgende Instruktion warten, bis der Wert den gesamten Pipeline-Zyklus durchlaufen hat. Mit Forwarding kann der Wert jedoch direkt von der Execute- zur Decode-Stufe geleitet werden, wodurch Wartezeiten entfalten werden.
• Vorteile:
  • Reduktion von Pipeline-Stalls: Instruktionen müssen nicht auf das Abschluss eines kompletten Pipeline-Zyklus der vorhergehenden Instruktionen warten.
  • Erhöhung des Durchsatzes: Mehr Instruktionen können pro Zeiteinheit ausgeführt werden, was zu einer besseren Performance führt.

Berechnung der Latenzänderung:

Gegeben sei eine 5-stufige Pipeline ohne Forwarding:

• Fetch (1 Taktzyklus)
• Decode (1 Taktzyklus)
• Execute (1 Taktzyklus)
• Memory (1 Taktzyklus)
• Writeback (1 Taktzyklus)

In einer Pipeline ohne Forwarding würde eine Instruktion, die von dem Ergebnis einer vorhergehenden Instruktion abhängt, warten, bis diese das Writeback-Stadium erreicht hat. Dies bedeutet, dass die nachfolgende Instruktion mindestens 5 Taktzyklen verzögert wird.

Mit Datenweiterleitung wird das Ergebnis jedoch direkt von der Execute-Stufe zur Decode-Stufe weitergeleitet. Das bedeutet:

• Die abhängige Instruktion kann den Wert bereits im Decode-Stadium erhalten, anstatt bis zum Writeback zu warten.
• Dies reduziert die Wartezeit um 3 Taktzyklen (Memory und Writeback), sodass die abhängige Instruktion nur noch 2 Taktzyklen warten muss (also den Fetch- und Decode-Zyklus).

Veränderung der Latenz: Ohne Forwarding beträgt die Latenz 5 Taktzyklen (1 Fetch + 1 Decode + 1 Execute + 1 Memory + 1 Writeback).

Mit Forwarding beträgt die Latenz nur noch 2 Taktzyklen (1 Fetch + 1 Decode), da das Ergebnis schon während der Decode-Phase zur Verfügung steht.

Somit reduziert sich die Latenz von 5 Taktzyklen auf 2 Taktzyklen, wenn Datenweiterleitung eingesetzt wird.

d)

d) Was versteht man unter superskalarem Ausführung? Stelle eine Pipeline vor, die 1 Instruktion pro Taktzyklus ausführt und eine andere, die 2 Instruktionen pro Taktzyklus ausführt. Angenommen, jede Instruktion benötigt durchschnittlich 5 Taktzyklen, um abgeschlossen zu werden. Berechne den Durchsatz für beide Pipelines und vergleiche die Ergebnisse. Diskutiere, unter welchen Bedingungen eine superskalare Architektur mehr Vorteile bietet.

Lösung:

d) Superskalare Ausführung:

• Definition: Superskalare Ausführung bezeichnet die Fähigkeit eines Prozessors, mehr als eine Instruktion pro Taktzyklus auszuführen. Dies wird durch die Nutzung mehrerer paralleler Funktionseinheiten innerhalb der Pipeline erreicht. Superskalare Prozessoren sind so ausgelegt, dass sie mehrere Instruktionen gleichzeitig abrufen, dekodieren und ausführen können.

Berechnung des Durchsatzes:

• Einzelpipline (1 Instruktion pro Taktzyklus): Angenommen, jede Instruktion benötigt durchschnittlich 5 Taktzyklen, um abgeschlossen zu werden. Der Durchsatz (Anzahl der abgeschlossenen Instruktionen pro Taktzyklus) kann wie folgt berechnet werden:

 Durchsatz Einzelpipline = Anzahl Instruktionen pro Taktzyklus / Durchschnittliche Taktzyklen pro Instruktion              = 1 Instruktion / 5 Taktzyklen             = 0,2 Instruktionen pro Taktzyklus 

• Superskalare Pipeline (2 Instruktionen pro Taktzyklus): Angenommen, jede der beiden parallelen Instruktionen benötigt ebenfalls durchschnittlich 5 Taktzyklen, um abgeschlossen zu werden. Der Durchsatz wäre:

 Durchsatz superskalare Pipeline = Anzahl Instruktionen pro Taktzyklus / Durchschnittliche Taktzyklen pro Instruktion                           = 2 Instruktionen / 5 Taktzyklen                           = 0,4 Instruktionen pro Taktzyklus 

• Der Durchsatz einer Pipeline, die 2 Instruktionen pro Taktzyklus ausführt, ist somit doppelt so hoch wie der einer Pipeline, die 1 Instruktion pro Taktzyklus ausführt.

Vergleich der Ergebnisse:

• Einzelpipeline: 0,2 Instruktionen pro Taktzyklus
• Superskalare Pipeline: 0,4 Instruktionen pro Taktzyklus

Diskussion der Vorteile einer superskalaren Architektur:

• Eine superskalare Architektur bietet signifikante Vorteile unter folgenden Bedingungen:
• Es gibt genügend unabhängige Instruktionen, die parallel ausgeführt werden können. Wenn viele Instruktionen Abhängigkeiten voneinander haben, kann die superskalare Architektur nicht effektiv genutzt werden.
• Die Hardware-Ressourcen (wie Funktionseinheiten und Register) sind ausreichend, um mehrere parallele Pfade zu unterstützen.
• Die Steuerlogik des Prozessors ist in der Lage, Instruktionsflüsse effizient zu verteilen und Konflikte (Hazards) zu minimieren.
• Vorteile:
  • Erhöhung des Durchsatzes: Die Execution von mehreren Instruktionen pro Taktzyklus erhöht die Leistung des Prozessors erheblich.
  • Bessere Ressourcennutzung: Superskalare Architekturen können Hardware-Ressourcen effizienter nutzen.
• Limitierungen:
  • Instruktionsabhängigkeiten: Wenn viele Instruktionen auf das Ergebnis vorheriger Instruktionen warten müssen, können nicht alle parallelen Pfade genutzt werden.
  • Hardware-Komplexität: Die Steuerlogik und Ressourcenzuweisung werden erheblich komplexer und teurer.
  • Energieverbrauch: Mehr parallele Einheiten erhöhen den Energieverbrauch und die Wärmeabgabe des Prozessors.

Aufgabe 2)

Angenommen, Du hast einen Many-Core Prozessor mit 64 Kernen, der für wissenschaftliche Berechnungen eingesetzt wird. Du wirst beauftragt, ein Programm zur Simulation von Fluiddynamik zu schreiben. In diesem Programm müssen große Datenmengen parallel verarbeitet werden, um die Berechnungen in akzeptabler Zeit durchzuführen. Zusätzlich soll die Effizienz der Nutzung aller verfügbaren Kerne maximiert werden.

a)

Zuerst musst Du die Datenstruktur für diese Simulation entwerfen. Beschreibe die wichtigsten Aspekte, die Du bei der Wahl der Datenstruktur(en) für die parallele Verarbeitung auf einem Many-Core Prozessor berücksichtigen musst. Erkläre, wie Du sicherstellen kannst, dass die Speicherzugriffe optimal erfolgen und welche Synchronisationsmechanismen nötig sein könnten, um Thread-Konflikte zu minimieren.

Lösung:

• Wahl der Datenstruktur
• Du solltest eine Datenstruktur wählen, die eine effiziente parallele Verarbeitung ermöglicht. Eine gute Wahl könnten Arrays, Matrizen oder Vektoren sein, da diese leicht in kleinere Teile segmentiert werden können, die dann parallel verarbeitet werden.
• Ein regelmäßiges Raster (Grid) eignet sich hervorragend für Fluiddynamiksimulationen, da die Nachbarschaftsbeziehungen zwischen den Zellen klar definiert sind. Ein 2D- oder 3D-Array kann verwendet werden, um die physikalischen Eigenschaften jedes Punktes im Raum darzustellen.
• Optimierung der Speicherzugriffe
• Um die Speicherzugriffe zu optimieren, solltest Du auf die Speicherhierarchie achten. Eine Cache-freundliche Datenorganisation ist entscheidend. Versuche, die Daten in einem kontinuierlichen Speicherbereich abzulegen, um Cache-Misses zu minimieren.
• Das Layout der Daten sollte so gewählt werden, dass der Zugriff lokal bleibt. Das bedeutet, dass aufeinanderfolgende Speicherzugriffe die gleiche oder benachbarte Speicherblöcke betreffen.
• Eine Blockpartitionierung kann dabei helfen: Teile das große Problem in kleinere Blöcke auf, die innerhalb eines Kernels Cache-effizient verarbeitet werden können.
• Synchronisationsmechanismen
• Thread-Konflikte können durch die Verwendung von Synchronisationsmechanismen wie Mutexes, Semaphoren oder Sperren (Locks) minimiert werden. Diese Mechanismen sorgen dafür, dass nur ein Thread gleichzeitig auf eine kritische Ressource zugreift.
• Ein anderer Ansatz könnte das Verwenden von lock-free Strukturen sein, jedoch sind diese komplexer und erfordern ein tiefes Verständnis der parallelen Programmierung.
• Eine Barriere-Synchronisation kann nach jedem Zeitschritt der Simulation notwendig sein, um sicherzustellen, dass alle Threads ihren aktuellen Berechnungszyklus abgeschlossen haben, bevor sie mit dem nächsten beginnen.
• Atomare Operationen sollten ebenfalls in Betracht gezogen werden, um Operationen zu implementieren, die ohne Unterbrechung abgeschlossen werden und somit Thread-Konflikte vermeiden.
• Zusammenfassung
• Die Wahl einer geeigneten Datenstruktur (Raster/Array/Matrix) ist entscheidend für die parallele Verarbeitung.
• Optimiere die Speicherzugriffe durch Cache-freundliche Datenorganisation und Lokalisierung der Zugriffe.
• Verwende geeignete Synchronisationsmechanismen (Mutexes, Semaphoren, Barrieren, atomare Operationen) zur Minimierung von Thread-Konflikten.

 // Definition eines einfachen 2D-Arrays zur Darstellung des Fluidfelds#define N 100#define T 1000float fluidField[N][N];  // Funktion, die von jedem Thread aufgerufen wirdvoid updateFluidField(int id, int numThreads) {    for (int t = 0; t < T; t++) {        for (int i = id; i < N; i += numThreads) {            for (int j = 0; j < N; j++) {                // Berechnung der neuen Werte, basierend auf Nachbarschaft                fluidField[i][j] = computeNewValue(i, j);             }        }        // Barriere-Synchronisation sicherstellen        #pragma omp barrier    }}

b)

Angenommen, die Hauptberechnung in deiner Fluiddynamik-Simulation ist in der Lage, auf alle 64 Kerne parallel verteilt zu werden. Formuliere ein mathematisches Modell zur Bestimmung der Gesamtausführungszeit der Simulation. Berücksichtige dabei die Skalierbarkeit und mögliche Overheads durch Thread-Verwaltung und Synchronisation. Zeige mathematisch auf, wie sich die Run-Time verhält, wenn die Anzahl der Kernel von 1 auf 64 ansteigt. Nutze folgende gegebenen Variablen:

• \( t_{seq} \): Zeit für die sequentielle Berechnung
• \( t_{par} \): Zeit für die parallele Berechnung pro Kern
• \( O_{sync} \): Overhead-Zeit durch Synchronisation

Lösung:

• Mathematisches Modell zur Bestimmung der Gesamtausführungszeit
• Um die Gesamtausführungszeit der Fluiddynamik-Simulation zu modellieren, werden wir sowohl die Zeit für sequentielle Berechnungen als auch für parallele Berechnungen und den Synchronisations-Overhead berücksichtigen.

• Die Gesamtausführungszeit (T_{total}) kann folgendermaßen ausgedrückt werden:

• \( T_{total} = t_{seq} + \frac{t_{par}}{N} + O_{sync} \times (N-1) \)

• Hierbei:

• \( t_{seq} \): Zeit für die sequentielle Berechnung
• \( t_{par} \): Zeit für die parallele Berechnung pro Kern
• \( O_{sync} \): Overhead-Zeit durch Synchronisation
• \( N \): Anzahl der Kerne

• Diese Formel berücksichtigt:

• Die sequentielle Berechnung, die unabhängig von der Anzahl der Kerne ist.
• Die parallele Berechnungszeit, die durch die Anzahl der Kerne geteilt wird.
• Die Synchronisations-Overhead, der proportional zur Anzahl der Kerne minus eins ist.

• Analyse der Gesamtausführungszeit für verschiedene Werte von N:

• Für \( N = 1 \) (ein Kern):

• \( T_{total}(1) = t_{seq} + t_{par} + O_{sync} \times 0 \)

• \( T_{total}(1) = t_{seq} + t_{par} \)

• Für \( N = 2 \) (zwei Kerne):

• \( T_{total}(2) = t_{seq} + \frac{t_{par}}{2} + O_{sync} \times (2-1) \)

• \( T_{total}(2) = t_{seq} + \frac{t_{par}}{2} + O_{sync} \)

• Für \( N = 64 \) (64 Kerne):

• \( T_{total}(64) = t_{seq} + \frac{t_{par}}{64} + O_{sync} \times (64-1) \)

• \( T_{total}(64) = t_{seq} + \frac{t_{par}}{64} + O_{sync} \times 63 \)

• Interpretation des Ergebnisses hinsichtlich der Effizienzsteigerung:

• Der Overhead durch Synchronisation wächst linear mit der Anzahl der Kerne (\( N \)), während die Zeit für die parallele Berechnung invers proportional zur Anzahl der Kerne abnimmt.
• Das bedeutet, dass bei einer kleinen Anzahl von Kernen die parallele Berechnung dominiert, während bei einer großen Anzahl von Kernen der Synchronisations-Overhead dominanter wird.
• Zur Bewertung der Effizienzsteigerung kann das Speedup-Verhältnis berechnet werden:

• \( \text{Speedup}(N) = \frac{T_{total}(1)}{T_{total}(N)} \)

• Ideal wäre das Speedup-Verhältnis gleich der Anzahl der genutzten Kerne (\( N \)). Falls der Overhead vernachlässigbar wäre, würde das Speedup-Verhältnis näher an \( N \) liegen.

• Für \( N = 64 \):

• \( \text{Speedup}(64) = \frac{t_{seq} + t_{par}}{t_{seq} + \frac{t_{par}}{64} + O_{sync} \times 63} \)

• Mit zunehmender Anzahl an Kernen wird die Effizienzreduktion aufgrund der Synchronisations-Overhead deutlicher. Dies verdeutlicht die Balance zwischen Parallelisierung und Synchronisationskosten und zeigt, dass theoretisch unbegrenzt viele Kerne nicht immer zu einer Proportionalen Reduktion der Laufzeit führen.

Aufgabe 3)

In dieser Aufgabe sollst Du das Wissen über Leistungsmessinstrumente und -metriken anwenden. Die Leistung eines Computerprogramms und seine Effizienz in einer gegebenen Rechnerarchitektur sollen analysiert und bewertet werden. Dazu stehen verschiedene Werkzeuge und Methoden zur Verfügung, wie Profiler, Tracing-Tools und Hardware-Performance-Counter. Typische Metriken sind Durchsatz (Throughput), Latenz (Latency) und Zyklen pro Instruktion (CPI). Zur Effizienzbewertung können FLOPS (Floating Point Operations Per Second) und MIPS (Million Instructions Per Second) herangezogen werden.

a)

a) Betrachte ein Computerprogramm, das 1.000.000 Instruktionen ausführt. Wenn es auf einer bestimmten Rechnerarchitektur eine durchschnittliche Latenz von 500 ns pro Instruktion hat, berechne den gesamten Durchsatz in Instruktionen pro Sekunde (IPS). Hinweis: Der Durchsatz (IPS) ist reciprocal zur Latenzzeit. Gib Deine Antwort sowohl in IPS als auch in MIPS an.

Lösung:

Um diese Aufgabe Schritt für Schritt zu lösen, folgen wir diesen Schritten:

• Zuerst definieren wir, was wir wissen:

• Das Computerprogramm führt 1.000.000 Instruktionen aus.
• Die durchschnittliche Latenz pro Instruktion beträgt 500 ns (Nanosekunden).

• Um den Durchsatz in Instruktionen pro Sekunde (IPS) zu berechnen, nutzen wir die Beziehung zwischen Latenz und Durchsatz:

• Durchsatz (\text{IPS}) ist der Kehrwert der Latenzzeit.

Die Latenzzeit ist gegeben als:

• 500 ns (Nanosekunden) pro Instruktion.

Da 1 Sekunde = 1.000.000.000 Nanosekunden, ist die Latenzzeit in Sekunden:

• \text{Latenzzeit} = 500 \text{ ns} = \frac{500}{1.000.000.000} \text{ s} = 5 \times 10^{-7} \text{ s}

Nun berechnen wir den Durchsatz (\text{IPS}):

• \text{Durchsatz} (\text{IPS}) = \frac{1}{{\text{Latenzzeit}}} = \frac{1}{5 \times 10^{-7} \text{ s}} = 2.000.000 \text{ IPS}

Jetzt konvertieren wir den Durchsatz in Million Instructions Per Second (MIPS):

• \text{Durchsatz} (\text{MIPS}) = \frac{2.000.000 \text{ IPS}}{1.000.000} = 2 \text{ MIPS}

Antwort:

• Der gesamte Durchsatz beträgt 2.000.000 Instruktionen pro Sekunde (IPS).
• Der gesamte Durchsatz beträgt 2 Million Instruktionen pro Sekunde (MIPS).

b)

b) Angenommen, Du verwendest das Profiler-Tool \textit{gprof}, um das gleiche Programm zu analysieren. Beschreibe detailliert, welche Informationen und Metriken \textit{gprof} liefern würde. Nenne mindestens drei spezifische Outputs von \textit{gprof} und erkläre, wie diese zur Bewertung der Programmleistung genutzt werden können.

Lösung:

Das Profiler-Tool gprof ist sehr nützlich, um die Leistung eines Programms zu analysieren. Es liefert detaillierte Informationen über die Ausführung der Funktionen im Programm und gibt Aufschluss über mehrere Leistungsmetriken. Im Folgenden werden drei spezifische Outputs beschrieben, die gprof liefert, und es wird erklärt, wie diese zur Bewertung der Programmleistung genutzt werden können:

• Call Graph: Der Call Graph ist eine grafische Darstellung der Funktionsaufrufe im Programm. Er zeigt, welche Funktionen andere Funktionen aufrufen und wie oft diese Aufrufe stattfinden. Diese Information hilft dabei, die Struktur des Programms zu verstehen und die kritischen Pfade zu identifizieren. Durch die Analyse des Call Graphs kann man feststellen, welche Funktionen am häufigsten aufgerufen werden und daher möglicherweise für Optimierungen in Betracht kommen.

• Flat Profile: Das Flat Profile ist eine tabellarische Darstellung, die zeigt, wie viel Zeit (sowohl in absoluten als auch in relativen Zahlen) in jeder Funktion des Programms verbracht wird. Diese Informationen helfen dabei, die Funktionen zu identifizieren, die für die meiste Rechenzeit verantwortlich sind. Durch das Optimieren dieser Funktionen kann die Gesamtleistung des Programms signifikant verbessert werden.

• Time Spent in Functions: gprof liefert auch detaillierte Informationen darüber, wie viel Zeit in jeder Funktion einschließlich der Aufgerufenen Funktionen (also der Kinderfunktionen) verbracht wird. Diese Information ist wichtig, um zu verstehen, wie die Rechenzeit zwischen den verschiedenen Funktionsebenen verteilt ist. Eine Funktion kann beispielsweise recht schnell sein, aber wenn sie viele aufwendige Kinderfunktionen aufruft, kann das die Gesamtleistung beeinträchtigen.

Diese Outputs von gprof sind sehr wertvoll für die Leistungsanalyse und -optimierung eines Programms. Durch das Verständnis dieser Metriken und die Identifikation von Engpässen kann man gezielte Optimierungen vornehmen, um die Effizienz und die Ausführungszeiten des Programms zu verbessern.

c)

c) Entwickle eine einfache mathematische Formel, die die Anzahl der Zyklen pro Instruktion (CPI) berechnet, wenn die Taktrate des Prozessors 2 GHz beträgt und das Programm 1.000.000 Zyklen für die Ausführung benötigt. Berechne den CPI-Wert für dieses Szenario.

Lösung:

Um die Anzahl der Zyklen pro Instruktion (CPI) zu berechnen, verwenden wir die bekannte Formel:

• \( \text{CPI} = \frac{\text{Gesamtanzahl der Zyklen}}{\text{Anzahl der Instruktionen}} \)

Die gegebenen Werte sind:

• Die Taktrate des Prozessors beträgt 2 GHz.
• Das Programm benötigt 1.000.000 Zyklen zur Ausführung.
• Das Programm führt 1.000.000 Instruktionen aus.

Schritt 1: Die Gesamtanzahl der Zyklen ist gegeben als 1.000.000 Zyklen.

• \( \text{Gesamtanzahl der Zyklen} = 1.000.000 \)

Schritt 2: Die Anzahl der Instruktionen ist ebenfalls 1.000.000 Instruktionen.

• \( \text{Anzahl der Instruktionen} = 1.000.000 \)

Schritt 3: Setzen wir diese Werte in die Formel ein:

• \( \text{CPI} = \frac{1.000.000 \text{ Zyklen}}{1.000.000 \text{ Instruktionen}} = 1 \)

Der CPI-Wert für dieses Szenario beträgt also:

• \( \text{CPI} = 1 \)

Dieser Wert bedeutet, dass der Prozessor im Durchschnitt einen Zyklus benötigt, um eine einzelne Instruktion auszuführen, was für viele moderne Prozessoren relativ effizient ist.

d)

d) Diskutiere die Vor- und Nachteile der Verwendung von FLOPS und MIPS als Metriken zur Bewertung der Leistung einer Rechnerarchitektur. Vergleiche dabei insbesondere die Situationen, in denen diese Metriken sinnvoll angewendet werden können, und erläutere, welche zusätzlichen Informationen benötigt werden, um eine vollständige Bewertung der Programmleistung vorzunehmen.

Lösung:

FLOPS (Floating Point Operations Per Second) und MIPS (Million Instructions Per Second) sind zwei häufig verwendete Metriken zur Bewertung der Leistung einer Rechnerarchitektur. Beide haben ihre Vor- und Nachteile, die im Folgenden diskutiert werden:

• FLOPS (Floating Point Operations Per Second):

• Vorteile:
• FLOPS ist eine nützliche Metrik für Anwendungen, die intensive Gleitkommaberechnungen durchführen, wie zum Beispiel wissenschaftliche Simulationen, maschinelles Lernen oder Grafikverarbeitung.
• Es ermöglicht die Bewertung der Leistungsfähigkeit von Rechenoperationen, die für numerische Berechnungen kritisch sind.
• Nachteile:
• FLOPS konzentriert sich nur auf Gleitkommaberechnungen und ignoriert andere wichtige Operationen wie Ganzzahloperationen, Speicherzugriffe und Steuerbefehle.
• Es spiegelt nicht die gesamte Systemleistung wider, insbesondere wenn das Programm umfangreiche nicht-numerische Berechnungen enthält.
• MIPS (Million Instructions Per Second):
• Vorteile:
• MIPS bietet eine allgemeine Metrik zur Bewertung der Ausführungsgeschwindigkeit eines Programms, da es die Anzahl der ausgeführten Instruktionen pro Zeit berücksichtigt.
• Es eignet sich gut für die Bewertung von Programmen mit einer Mischung aus verschiedenen Instruktionstypen.
• Nachteile:
• MIPS ist stark abhängig vom Instruktionssatz der jeweiligen Architektur, was den Vergleich zwischen unterschiedlichen Architekturen erschwert.
• Es berücksichtigt nicht die Komplexität der einzelnen Instruktionen, was dazu führen kann, dass Programme mit einfacheren Instruktionen künstlich besser abschneiden.
• Es misst nur die Anzahl der ausgeführten Instruktionen und nicht deren tatsächliche Ausführungseffizienz oder den inhärenten Arbeitsaufwand.

Vergleich und Anwendungsszenarien:

• FLOPS: FLOPS ist am sinnvollsten in Szenarien, in denen numerische Berechnungen im Vordergrund stehen, insbesondere bei wissenschaftlichen und technischen Anwendungen. Hier ist die Fähigkeit, viele Gleitkommaoperationen schnell auszuführen, entscheidend.
• MIPS: MIPS ist nützlich für allgemeine Programmme mit einer Vielzahl von Instruktionen, einschließlich System- und Anwendungssoftware. Es hilft dabei, die allgemeine Rechengeschwindigkeit und die Effizienz eines Prozessors zu bewerten.

Zusätzliche Informationen zur vollständigen Bewertung der Programmleistung:

• Latenz und Durchsatz: Es ist wichtig zu wissen, wie schnell einzelne Instruktionen ausgeführt werden können (Latenz) und wie viele Instruktionen parallel ausgeführt werden können (Durchsatz).
• Zyklen pro Instruktion (CPI): CPI hilft dabei zu verstehen, wie viele Taktzyklen im Durchschnitt pro Instruktion benötigt werden, was Aufschluss über die Effizienz der Instruktionsverarbeitung gibt.
• Speicherzugriffszeiten: Die Zeit, die für Speicherzugriffe benötigt wird, wie Cache-Zugriffszeiten und Hauptspeicherzugriffszeiten, ist entscheidend für die Gesamtleistung.
• Leistungsaufnahme und Energieeffizienz: In modernen Anwendungen ist auch die Energieeffizienz wichtig, um die Leistungsaufnahme zu minimieren und die Akkulaufzeit zu maximieren (bei mobilen Geräten) oder die Betriebskosten zu senken (bei Servern).
• Benchmarking mit realen Arbeitslasten: Es ist oft hilfreich, spezifische Benchmarks mit realen Arbeitslasten auszuführen, um eine realistische Bewertung der Leistung und Effizienz eines Systems zu erhalten.

Durch die Berücksichtigung dieser zusätzlichen Faktoren kann eine umfassendere und genauere Bewertung der Programmleistung und der Effizienz einer Rechnerarchitektur vorgenommen werden.

Aufgabe 4)

Speicherhierarchien und CachesSpeicherhierarchien minimieren Latenzen und steigern die Effizienz. Ein Cache speichert häufig benötigte Daten nahe der CPU. Die Hierarchieebenen umfassen Register, Cache (L1, L2, L3), Hauptspeicher und Sekundärspeicher. In Multi-Core-Systemen ist Cache-Kohärenz von großer Bedeutung. Es gibt mehrere Cache-Mapping-Methoden wie direktes, vollassoziatives und satzassoziatives Mapping. Cache Miss-Typen können in Cold, Conflict und Capacity Misses unterteilt werden.

a)

• (a) Cache-Kohärenz in Multi-Core-Systemen: Erläutere das Problem der Cache-Kohärenz in Multi-Core-Systemen und erkläre, wie das MESI-Protokoll (Modified, Exclusive, Shared, Invalid) zur Lösung dieses Problems beiträgt. Gehe dabei detailliert auf die Zustände und Übergänge des Protokolls ein und beschreibe eine typische Abfolge von Operationen, die zur Invalidierung eines Caches führen.
• (b) Cache Mapping und Miss-Typen: Angenommen, Du hast ein Cache-System mit einer Satzassoziativität von 4 Wegen und eine Cache-Größe von 16 KB, wobei jede Cache-Linie 64 Byte groß ist. Berechne die Anzahl der Sätze und die Anzahl der Index-Bits, die benötigt werden. Erläutere dann, wie die drei Miss-Typen (Cold, Conflict, Capacity) in diesem Kontext entstehen können und gib ein Beispiel für jeden Typ.

Lösung:

Speicherhierarchien und Caches

Speicherhierarchien minimieren Latenzen und steigern die Effizienz. Ein Cache speichert häufig benötigte Daten nahe der CPU. Die Hierarchieebenen umfassen Register, Cache (L1, L2, L3), Hauptspeicher und Sekundärspeicher. In Multi-Core-Systemen ist Cache-Kohärenz von großer Bedeutung. Es gibt mehrere Cache-Mapping-Methoden wie direktes, vollassoziatives und satzassoziatives Mapping. Cache Miss-Typen können in Cold, Conflict und Capacity Misses unterteilt werden.Im Folgenden werden die aufgelisteten Probleme gelöst:
• (a) Cache-Kohärenz in Multi-Core-Systemen:Das Problem der Cache-Kohärenz in Multi-Core-Systemen tritt auf, wenn mehrere Cores ihre eigenen lokalen Caches haben, aber auf gemeinsame Daten im Hauptspeicher zugreifen. Änderungen an Daten in einem Cache müssen den anderen Caches bekannt gemacht werden, um Konsistenz zu gewährleisten. Ohne Cache-Kohärenz könnten verschiedene Caches unterschiedliche Werte für dieselben Speicheradressen enthalten.Das MESI-Protokoll (Modified, Exclusive, Shared, Invalid) ist ein weit verbreitetes Cache-Kohärenzprotokoll, das dieses Problem löst. Es definiert vier Zustände für jede Cache-Linie:
  • Modified: Die Cache-Linie wird nur von einem Core genutzt und ist gegenüber dem Hauptspeicher geändert. Diese Linie muss in den Speicher zurückgeschrieben werden (write-back), wenn sie verdrängt wird.
  • Exclusive: Die Cache-Linie wird nur von einem Core genutzt und entspricht dem Wert im Hauptspeicher. Keine anderen Caches haben eine Kopie.
  • Shared: Die Cache-Linie kann in mehreren Caches existieren und entspricht dem Wert im Hauptspeicher.
  • Invalid: Die Cache-Linie ist ungültig und enthält keine nützlichen Daten.
  Zustandsübergänge im MESI-Protokoll:
  • Ein Read-Hit in einem beliebigen Zustand außer „Invalid“ lässt den Zustand unverändert.
  • Ein Write-Hit in „Exclusive“ ändert den Zustand zu „Modified“.
  • Ein Read-Miss oder Write-Miss kann zu verschiedenen Zustandsübergängen führen, entweder durch Lese- oder Schreibzugriffe von anderen Cores.
  • Beim Erhalt von invalidierenden Nachrichten können Zustände zu „Invalid“ wechseln.
  Beispiel für eine typische Abfolge von Operationen:1. Ein Core liest eine Cache-Linie und sie ist zunächst im Zustand „Invalid“.2. Ein Cache-Miss tritt auf, und die Cache-Linie wird in den Zustand „Shared“ oder „Exclusive“ versetzt, wenn kein anderer Core sie besitzt.3. Der Core schreibt in dieselbe Cache-Linie, ändert den Zustand zu „Modified“.4. Ein anderer Core möchte dieselbe Cache-Linie lesen, eine Invalidierungsnachricht wird gesendet und der erste Core inaktiviert seine Linie.
• (b) Cache Mapping und Miss-Typen:Gegeben ein Cache-System mit einer Satzassoziativität von 4 Wegen, einer Cache-Größe von 16 KB und jede Cache-Linie ist 64 Byte groß.Anzahl der Sätze:Die Anzahl der Cache-Linien kann berechnet werden als:

   Anzahl Cache-Linien = Cache-Größe / Cache-Liniengröße = 16 KB / 64 B = 256 

  Da die Satzassoziativität 4 ist, gibt es

   Anzahl der Sätze = Anzahl Cache-Linien / Satzassoziativität = 256 / 4 = 64 

  Anzahl der Index-Bits:Die Anzahl der Index-Bits kann durch logarithmieren der Anzahl der Sätze berechnet werden:

   Anzahl der Index-Bits = log2(64) = 6 

  Miss-Typen:
  • Cold Miss: Ein Cold Miss tritt auf, wenn Daten zum ersten Mal in den Cache geladen werden müssen. Beispiel: Ein Programm greift auf Daten zu, die noch nie zuvor verwendet wurden, wodurch eine Cold Miss auftritt.
  • Conflict Miss: Ein Conflict Miss tritt auf, wenn Cache-Linien innerhalb eines Satzes ersetzt werden, obwohl es noch freien Platz in anderen Sätzen gibt. Beispiel: Zwei oder mehr Datenblöcke, die kollidierende Adressen haben, konkurrieren um denselben Satz im Cache.
  • Capacity Miss: Ein Capacity Miss tritt auf, wenn der Cache nicht groß genug ist, um alle benötigten Daten zu speichern, und daher ältere Daten verdrängt werden müssen. Beispiel: Ein Programm greift auf mehr Daten zu, als im Cache Platz finden, was zur Auslagerung von Daten führt und eine erneute Anfrage erzeugt.