HPC Software Projekt - Exam

Aufgabe 1)

Ein wesentlicher Aspekt im Bereich des Hochleistungsrechnens (HPC) ist die Organisation der Speicherressourcen, wofür zwei Hauptansätze existieren: gemeinsam genutzter Speicher und verteilte Speicherarchitekturen. Gemeinsam genutzter Speicher ermöglicht mehreren Prozessoren den Zugriff auf denselben physischen Speicher, was zu einem einfacheren Programmiermodell führt, jedoch auch zu Datenzugriffengpässen führen kann. Ein Beispiel hierfür ist Symmetric Multiprocessing (SMP). Bei verteilten Speicherarchitekturen besitzt jeder Prozessor seinen eigenen lokalen Speicher. Dies erlaubt eine bessere Skalierbarkeit durch das Hinzufügen weiterer Knoten, erfordert jedoch Datenbewegung über ein Netzwerk. Ein Beispiel hierfür ist Massively Parallel Processing (MPP).

a)

Vergleiche die Vor- und Nachteile von gemeinsam genutztem Speicher und verteilten Speicherarchitekturen. Diskutiere hierbei insbesondere den Einfluss auf die Skalierbarkeit und die Datenzugriffszeiten.

Lösung:

Vergleich der Vor- und Nachteile von gemeinsam genutztem Speicher und verteilten Speicherarchitekturen

• Gemeinsam genutzter Speicher (Shared Memory)

• Vorteile:
• Einfacheres Programmiermodell: Da alle Prozessoren auf denselben physischen Speicher zugreifen können, ist die Programmierung im Allgemeinen einfacher. Es ist keine explizite Datenverteilung notwendig.
• Direkter Zugriff: Prozessoren können direkt auf alle Daten im gemeinsamen Speicher zugreifen, was die Kommunikation zwischen Prozessoren erleichtert.
• Nachteile:
• Datenzugriffengpässe: Bei vielen Prozessoren kann es zu Konkurrenz um den Speicherzugriff kommen, was zu Engpässen und Wartezeiten führt.
• Begrenzte Skalierbarkeit: Die Skalierbarkeit ist begrenzt, da der gemeinsame Speicher und die damit verbundenen Speicherbusse mit steigender Prozessanzahl überlastet werden können.
• Verteilte Speicherarchitektur (Distributed Memory)
• Vorteile:
• Skalierbarkeit: Da jeder Prozessor seinen eigenen lokalen Speicher hat, kann das System durch Hinzufügen weiterer Knoten leicht skaliert werden, ohne dass ein Engpass im Speicherzugriff entsteht.
• Geringere Konkurrenz: Es gibt keine zentrale Speichereinheit, um die konkurriert werden muss; jeder Prozessor bedient seinen eigenen Speicher, was die Zugriffszeiten verringern kann.
• Nachteile:
• Komplexeres Programmiermodell: Entwickler müssen explizit Daten zwischen Prozessoren verschieben und synchronisieren, was die Programmierung komplexer und fehleranfälliger macht.
• Netzwerküberlastung: Da Daten zwischen Prozessoren über ein Netzwerk verschoben werden müssen, kann eine hohe Netzwerkbelastung zu längeren Datenzugriffszeiten und insgesamt zu Verzögerungen führen.

Einfluss auf die Skalierbarkeit und Datenzugriffszeiten

• Gemeinsam genutzter Speicher:Die Skalierbarkeit ist limitiert, da der gemeinsame Zugriff auf denselben Speicherbereich bei einer hohen Anzahl an Prozessoren zu Engpässen und Wartezeiten führen kann. Die Datenzugriffszeiten sind im Allgemeinen schneller, solange der Speicherzugriff nicht überlastet ist.
• Verteilte Speicherarchitektur:Die Skalierbarkeit ist besser, da jeder Prozessor auf seinen eigenen Speicher zugreift und damit keine Engpässe entstehen. Allerdings können die Datenzugriffszeiten länger sein, wenn Daten über das Netzwerk verschoben werden müssen. Hierbei spielt die Netzwerklatenz eine wesentliche Rolle.

b)

Berechne die theoretische maximale Bandbreite einer verteilten Speicherarchitektur mit 8 Knoten, wobei jeder Knoten eine Bandbreite von 10 GB/s hat. Gehe davon aus, dass die Kommunikation zwischen den Knoten vernachlässigbar ist.

Lösung:

Berechnung der theoretischen maximalen Bandbreite einer verteilten Speicherarchitektur

• Wir haben eine verteilte Speicherarchitektur mit 8 Knoten.
• Jeder Knoten hat eine Bandbreite von 10 GB/s.
• Es wird angenommen, dass die Kommunikation zwischen den Knoten vernachlässigbar ist.

Schritt-für-Schritt-Berechnung

• 1. Bestimme die Bandbreite eines einzelnen Knotens:Bandbreite_Knoten = 10 GB/s
• 2. Multipliziere die Bandbreite eines Knotens mit der Anzahl der Knoten:Insgesamt_Bandbreite = Anzahl_Knoten × Bandbreite_Knoten= 8 × 10 GB/s= 80 GB/s

Ergebnis

Die theoretische maximale Bandbreite der verteilten Speicherarchitektur mit 8 Knoten beträgt 80 GB/s.

c)

Implementiere einen algorithmischen Ansatz (in Python oder pseudocode), der zeigt, wie Daten in einem System mit gemeinsam genutztem Speicher synchronisiert werden können, um Datenzugriffengpässe zu minimieren.

Lösung:

Algorithmischer Ansatz zur Synchronisierung von Daten in einem System mit gemeinsam genutztem Speicher

Im Folgenden wird ein allgemeiner algorithmischer Ansatz gezeigt, wie Daten in einem System mit gemeinsam genutztem Speicher synchronisiert werden können, um Datenzugriffengpässe zu minimieren. Hier verwenden wir Pseudo-Code, um den Algorithmus darzustellen. Der Ansatz verwendet Sperren (Locks), um zu gewährleisten, dass nur ein Prozess gleichzeitig auf den kritischen Abschnitt zugreifen kann.

Pseudo-Code zur Synchronisierung

// Initialisierung von Variablenshared_data = 0 // Gemeinsame Datenresourcemutex_lock = False // Sperre für den kritischen Abschnitt// Funktion zum Sperrenfunction lock(mutex):    while mutex == True: // Warten, bis Sperre frei ist        pass    mutex = True // Sperre setzen// Funktion zum Entsperrenfunction unlock(mutex):    mutex = False // Sperre freigeben// Funktion zum Ändern der gemeinsamen Datenresourcefunction modify_shared_data():    lock(mutex_lock) // Kritischen Abschnitt sperren    // Kritischer Abschnitt - Start    shared_data = shared_data + 1 // Gemeinsame Daten ändern    // Kritischer Abschnitt - Ende    unlock(mutex_lock) // Kritischen Abschnitt entsperren// Hauptteil des Programms// Simuliert mehrere Threads, die auf die gemeinsamen Daten zugreifenfor i from 1 to number_of_threads do:    start_thread(modify_shared_data)// threads synchronisieren... (Hier könnte eine Logik zur Synchronisierung und zum Warten auf alle Threads implementiert werden)

Erklärung des Algorithmus

• Initialisierung:Die gemeinsame Datenresource (shared_data) und die Sperre (mutex_lock) werden initialisiert.
• Sperren und Entsperren:Zwei Funktionen (lock und unlock) werden definiert, um den kritischen Abschnitt zu sperren und freizugeben, wobei die Sperre in einem einfachen Spinlock-Verfahren implementiert wird.
• Änderung der gemeinsamen Daten:Die Funktion modify_shared_data sperrt den kritischen Abschnitt, ändert die Daten und entsperrt ihn danach wieder. Dies stellt sicher, dass keine zwei Threads gleichzeitig die gemeinsamen Daten ändern.
• Threads starten:Im Hauptteil des Programms werden mehrere Threads gestartet, die alle die modify_shared_data-Funktion ausführen. Eine Logik zur Synchronisierung/Warten der Threads könnte nach dem Start eingefügt werden, um sicherzustellen, dass alle Threads ihre Arbeit beenden.

Aufgabe 2)

In einem Hochleistungsrechenzentrum soll eine numerische Simulation durchgeführt werden. Diese Simulation nutzt sowohl OpenMP als auch MPI, um die Berechnung effizient zu parallelisieren. Die Simulation berechnet numerische Lösungen eines physikalischen Problems und benötigt sowohl eine gemeinsame Speicherarchitektur (OpenMP) für Multi-Threading auf Einzelknoten als auch eine verteilte Speicherarchitektur (MPI) für die Kommunikation zwischen mehreren Knoten im Cluster. Das Programm ist so konzipiert, dass es große Matrizen und Vektoren verarbeitet und eine effiziente Lastverteilung und Synchronisation gewährleistet ist.

a)

Erkläre, wie Du die OpenMP-Direktive `#pragma omp parallel for` nutzen würdest, um eine Schleife für die Matrixmultiplikation zu parallelisieren. Schreibe den entsprechenden Code und erläutere kurz die einzelnen Teile.

Lösung:

Um eine Schleife zur Matrixmultiplikation mit der OpenMP-Direktive #pragma omp parallel for zu parallelisieren, müsste der Code wie folgt angepasst werden:

#include <omp.h> #include <stdio.h> #define N 1000  void matrixMultiplication(double A[N][N], double B[N][N], double C[N][N]) {    int i, j, k;      // Initialisiere die Ergebnis-Matrix C     #pragma omp parallel for private(i, j)     for (i = 0; i < N; i++) {        for (j = 0; j < N; j++) {            C[i][j] = 0.0;         }    }     // Parallelisiere die äußere Schleife     #pragma omp parallel for private(i, j, k)     for (i = 0; i < N; i++) {        for (j = 0; j < N; j++) {            for (k = 0; k < N; k++) {                C[i][j] += A[i][k] * B[k][j];             }        }    }} int main() {    double A[N][N], B[N][N], C[N][N];      // Initialisiere die Matrizen A und B mit Beispieldaten     #pragma omp parallel for private(i, j)     for (int i = 0; i < N; i++) {        for (int j = 0; j < N; j++) {            A[i][j] = (double)(i * j);             B[i][j] = (double)(i + j);         }    }     // Führe die Matrixmultiplikation durch     matrixMultiplication(A, B, C);      // Optional: Ergebnis ausgeben oder weiterverarbeiten      return 0; }

Erklärung der einzelnen Teile:

• #pragma omp parallel for: Diese Direktive veranlasst den Compiler, die nachfolgende Schleife parallel auszuführen. Jeder Thread erhält einen Teil der Iterationen zur Berechnung.
• private(i, j, k): Diese Klausel stellt sicher, dass jede Iterationsvariable innerhalb des Thread-Kontexts lokal bleibt, sodass Threads unabhängig voneinander darauf zugreifen können.
• Initalisierung der Ergebnis-Matrix C: Diese Schleife setzt alle Elemente von C auf 0.0, wobei die Arbeit gleichmäßig auf die Threads verteilt wird.
• Matrixmultiplikation: Die äußere Schleife, die über Zeilen von Matrix A iteriert, wird parallelisiert. Jeder Thread berechnet bestimmte Zeilen von C, was die Ausführungszeit reduziert.

b)

Beschreibe, wie MPI für die Kommunikation zwischen verschiedenen Knoten in einem Cluster verwendet wird. Erkläre die Funktionen `MPI_Send` und `MPI_Recv` und illustriere deren Anwendung anhand eines Beispiels, in dem ein Vektor von einem Knoten an einen anderen gesendet wird.

Lösung:

MPI (Message Passing Interface) wird verwendet, um die Kommunikation zwischen verschiedenen Knoten in einem Cluster zu ermöglichen. Dies ist besonders nützlich bei numerischen Simulationen, bei denen große Datenmengen zwischen den Knoten ausgetauscht werden müssen. Zwei grundlegende Funktionen zur Punkt-zu-Punkt-Kommunikation in MPI sind MPI_Send und MPI_Recv.

• MPI_Send: Diese Funktion wird verwendet, um Daten von einem Prozess an einen anderen zu senden.
  • Signatur:

    int MPI_Send(void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm);

  • Parameter:
    • buf: Zeiger auf das zu sendende Datenpuffer.
    • count: Anzahl der zu sendenden Elemente.
    • datatype: Typ der zu sendenden Elemente (z.B. MPI_INT).
    • dest: Rang des Zielprozesses.
    • tag: Nachrichtentag zur Unterscheidung verschiedener Nachrichten.
    • comm: Kommunikations-Communicator (z.B. MPI_COMM_WORLD).
• MPI_Recv: Diese Funktion wird verwendet, um Daten von einem anderen Prozess zu empfangen.
  • Signatur:

    int MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status);

  • Parameter:
    • buf: Zeiger auf das Empfangspuffer.
    • count: Anzahl der zu empfangenden Elemente.
    • datatype: Typ der zu empfangenden Elemente (z.B. MPI_INT).
    • source: Rang des sendenden Prozesses.
    • tag: Nachrichtentag zur Unterscheidung verschiedener Nachrichten.
    • comm: Kommunikations-Communicator (z.B. MPI_COMM_WORLD).
    • status: Statusobjekt zur Überprüfung der Nachricht.

Hier ist ein Beispiel, das zeigt, wie ein Vektor von einem Knoten an einen anderen gesendet wird:

#include <mpi.h> #include <stdio.h> #define N 100  int main(int argc, char *argv[]) {    int rank, size;    int vector[N];     MPI_Init(&argc, &argv);    MPI_Comm_rank(MPI_COMM_WORLD, &rank);    MPI_Comm_size(MPI_COMM_WORLD, &size);     if (rank == 0) {        // Initialisiere den Vektor mit Beispieldaten        for (int i = 0; i < N; i++) {            vector[i] = i;        }         // Sende den Vektor an den Prozess mit Rang 1        MPI_Send(vector, N, MPI_INT, 1, 0, MPI_COMM_WORLD);        printf("Prozess 0 hat den Vektor gesendet.");    } else if (rank == 1) {        // Empfange den Vektor        MPI_Recv(vector, N, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);        printf("Prozess 1 hat den Vektor empfangen.");    }     MPI_Finalize();    return 0;}

Erklärung des Beispiels:

• Initialisierung: MPI_Init initialisiert das MPI-Umfeld und MPI_Comm_rank sowie MPI_Comm_size geben den Rang bzw. die Größe des Kommunikators an.
• Rank 0: Der Prozess mit Rang 0 füllt den Vektor mit Daten und sendet ihn dann mit MPI_Send an den Prozess mit Rang 1.
• Rank 1: Der Prozess mit Rang 1 empfängt den Vektor mit MPI_Recv.
• Finalisierung: MPI_Finalize schließt das MPI-Umfeld.

Aufgabe 3)

In einem Softwareprojekt für Hochleistungsrechnen (High Performance Computing, HPC) an der Universität Erlangen-Nürnberg soll ein Programm entwickelt werden, das mehrere Threads zur gleichzeitigen Verarbeitung von Daten verwendet. Während der Entwicklung treten im Programm Race Conditions auf, was in unvorhersehbarem Verhalten des Programms resultiert. Um diese Race Conditions zu vermeiden und zu beheben, stehen dir verschiedene Ansätze zur Verfügung, wie z.B. die Nutzung von Sperren (Locks), atomaren Operationen und Synchronisationsmechanismen, sowie verschiedene Design-Strategien und Tools zur Überprüfung auf Race Conditions.

a)

Implementiere einen Thread-sicheren Zähler in Python, der mit mehreren Threads gleichzeitig inkrementiert werden kann, ohne dass Race Conditions auftreten. Verwende dazu Sperren (Locks). Dein Programm sollte wie folgt aussehen: Ein Hauptprogramm erstellt mehrere Threads, die alle die gleiche Zählerfunktion aufrufen. Nutze die Klasse `threading.Lock` in Python. Achte darauf, dass der Zähler korrekt inkrementiert und am Ende die richtige Anzahl angezeigt wird. Schreibe die Implementierung des Zählers und des Hauptprogramms. Beispiel Ausgabe: Wenn 10 Threads jeweils den Zähler 1000-mal inkrementieren, sollte der endgültige Zählerwert 10000 sein.

import threadingclass SafeCounter:    def __init__(self):        self.value = 0        self.lock = threading.Lock()    def increment(self):        with self.lock:            self.value += 1    def get_value(self):        return self.valueif __name__ == '__main__':    counter = SafeCounter()    threads = []    def worker():        for _ in range(1000):            counter.increment()    for _ in range(10):        thread = threading.Thread(target=worker)        threads.append(thread)        thread.start()    for thread in threads:        thread.join()    print(f'Endgültiger Zählerwert: {counter.get_value()}')

Lösung:

Hier ist eine mögliche Implementierung eines thread-sicheren Zählers in Python unter Verwendung von Sperren (Locks):

import threadingclass SafeCounter:    def __init__(self):        self.value = 0        self.lock = threading.Lock()    def increment(self):        with self.lock:            self.value += 1    def get_value(self):        return self.valueif __name__ == '__main__':    counter = SafeCounter()    threads = []    def worker():        for _ in range(1000):            counter.increment()    for _ in range(10):        thread = threading.Thread(target=worker)        threads.append(thread)        thread.start()    for thread in threads:        thread.join()    print(f'Endgültiger Zählerwert: {counter.get_value()}')

Wichtige Schritte in der Implementierung:

• Erstelle eine Klasse SafeCounter, die einen Zählerwert und eine Lock-Instanz enthält.
• Die Methode increment erhöht den Zählerwert innerhalb eines with self.lock-Blocks, um eine Race Condition zu verhindern.
• Die Methode get_value gibt den aktuellen Zählerwert zurück.
• Im Hauptprogramm werden mehrere Threads erstellt, die jeweils die worker-Funktion ausführen und den Zähler inkrementieren.
• Nach dem Starten der Threads wird auf deren Fertigstellung gewartet, indem thread.join() verwendet wird.
• Am Ende wird der endgültige Zählerwert ausgegeben. Wenn 10 Threads jeweils den Zähler 1000-mal inkrementieren, sollte der endgültige Zählerwert 10000 sein.

Diese Implementierung stellt sicher, dass keine Race Conditions auftreten und der Zähler korrekt inkrementiert wird.

b)

In einem anderen Anwendungsfall sollen geteilte Zustände vermieden werden, um Race Conditions zu verhindern. Dies kann durch die Verwendung von Immutable-Objekten oder Thread-Local Storage erreicht werden. Erkläre die Konzepte von Immutable-Objekten und Thread-Local Storage und beschreibe, wie sie helfen können, Race Conditions zu vermeiden. Erstelle dann ein kurzes Beispiel in Python, das Thread-Local Storage verwendet, um einem ähnlichen Problem wie im ersten Teil der Aufgabe zu begegnen. Dein Beispiel sollte einen Zähler beinhalten, der in jedem Thread separat gehalten wird, ohne dass Race Conditions auftreten können.

import threadingclass ThreadLocalCounter:    def __init__(self):        self.local = threading.local()    def increment(self):        if not hasattr(self.local, 'value'):            self.local.value = 0        self.local.value += 1    def get_value(self):        return getattr(self.local, 'value', 0)if __name__ == '__main__':    counter = ThreadLocalCounter()    results = []    threads = []    def worker():        for _ in range(1000):            counter.increment()        results.append(counter.get_value())    for _ in range(10):        thread = threading.Thread(target=worker)        threads.append(thread)        thread.start()    for thread in threads:        thread.join()    print(f'Endgültige Zählerwerte: {results}')

Lösung:

Um Race Conditions zu vermeiden, können wir zwei Konzepte nutzen:

• Immutable-Objekte: Immutable-Objekte sind Objekte, die nach ihrer Erstellung nicht mehr verändert werden können. Da sie nach ihrer Erstellung konstant bleiben, können keine Race Conditions auftreten, da mehrere Threads nicht gleichzeitig auf dasselbe Objekt zugreifen und es ändern können. Ein Beispiel für ein Immutable-Objekt in Python ist ein Tuple.
• Thread-Local Storage: Thread-Local Storage ermöglicht es, Daten an einen bestimmten Thread zu binden, sodass jeder Thread seine eigene Ausgabe hat, ohne dass gemeinsame Zustände geteilt werden. Dies verhindert, dass mehrere Threads auf denselben Speicherbereich zugreifen und ihn ändern. In Python wird dies durch die Klasse threading.local() bereitgestellt.

Das folgende Beispiel zeigt, wie man Thread-Local Storage in Python verwendet, um einen Zähler in jedem Thread separat zu halten, ohne dass Race Conditions auftreten können:

import threadingclass ThreadLocalCounter:    def __init__(self):        self.local = threading.local()    def increment(self):        if not hasattr(self.local, 'value'):            self.local.value = 0        self.local.value += 1    def get_value(self):        return getattr(self.local, 'value', 0)if __name__ == '__main__':    counter = ThreadLocalCounter()    results = []    threads = []    def worker():        for _ in range(1000):            counter.increment()        results.append(counter.get_value())    for _ in range(10):        thread = threading.Thread(target=worker)        threads.append(thread)        thread.start()    for thread in threads:        thread.join()    print(f'Endgültige Zählerwerte: {results}')

Wichtige Schritte in der Implementierung:

• Erstelle eine Klasse ThreadLocalCounter, die ein Attribute local hat, das eine Instanz von threading.local() ist.
• Die Methode increment prüft, ob local.value existiert. Wenn nicht, wird er auf 0 gesetzt. Danach wird er inkrementiert.
• Die Methode get_value gibt den aktuellen Zählerwert des lokalen Threads zurück.
• Im Hauptprogramm werden mehrere Threads erstellt, die jeweils die worker-Funktion ausführen und den Zähler inkrementieren.
• Nach dem Starten der Threads wird auf deren Fertigstellung gewartet, indem thread.join() verwendet wird.
• Am Ende werden die endgültigen Zählerwerte jedes Threads ausgegeben.

Durch die Verwendung von threading.local() haben wir erreicht, dass jeder Thread seinen eigenen Zählerwert hat und somit keine Race Conditions auftreten.

Aufgabe 4)

Du arbeitest an einem HPC-Softwareprojekt, bei dem die Performanz der Anwendung stark von der effizienten Nutzung verschiedener Speicherhierarchien abhängt. Du möchtest den Cache gezielt optimieren, um Cache-Misses zu minimieren und die Gesamtleistung zu maximieren. Die Speicherhierarchien umfassen Register, L1, L2 und L3 Caches sowie den Hauptspeicher.

a)

Implementiere eine Funktion in C, die eine große Matrix multiplikativ transponiert und dabei die Cache-Effizienz berücksichtigt. Erkläre dabei, wie Deine Implementierung Cache-Misses minimiert und daher die Leistung der Anwendung verbessert. Nutze dabei möglichst sequentielle Speicherzugriffe und berücksichtige Cache-Ausrichtungen.

Lösung:

Funktion zur Multiplikation und Transposition einer großen Matrix in C mit Cache-Optimierung

Um die Cache-Effizienz zu maximieren und Cache-Misses zu minimieren, ist es wichtig, dass sequentielle Speicherzugriffe und Cache-Ausrichtungen bei der Implementierung der Matrixtransposition berücksichtigt werden. Eine bewährte Methode hierfür ist das Blockieren der Matrizen, um sicherzustellen, dass die Zugriffe in jedem Block im Cache bleiben und somit die Ausführung beschleunigen.

Implementierung der Funktion

Hier ist eine Beispielimplementierung in C, die eine Matrix transponiert und dabei Cache-Optimierungstechniken nutzt:

#include <stdio.h>#include <stdlib.h>#define BLOCKSIZE 32void transposeMatrix(int *src, int *dest, int size) {int i, j, bi, bj;for (bi = 0; bi < size; bi += BLOCKSIZE) {for (bj = 0; bj < size; bj += BLOCKSIZE) {for (i = bi; i < bi + BLOCKSIZE && i < size; i++) {for (j = bj; j < bj + BLOCKSIZE && j < size; j++) {dest[j * size + i] = src[i * size + j];}}}}}int main() {int size = 1024;int *src = (int *)malloc(size * size * sizeof(int));int *dest = (int *)malloc(size * size * sizeof(int));for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {src[i * size + j] = i * size + j;}}transposeMatrix(src, dest, size);free(src);free(dest);return 0;}

Erklärung des Ansatzes zur Cache-Optimierung

• Blockweise Verarbeitung: Durch die Verwendung von BLOCKSIZE wird die Matrix in kleinere Blöcke unterteilt. Dies stellt sicher, dass die Daten, die in einem Block verwendet werden, im Cache bleiben und nicht durch andere Speicherzugriffe verdrängt werden.
• Sequentielle Speicherzugriffe: Innerhalb eines Blocks erfolgen die Speicherzugriffe sequentiell, wodurch die Wahrscheinlichkeit erhöht wird, dass die nächsten Speicherzugriffe im Cache gefunden werden.
• Vermeidung von Cache-Misses: Durch die Blockierung und sequentiellen Zugriffsmuster wird die Nutzung des Caches maximiert und die Anzahl der Cache-Misses reduziert. Dies führt zu einer Verbesserung der Gesamtleistung, da der Zugriff auf den Hauptspeicher minimiert wird.

Mit dieser Implementierung und den beschriebenen Optimierungstechniken kannst Du die Cache-Effizienz der Matrixtransposition erheblich verbessern und somit die Leistung Deiner HPC-Anwendung steigern.

b)

Gegeben sei folgende Schleifenstruktur zur Multiplikation zweier Matrizen in einem HPC-Umfeld in C:

for (int i = 0; i < N; i++) {    for (int j = 0; j < N; j++) {        for (int k = 0; k < N; k++) {            C[i][j] += A[i][k] * B[k][j];        }    }}

Lösung:

Analyse der Cache-Effizienz und Optimierung der Schleifenstruktur zur Matrixmultiplikation

Betrachten wir zunächst die gegebene Schleifenstruktur zur Matrixmultiplikation in C:

for (int i = 0; i < N; i++) {    for (int j = 0; j < N; j++) {        for (int k = 0; k < N; k++) {            C[i][j] += A[i][k] * B[k][j];        }    }}

Analyse der Cache-Effizienz

In der aktuellen Implementierung gibt es mehrere Probleme bezüglich der Cache-Effizienz:

• Die Matrix A wird zeilenweise (sequentiell) durchlaufen, was gut für den Cache ist.
• Die Matrix B wird jedoch spaltenweise durchlaufen, was zu zahlreichen Cache-Misses führen kann, da die Speicherzugriffe nicht sequentiell erfolgen.
• Die Matrix C wird ebenfalls sequentiell durchlaufen, was wiederum vorteilhaft ist.

Optimierung durch Blockierung (Tiling)

Eine effiziente Methode zur Verbesserung der Cache-Effizienz ist die Blockierung (auch Tiling genannt). Dadurch wird die Schleifenstruktur so geändert, dass kleine Blöcke bearbeitet werden, die besser in den Cache passen und somit Cache-Misses reduziert werden.

#define BLOCK_SIZE 32for (int i = 0; i < N; i += BLOCK_SIZE) {    for (int j = 0; j < N; j += BLOCK_SIZE) {        for (int k = 0; k < N; k += BLOCK_SIZE) {            for (int ii = i; ii < i + BLOCK_SIZE && ii < N; ii++) {                for (int jj = j; jj < j + BLOCK_SIZE && jj < N; jj++) {                    for (int kk = k; kk < k + BLOCK_SIZE && kk < N; kk++) {                        C[ii][jj] += A[ii][kk] * B[kk][jj];                    }                }            }        }    }}

Optimierung durch Prefetching

Zusätzlich zur Blockierung kann Prefetching verwendet werden, um Daten in den Cache zu laden, bevor sie tatsächlich benötigt werden. Moderne Prozessoren unterstützen oft Hardware-Prefetching, aber explizites Prefetching kann in manchen Fällen von Vorteil sein.

#define PREFETCH_DISTANCE 4for (int i = 0; i < N; i += BLOCK_SIZE) {    for (int j = 0; j < N; j += BLOCK_SIZE) {        for (int k = 0; k < N; k += BLOCK_SIZE) {            for (int ii = i; ii < i + BLOCK_SIZE && ii < N; ii++) {                for (int jj = j; jj < j + BLOCK_SIZE && jj < N; jj++) {                    for (int kk = k; kk < k + BLOCK_SIZE && kk < N; kk++) {                        __builtin_prefetch(&A[ii][kk + PREFETCH_DISTANCE], 0, 1);                        __builtin_prefetch(&B[kk + PREFETCH_DISTANCE][jj], 0, 1);                        C[ii][jj] += A[ii][kk] * B[kk][jj];                    }                }            }        }    }}

Theoretischer Performance-Gewinn

Angenommen, die Cache-Trefferquote wird durch die Optimierungen um 30% verbessert, können wir den theoretischen Performance-Gewinn folgendermaßen berechnen:

• Cache-Hit-Zeit: etwa 1-2 Clockzyklen
• Cache-Miss-Latenz: etwa 100 Clockzyklen (Zugriff auf Hauptspeicher)

Ohne Optimierung:

• Cache-Trefferquote: 50%
• Erwartete Zeit pro Zugriff: \(0.5 \times 1 + 0.5 \times 100 = 50.5\) Clockzyklen

Mit Optimierung:

• Cache-Trefferquote: 80%
• Erwartete Zeit pro Zugriff: \(0.8 \times 1 + 0.2 \times 100 = 20.8\) Clockzyklen

Theoretischer Performance-Gewinn:

• Performance-Gewinn-Verhältnis: \(\frac{50.5}{20.8} \times 100\% \approx 2.43\text{ (243%)}\)

Die Optimierungen könnten theoretisch zu einem Performance-Zuwachs von etwa 2.43x (oder 143%) führen. Die tatsächliche Verbesserung hängt jedoch von vielen Faktoren ab, wie der spezifischen Hardware und anderen Optimierungen, die bereits angewendet wurden.

c)

Erkläre das Konzept der Speicheraffinität in einem HPC-System. Beschreibe, wie Du die Speicheraffinität in Deiner Anwendung verbessern kannst und welche Auswirkungen dies auf die Cache-Leistung und die Gesamtleistung hat. Gib konkrete Beispiele für typische Maßnahmen zur Steigerung der Speicheraffinität in parallelen Anwendungen. Berechne die potentielle Leistungssteigerung bei einer 10%igen Verringerung der Speicherzugriffszeit.

Lösung:

Das Konzept der Speicheraffinität in einem HPC-System

Speicheraffinität bezieht sich auf die Praxis, die Daten möglichst nahe bei den Recheneinheiten zu halten, die sie nutzen sollen. In einem HPC-System kann dies bedeuten, dass Daten in dem Speicher abgespeichert werden, der zu den entsprechenden Rechenkernen gehört. Die Verbesserung der Speicheraffinität kann die Cache-Leistung erhöhen, indem Cache-Misses und Zugriffe auf den langsamen Hauptspeicher reduziert werden. Dies führt zu einer besseren Gesamtleistung der Anwendung.

Verbesserung der Speicheraffinität

Um die Speicheraffinität in einer Anwendung zu verbessern, können folgende Maßnahmen ergriffen werden:

• Datenlokalität sicherstellen: Teile die Daten so auf, dass sie physisch nahe bei den Threads oder Prozessen liegen, die sie nutzen.
• Nutzung von First-Touch-Platzierung: Initialisiere Datenstrukturen auf dem Kern, der sie später nutzt. Dies stellt sicher, dass der Speicher nahe bei diesem Kern alloziert wird.
• Thread-Bindung: Weise Threads explizit bestimmten Kernen oder Knoten zu, wodurch die Daten in dem zugehörigen lokalen Speicherbereich bleiben.
• Nutzung von NUMA-Aware Datenstrukturen: Entwickle und verwende Datenstrukturen, die die Nicht-Einheitliche Speicherarchitektur (NUMA) unterstützen, um die Speicheraffinität zu erhöhen.
• Speicherbindung: Verwende Tools oder API-Anrufe, um zu steuern, wo die Speichersegmente platziert werden (z. B. numa_alloc_onnode in Linux).

Beispiele zur Steigerung der Speicheraffinität in parallelen Anwendungen

Ein typisches Szenario könnte eine parallele Matrixmultiplikation auf einem NUMA-System sein. Durch die Verbesserung der Speicheraffinität könnte die Anwendung beschleunigt werden:

#include <numa.h>#include <omp.h>#define N 1024#define BLOCK_SIZE 64void matrixMultiply(double **A, double **B, double **C, int size) {    #pragma omp parallel for    for (int i = 0; i < size; i++) {        for (int j = 0; j < size; j++) {            double sum = 0.0;            for (int k = 0; k < size; k++) {                sum += A[i][k] * B[k][j];            }            C[i][j] = sum;        }    }}int main() {    // Speicher auf dem ersten NUMA-Knoten reservieren    numa_set_preferred(0);    double **A = numa_alloc_onnode(N * sizeof(double *), 0);    double **B = numa_alloc_onnode(N * sizeof(double *), 0);    double **C = numa_alloc_onnode(N * sizeof(double *), 0);    for (int i = 0; i < N; i++) {        A[i] = numa_alloc_onnode(N * sizeof(double), 0);        B[i] = numa_alloc_onnode(N * sizeof(double), 0);        C[i] = numa_alloc_onnode(N * sizeof(double), 0);    }    // Matrixmulitplikation    matrixMultiply(A, B, C, N);    return 0;}

Berechnung der potentiellen Leistungssteigerung

Angenommen, durch die Verbesserung der Speicheraffinität wird die Speicherzugriffszeit um 10% reduziert. Die Gesamtleistung der Anwendung besteht sowohl aus der Rechenzeit als auch aus der Speicherzugriffszeit. Nehmen wir an, dass die ursprüngliche Speicherzugriffszeit T_mem und die Rechenzeit T_comp beträgt. Dann beträgt die Gesamtzeit T_tot = T_mem + T_comp.

Nach der Reduzierung der Speicherzugriffszeit:

• T'_mem = 0.9 \times T_mem
• Die neue Gesamtzeit T'_tot = T'_mem + T_comp
• = 0.9 T_mem + T_comp

Die Leistungssteigerung ist dann:

• Performance-Gewinn-Verhältnis = \(\frac{T_{tot}}{T'_{tot}}\)
• = \(\frac{T_{mem} + T_{comp}}{0.9 T_{mem} + T_{comp}}\)

Beispiel:

Angenommen, die ursprüngliche Speicherzugriffszeit beträgt 70% der Gesamtzeit und die Rechenzeit beträgt 30% der Gesamtzeit:

• T_mem = 0.7
• T_comp = 0.3

Neue Gesamtzeit:

• T'_tot = 0.9 \times 0.7 + 0.3 = 0.63 + 0.3 = 0.93

Leistungssteigerung:

• Performance-Gewinn-Verhältnis = \(\frac{1}{0.93}\) = 1.075
• Entsprechende 7.5% Steigerung.

Durch die Verbesserung der Speicheraffinität und die Reduktion der Speicherzugriffszeit kann daher eine signifikante Leistungssteigerung erzielt werden.