Programmiertechniken für Supercomputer - Exam

Aufgabe 1)

MPI (Message Passing Interface) und numerische SimulationenGegeben ist eine numerische Simulation auf einem verteilten Speichersystem, welche durch eine Gruppe von Prozessen parallelisiert werden soll. Diese Prozesse kommunizieren über MPI und tauschen Nachrichten aus, um die Berechnung effizient zu gestalten. Jeder Prozess berechnet einen Teil der Gesamtsimulation und die Ergebnisse müssen am Ende der Berechnung gesammelt und synchronisiert werden. Verwende hierzu \texttt{MPI\textunderscore Send} und \texttt{MPI\textunderscore Recv}, um die Kommunikation zwischen den Prozessen zu implementieren. Die Simulation besteht aus einer 2D-Gitter-Berechnung, bei der das Gitter in kleinere Sub-Gitter aufgeteilt wird, die dann den einzelnen Prozessen zugewiesen werden. Nach einer bestimmten Anzahl von Iterationen müssen die Sub-Gitter wieder zusammengesetzt werden.

a)

Implementiere den initialen Datenaustausch zwischen den Prozessen, bei dem jeder Prozess sein Sub-Gitter vom Hauptprozess (Prozess 0) erhält. Verwende \texttt{MPI\textunderscore Send} und \texttt{MPI\textunderscore Recv} für die Kommunikation. Stelle sicher, dass alle Prozesse ihren Datenanteil korrekt erhalten.

Lösung:

Um den initialen Datenaustausch zwischen den Prozessen zu implementieren, bei dem jeder Prozess sein Sub-Gitter vom Hauptprozess (Prozess 0) erhält, können wir die MPI_Send- und MPI_Recv-Funktionen verwenden. Hier ist ein Beispiel, wie dies mit MPI in Python (using mpi4py) realisiert werden könnte:

 from mpi4py import MPI  import numpy as np   comm = MPI.COMM_WORLD  rank = comm.Get_rank()  size = comm.Get_size()   # Dimensionen des 2D-Gitters  grid_size = (8, 8)   # Sub-Gitter-Dimensionen  sub_grid_size = (grid_size[0] // size, grid_size[1])   if rank == 0:  # Hauptprozess generiert das komplette Gitter  grid = np.arange(grid_size[0] * grid_size[1]).reshape(grid_size)   # Senden Sie das entsprechende Sub-Gitter an jeden Prozess  for i in range(1, size):  start_row = i * sub_grid_size[0]  end_row = start_row + sub_grid_size[0]  sub_grid = grid[start_row:end_row, :]  comm.Send(sub_grid, dest=i, tag=0)   # Hauptprozess erhält sein eigenes Sub-Gitter  own_sub_grid = grid[0:sub_grid_size[0], :]  else:  # Alle anderen Prozesse empfangen ihr Sub-Gitter vom Hauptprozess  own_sub_grid = np.empty(sub_grid_size, dtype=int)  comm.Recv(own_sub_grid, source=0, tag=0)   # Ausgabe zur Überprüfung  print(f'Prozess {rank} empfängt Sub-Gitter:', own_sub_grid)  

• Initialisierung und Festlegung der Sub-Gitter: Der Hauptprozess (Prozess 0) generiert das komplette 2D-Gitter und teilt es in Sub-Gitter auf. Jedes Sub-Gitter wird entsprechend der Anzahl der Prozesse berechnet.
• Kommunikation mit MPI: Der Hauptprozess sendet die jeweiligen Sub-Gitter an alle anderen Prozesse (Ranks 1 bis N-1) unter Verwendung der MPI_Send-Funktion. Jeder der anderen Prozesse empfängt sein Sub-Gitter mithilfe der MPI_Recv-Funktion.
• Überprüfung: Jeder Prozess gibt sein empfangenes Sub-Gitter zur Überprüfung aus, um sicherzustellen, dass der Datenaustausch korrekt stattgefunden hat.

So kannst Du sicherstellen, dass jeder Prozess seinen Datenanteil korrekt erhält. Vergiss nicht, dass beim Fein-Tuning und bei größeren Simulationen zusätzliche Faktoren wie Fehlertoleranz und Overheads berücksichtigt werden müssen.

b)

Nach Abschluss der Berechnung müssen die Sub-Gitter wieder an den Hauptprozess zurückgesendet und zusammengeführt werden. Implementiere dies unter Verwendung der kollektiven Operation \texttt{MPI\textunderscore Gather}. Erkläre, wie \texttt{MPI\textunderscore Gather} in diesem Szenario funktioniert und welche Herausforderungen es bei der Implementierung gibt.

Lösung:

Um nach Abschluss der Berechnung die Sub-Gitter wieder an den Hauptprozess zurückzusenden und zusammenzuführen, können wir die kollektive Operation MPI_Gather verwenden. Hier ist eine Beispielimplementierung mit Python (mittels mpi4py), um zu zeigen, wie dies funktioniert:

 from mpi4py import MPI  import numpy as np   comm = MPI.COMM_WORLD  rank = comm.Get_rank()  size = comm.Get_size()   # Dimensionen des 2D-Gitters  grid_size = (8, 8)   # Sub-Gitter-Dimensionen  sub_grid_size = (grid_size[0] // size, grid_size[1])   if rank == 0:  # Hauptprozess generiert das komplette Gitter (nur zu Demonstrationszwecken)  grid = np.arange(grid_size[0] * grid_size[1]).reshape(grid_size)  else:  grid = None   # Hier würde eine numerische Berechnung stattfinden  # Jeder Prozess nimmt an, dass er ein Sub-Gitter hat  if rank == 0:  own_sub_grid = grid[0:sub_grid_size[0], :]  else:  own_sub_grid = np.empty(sub_grid_size, dtype=int)   # Simulation der Berechnung durch Addition von 100 * rank  own_sub_grid += 100 * rank   # MPI_Gather, um Sub-Gitter zurück an den Hauptprozess zu senden  if rank == 0:  recv_buf = np.empty(grid_size, dtype=int)  else:  recv_buf = None   comm.Gather(own_sub_grid, recv_buf, root=0)   if rank == 0:  print('Gesammeltes Gitter:', recv_buf)  

• Initialisierung und Simulation der Berechnung: Im obigen Beispiel wird angenommen, dass jeder Prozess nach dem initialen Datenaustausch eine numerische Berechnung auf seinem Sub-Gitter durchführt (simuliert durch Addition von 100 * rank).
• MPI_Gather: Diese kollektive Operation wird verwendet, um die Sub-Gitter von allen Prozessen zu einem Buffer im Hauptprozess (Root) zu sammeln. Der recv_buf wird im Hauptprozess reserviert, um die empfangenen Daten zu speichern. Alle Sub-Gitter werden in der Reihenfolge der Rangs gesammelt und in den Empfangsbuffer kopiert.
• Herausforderungen bei der Implementierung:
  • Speicherverwaltung: Für große Simulationen kann die Speicheranforderung erheblich sein, insbesondere im Hauptprozess, der den gesamten Gitter-Buffer aufnehmen muss.
  • Synchronisierung: Die Sub-Gitter müssen in der richtigen Reihenfolge und ohne Datenverlust gesendet und empfangen werden. Eine präzise Synchronisation und korrektes Buffer-Management sind erforderlich.
  • Lastverteilung: Unterschiedliche Prozessgrößen können zu Ungleichgewichten in der Arbeitsverteilung führen, welche sich in der Ausführungsgeschwindigkeit und Gesamteffizienz niederschlagen können.

MPI_Gather ist ein leistungsstarkes Werkzeug, um Ergebnisse aus verteilten Prozessen in einem zentralen Prozess zu sammeln und wieder zusammenzuführen. Es ist entscheidend, die Implementierung sauber und effizient zu gestalten, um die Vorteile der parallelen Berechnung voll auszuschöpfen.

Aufgabe 2)

Angenommen, Du möchtest die Leistung einer rechenintensiven Aufgabe durch Parallelisierung optimieren. Dafür entscheidest Du Dich, die Berechnungen auf einer modernen GPU mithilfe von CUDA zu implementieren. Deine Aufgabe besteht darin, einen einfachen Vektor-Multiplikations-Kernel zu schreiben, diesen zu kompilieren und auszuführen sowie die Leistung zu analysieren und zu optimieren.

a)

Implementiere in CUDA einen Kernel, der die Elementweise Multiplikation zweier Vektoren übernimmt. Die Vektoren sollen jeweils 1024 Elemente enthalten. Füge den vollständigen CUDA-Code inklusive Speicherverwaltung und Datenübertragung zwischen Host und Device hinzu. Dokumentiere jeden Schritt innerhalb Deines Codes.

Lösung:

Um die elementweise Multiplikation zweier Vektoren mit jeweils 1024 Elementen in CUDA zu implementieren, folge den nachstehenden Schritten. Hierbei wird der Code gut dokumentiert und Schritt für Schritt erklärt.

Schritt 1: Inkludiere die notwendigen Header

#include <iostream>#include <cuda_runtime.h>using namespace std;

Schritt 2: Definiere die Vector Size Konstanten und den CUDA-Kernel für die elementweise Multiplikation

#define VECTOR_SIZE 1024__global__ void vectorMultiply(float *a, float *b, float *c, int n) {    int index = threadIdx.x + blockIdx.x * blockDim.x;    if(index < n) {        c[index] = a[index] * b[index];    }}

Schritt 3: Implementiere die Hauptfunktion

int main() {    int size = VECTOR_SIZE * sizeof(float);    // Allokiere Host-Speicher    float *h_a = (float*)malloc(size);    float *h_b = (float*)malloc(size);    float *h_c = (float*)malloc(size);    // Initialisiere Vektoren auf dem Host    for(int i = 0; i < VECTOR_SIZE; i++) {        h_a[i] = i;        h_b[i] = i*2;    }    // Allokiere Device-Speicher    float *d_a, *d_b, *d_c;    cudaMalloc((void **)&d_a, size);    cudaMalloc((void **)&d_b, size);    cudaMalloc((void **)&d_c, size);    // Kopiere Vektoren von Host zu Device    cudaMemcpy(d_a, h_a, size, cudaMemcpyHostToDevice);    cudaMemcpy(d_b, h_b, size, cudaMemcpyHostToDevice);    // Definiere Block- und Gridgröße    int blockSize = 256;    int gridSize = (VECTOR_SIZE + blockSize - 1) / blockSize;    // Starte den Kernel    vectorMultiply<<<gridSize, blockSize>>>(d_a, d_b, d_c, VECTOR_SIZE);    // Kopiere Ergebnis zurück zum Host    cudaMemcpy(h_c, d_c, size, cudaMemcpyDeviceToHost);    // Ausgabe der Ergebnisse    for(int i = 0; i < 10; i++) {        cout << "c[" << i << "] = " << h_c[i] << endl;    }    // Free GPU Speicher    cudaFree(d_a);    cudaFree(d_b);    cudaFree(d_c);    // Free CPU Speicher    free(h_a);    free(h_b);    free(h_c);    return 0;}

Dieser Code beschreibt alle Schritte von der Allokation des Speichers über die Datenübertragung bis hin zur Ausführung des CUDA-Kernels und der Rückübertragung der Ergebnisse. Damit kannst Du die Leistung der GPU für Vektormultiplikationen effektiv nutzen.

b)

Erläutere den Unterschied zwischen globalem, gemeinsamem und register-basiertem Speicher in der CUDA-Architektur. Welche Speicherarten kommen in Deinem implementierten Kernel zum Einsatz und warum?

Lösung:

In der CUDA-Architektur gibt es verschiedene Arten von Speicher, die für unterschiedliche Zwecke genutzt werden können. Hier ist ein Überblick über globalen, gemeinsamen und register-basierten Speicher:

• Globaler Speicher:- Dies ist der Hauptspeicher der GPU und kann von allen Threads in einem Grid gelesen und beschrieben werden.- Er ist relativ langsam im Vergleich zu anderen Speicherarten, hat aber eine hohe Kapazität.- In unserem implementierten Kernel wird der globale Speicher genutzt, um die Vektoren a, b und das Ergebnis c zu speichern. Wir verwenden globalen Speicher, weil die Daten zwischen Host (CPU) und Device (GPU) übertragen werden müssen und der globale Speicher für diese Aufgabe geeignet ist.
• Gemeinsamer Speicher (shared memory):- Dies ist ein schnellerer Speicherbereich, der nur von Threads innerhalb eines Blocks geteilt wird. Jeder Block hat seinen eigenen Bereich im gemeinsamen Speicher.- Er ist wesentlich schneller als globaler Speicher, insbesondere bei Kommunikationsmuster innerhalb eines Blocks.- In unserem Kernel verwenden wir keinen gemeinsamen Speicher, da der Fokus auf der elementweisen Multiplikation der Vektoren liegt und jedes Element unabhängig von den anderen berechnet werden kann.
• Register-basierter Speicher:- Dies ist der schnellste Speicher in der CUDA-Architektur und befindet sich direkt auf dem Chip.- Jedem Thread stehen eine begrenzte Anzahl von Registern zur Verfügung. Register werden für Variablen verwendet, die intensives Computing benötigen.- In unserem Kernel wird der register-basierte Speicher automatisch vom Compiler verwendet, um lokale Variablen wie index und die temporären Speicherorte zu verwalten.

Zusammenfassend kommen in unserem Kernel hauptsächlich globaler Speicher und register-basierter Speicher zum Einsatz. Der globale Speicher wird zur Speicherung der Vektoren und zur Kommunikation zwischen Host und Device verwendet, während der register-basierte Speicher für die Berechnung innerhalb der Threads genutzt wird, da er die geringste Latenz aufweist.

c)

Messe die Ausführungszeit Deines CUDA-Kernels mithilfe von CUDA-Ereignissen (cudaEvent_t). Implementiere den entsprechenden Code und dokumentiere die gemessenen Zeiten. Vergleiche die Leistung mit einer entsprechenden seriellen Implementierung auf der CPU. Wo liegen die Vorteile und Nachteile der CUDA-Implementierung im Vergleich zur seriellen, CPU-basierten Version?

Lösung:

Um die Ausführungszeit eines CUDA-Kernels zu messen, können wir die CUDA-Ereignisse (cudaEvent_t) verwenden. Das folgende Beispiel zeigt, wie Du das machst und wie Du die gemessenen Zeiten dokumentierst und vergleichst:

Schritt 1: Inkludiere die notwendigen Header

#include <iostream>#include <cuda_runtime.h>#include <chrono>using namespace std;

Schritt 2: Definiere die Vector Size Konstanten und den CUDA-Kernel für die elementweise Multiplikation (gleicher wie vorher)

#define VECTOR_SIZE 1024__global__ void vectorMultiply(float *a, float *b, float *c, int n) {    int index = threadIdx.x + blockIdx.x * blockDim.x;    if(index < n) {        c[index] = a[index] * b[index];    }}

Schritt 3: Implementiere die Hauptfunktion mit Zeitmessung

int main() {    int size = VECTOR_SIZE * sizeof(float);    // Allokiere Host-Speicher    float *h_a = (float*)malloc(size);    float *h_b = (float*)malloc(size);    float *h_c = (float*)malloc(size);    // Initialisiere Vektoren auf dem Host    for(int i = 0; i < VECTOR_SIZE; i++) {        h_a[i] = i;        h_b[i] = i*2;    }    // Allokiere Device-Speicher    float *d_a, *d_b, *d_c;    cudaMalloc((void **)&d_a, size);    cudaMalloc((void **)&d_b, size);    cudaMalloc((void **)&d_c, size);    // Kopiere Vektoren von Host zu Device    cudaMemcpy(d_a, h_a, size, cudaMemcpyHostToDevice);    cudaMemcpy(d_b, h_b, size, cudaMemcpyHostToDevice);    // Erstelle Ereignisse zur Zeitmessung    cudaEvent_t start, stop;    cudaEventCreate(&start);    cudaEventCreate(&stop);    // Starte Ereignis und Kernel    cudaEventRecord(start);    int blockSize = 256;    int gridSize = (VECTOR_SIZE + blockSize - 1) / blockSize;    vectorMultiply<<<gridSize, blockSize>>>(d_a, d_b, d_c, VECTOR_SIZE);    cudaEventRecord(stop);    // Warten auf das Ende des Events    cudaEventSynchronize(stop);    // Berechne die verstrichene Zeit    float milliseconds = 0;    cudaEventElapsedTime(&milliseconds, start, stop);    // Kopiere Ergebnis zurück zum Host    cudaMemcpy(h_c, d_c, size, cudaMemcpyDeviceToHost);    // Ausgabe der Ergebnisse    for(int i = 0; i < 10; i++) {        cout << "c[" << i << "] = " << h_c[i] << endl;    }    cout << "CUDA Kernel Time: " << milliseconds << " ms" << endl;    // Berechne die gleiche Operation seriell auf der CPU    auto cpu_start = chrono::high_resolution_clock::now();    for(int i = 0; i < VECTOR_SIZE; i++) {        h_c[i] = h_a[i] * h_b[i];    }    auto cpu_end = chrono::high_resolution_clock::now();    chrono::duration<float, milli> cpu_duration = cpu_end - cpu_start;    cout << "CPU Time: " << cpu_duration.count() << " ms" << endl;    // Free GPU Speicher    cudaFree(d_a);    cudaFree(d_b);    cudaFree(d_c);    // Free CPU Speicher    free(h_a);    free(h_b);    free(h_c);    return 0;}

Dokumentation der gemessenen Zeiten:- Die CUDA-Ausführungszeit des Kernels wird mit cudaEventElapsedTime gemessen und in Millisekunden ausgegeben.- Die CPU-Ausführungszeit wird mit der C++ chrono Bibliothek gemessen und ebenfalls in Millisekunden ausgegeben.

Vergleich der Leistung:

• Vorteile der CUDA-Implementierung:- Hohe Parallelität: Die GPU kann viele Operationen gleichzeitig ausführen, was insbesondere bei großen Datensätzen zu erheblichen Geschwindigkeitsvorteilen führt.- Effiziente Nutzung der GPU-Ressourcen: Die CUDA-Architektur ist optimiert für rechenintensive Aufgaben.
• Nachteile der CUDA-Implementierung:- Datenübertragungszeit: Das Kopieren von Daten zwischen Host und Device kann eine Flaschenhals sein und müsste im Timing berücksichtigt werden.- Komplexität: Das Schreiben und Debuggen von CUDA-Code kann komplexer sein als sequentieller CPU-Code.

d)

Diskutiere, wie Du die Leistung Deines CUDA-Programms weiter optimieren könntest. Gehe dabei insbesondere auf Themen wie Coalesced Memory Access und Thread Divergence ein. Welche Änderungen würdest Du vornehmen, um die Effizienz zu maximieren?

Lösung:

Um die Leistung eines CUDA-Programms weiter zu optimieren, gibt es verschiedene Aspekte, die berücksichtigt werden können. Zwei der wichtigsten sind Coalesced Memory Access und Thread Divergence. Hier sind diese beiden Konzepte sowie mögliche Optimierungsansätze ausführlich dargestellt:

• Coalesced Memory Access:- Coalesced Memory Access beschreibt die effiziente Datenzugriffsstrategie, bei der mehrere parallele Threads der GPU gleichzeitig auf zusammenhängende Speicheradressen im globalen Speicher zugreifen.- Dies minimiert die Speicherlatenz und maximiert die Bandbreitenausnutzung.- In unserem Kernel könnte dieses Konzept betrachtet werden, indem wir sicherstellen, dass Vektorelemente, die von benachbarten Threads verarbeitet werden, in aufeinanderfolgenden Speicheradressen liegen.
• Thread Divergence:- Thread Divergence tritt auf, wenn Threads innerhalb desselben Warp (ein Warp ist eine Gruppe von 32 Threads) unterschiedliche Ausführungspfade durchlaufen.- Dies führt dazu, dass die parallele Ausführung unterbrochen wird und die Leistung sinkt.- In unserem Kernel verhindern wir Thread Divergence weitgehend, da alle Threads die gleiche Operation (Multiplikation) auf unterschiedlichen Daten ausführen.- Um Thread Divergence zu vermeiden, sollten bedingungsabhängige Codeblöcke minimiert oder entfernt werden.

Weitere Optimierungsansätze:

• Gemeinsamer Speicher (Shared Memory):- Häufig verwendete Daten können im gemeinsamen Speicher (Shared Memory) zwischengespeichert werden, um die Zugriffzeit zu verringern.- Obwohl wir in unserem Beispiel keinen gemeinsamen Speicher verwenden, könnten wir dies in einem fortgeschrittenen Szenario sinnvoll nutzen, um Daten zwischen Threads innerhalb eines Blocks effizient zu teilen.- Dies könnte hilfreich sein, wenn wir beispielsweise mehrere Vektoroperationen durchführen müssen, bei denen Zwischenergebnisse zwischen den Threads kommuniziert werden müssen.
• Optimierung der Block- und Gridgröße:- Die Wahl von Block- und Gridgröße ist entscheidend für die Leistungsoptimierung.- Kleine Blöcke können die Nutzung der Rechenressourcen verschlechtern, während zu große Blöcke möglicherweise nicht die optimale Anzahl von Threads pro Block enthalten.- Experimente mit unterschiedlichen Blockgrößen können helfen, eine optimale Konfiguration zu finden. In unserem Fall verwenden wir blockSize = 256, aber diese Größe könnte auf Basis spezifischer Hardware-Spezifikationen und der Struktur des Problems weiter optimiert werden.
• Überlappung von Berechnung und Datenübertragung:- Eine leistungsstarke Optimierung besteht darin, Berechnungen auf der GPU und Datenübertragungen zwischen Host und Device zu überlappen.- Dies kann durch Verwendung von asynchronen CUDA-Streams realisiert werden, die es ermöglichen, Datenübertragungen und Kernel-Ausführungen gleichzeitig durchzuführen und somit die Gesamtzeit zu reduzieren.
• Profiling-Werkzeuge:- Profiler wie NVIDIA Nsight Compute oder nvprof ermöglichen es, Engpässe im CUDA-Code zu identifizieren.- Durch die Analyse der Profilergebnisse können gezielte Optimierungen vorgenommen werden, sei es in Speicherzugriffen, Recheneffizienz oder Latenzzeiten.

Durch die Anwendung dieser Optimierungstechniken kannst Du die Effizienz Deines CUDA-Programms erheblich steigern und die Vorteile paralleler Berechnungen auf einer GPU optimal nutzen.

Aufgabe 3)

Du hast einen sequentiellen Algorithmus, der eine große Matrixmultiplikation durchführt. Diesen Algorithmus sollst Du nun parallelisieren, um die Ausführungszeit auf einem Mehrkernprozessor zu verkürzen. Nutze dafür OpenMP und berücksichtige die Themen Compiler-Direktiven, Variablen, Synchronisation und Performanceanalyse.

a)

Modifiziere den folgenden sequentiellen Code zur Matrixmultiplikation, sodass er OpenMP zur Parallelisierung nutzt. Achte darauf, dass die Threads die Berechnungen korrekt aufteilen und keine Datenkonflikte auftreten. Nutze dabei die Direktiven #pragma omp parallel und #pragma omp for.

'#include #include void matrix_multiplication(int n, int A[n][n], int B[n][n], int C[n][n]) {    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            C[i][j] = 0;            for (int k = 0; k < n; k++) {                C[i][j] += A[i][k] * B[k][j];            }        }    }}int main() {    int n = 1000;    int (*A)[n] = malloc(n * n * sizeof(int));    int (*B)[n] = malloc(n * n * sizeof(int));    int (*C)[n] = malloc(n * n * sizeof(int));    // Initialisiere Matrizen A und B hier    matrix_multiplication(n, A, B, C);    free(A);    free(B);    free(C);    return 0;}'

Lösung:

Um den sequentiellen Code zur Matrixmultiplikation zu parallelisieren, kannst Du OpenMP benutzen. Dabei ist es wichtig, die Berechnungen korrekt auf die Threads zu verteilen und sicherzustellen, dass keine Datenkonflikte auftreten. Die benötigten OpenMP-Direktiven hierfür sind #pragma omp parallel und #pragma omp for.

Hier ist der modifizierte Code:

'#include #include #include void matrix_multiplication(int n, int A[n][n], int B[n][n], int C[n][n]) {    #pragma omp parallel for collapse(2)    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            C[i][j] = 0;            for (int k = 0; k < n; k++) {                C[i][j] += A[i][k] * B[k][j];            }        }    }}int main() {    int n = 1000;    int (*A)[n] = malloc(n * n * sizeof(int));    int (*B)[n] = malloc(n * n * sizeof(int));    int (*C)[n] = malloc(n * n * sizeof(int));    // Initialisiere Matrizen A und B hier        #pragma omp parallel for collapse(2)    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            A[i][j] = rand() % 100;            B[i][j] = rand() % 100;        }    }    matrix_multiplication(n, A, B, C);    free(A);    free(B);    free(C);    return 0;}'

• OpenMP-Direktiven: Durch #pragma omp parallel for collapse(2) werden die äußeren beiden Schleifen parallelisiert. Dadurch wird sichergestellt, dass die Arbeit der Schleifen effizient auf mehrere Threads verteilt wird.
• Initialisierung: Auch die Initialisierung der Matrizen A und B wird parallelisiert, um die Performance zu verbessern.
• Synchronisation: Da jede Thread-Gruppe an unterschiedlichen Indizes der Matrix arbeitet, treten keine Datenkonflikte auf.

b)

Betrachte nun die Variablen in Deinem parallelen Code. Erkläre, welche Variablen private und welche shared sein sollten und warum. Modifiziere den Code entsprechend.

Lösung:

In OpenMP müssen Variablen als private oder shared deklariert werden, um eine korrekte Parallelisierung zu gewährleisten. Hier ist eine Erklärung, welche Variablen private und welche shared sein sollten und warum:

• shared: Variablen, die für alle Threads sichtbar und von ihnen gemeinsam verwendet werden. Dies sind typischerweise Variablen, die von allen Threads gelesen, aber nicht gleichzeitig geschrieben werden, oder das übergeordnete Array, auf das alle Threads zugreifen.
• private: Variablen, die nur innerhalb eines bestimmten Threads existieren und von anderen Threads nicht beeinflusst werden. Dies sind oft Variablen, die innerhalb einer Schleife iterieren oder temporäre Ergebnisse speichern.

Für diesen Fall:

• shared: Die Arrays A, B und C sollten shared sein, da alle Threads auf dieselben Matrizen zugreifen.
• private: Die Schleifenvariablen i, j und k sollten private sein, da jede Iteration einer Schleife unabhängig voneinander ist und jeder Thread seine eigenen Schleifenvariablen benötigt.

Hier ist der angepasste Code:

'#include #include #include void matrix_multiplication(int n, int A[n][n], int B[n][n], int C[n][n]) {    #pragma omp parallel for collapse(2) shared(A, B, C) private(i, j, k)    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            C[i][j] = 0;            for (int k = 0; k < n; k++) {                C[i][j] += A[i][k] * B[k][j];            }        }    }}int main() {    int n = 1000;    int (*A)[n] = malloc(n * n * sizeof(int));    int (*B)[n] = malloc(n * n * sizeof(int));    int (*C)[n] = malloc(n * n * sizeof(int));    // Initialisiere Matrizen A und B hier        #pragma omp parallel for collapse(2) shared(A, B) private(i, j)    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            A[i][j] = rand() % 100;            B[i][j] = rand() % 100;        }    }    matrix_multiplication(n, A, B, C);    free(A);    free(B);    free(C);    return 0;}'

• shared: Die Arrays A, B und C sind shared, da alle Threads auf dieselben Daten zugreifen.
• private: Die Schleifenvariablen i, j und k sind private und dadurch für jeden Thread individuell.
• Hinweis: Die korrekte Deklaration und Synchronisation der Variablen erhöht die Stabilität und Performance des parallelen Codes.

Aufgabe 4)

Profiling von Supercomputer-AnwendungenDu arbeitest an der Leistungsanalyse einer großen wissenschaftlichen Anwendung, die auf einem Supercomputer ausgeführt wird. Um die Performance zu verbessern, entschließt Du dich, Profiling-Tools wie Gprof und VTune einzusetzen. Beantworte die folgenden Fragen, um zu zeigen, dass Du die Werkzeuge und ihren Nutzen verstehst.

a)

Beschreibe den grundlegenden Unterschied zwischen Sampling und Instrumentierung in Gprof. Warum könnte man sich für das eine oder das andere Verfahren entscheiden?

Lösung:

Grundlegender Unterschied zwischen Sampling und Instrumentierung in Gprof:

• Sampling: Beim Sampling erstellt Gprof periodische Momentaufnahmen (z.B. jede Millisekunde) des Programms, um festzustellen, welche Funktionen gerade ausgeführt werden. Diese Momentaufnahmen werden dann verwendet, um ein statistisches Profil der Programmausführung zu erstellen. Sampling ist weniger invasiv, da es keine zusätzlichen Anweisungen in den Programmcode einfügt. Es hat eine geringere Performanzbeeinträchtigung und ist daher oft schneller.Vorteile von Sampling:
  • Geringere Laufzeit-Overhead
  • Kann in Produktionsumgebungen verwendet werden
  • Einfache Konfiguration
• Instrumentierung: Bei der Instrumentierung fügt Gprof Anweisungen in den Quellcode oder den ausführbaren Code deines Programms ein, um detaillierte Daten über den Ablauf des Programms zu sammeln. Diese Daten umfassen z.B. die Anzahl der Aufrufe sowie Ein- und Austrittszeiten von Funktionen. Instrumentierung bietet genaue und detaillierte Ergebnisse, verursacht aber zusätzlichen Laufzeit-Overhead durch die Hinzufügung von Überwachungscode.Vorteile von Instrumentierung:
  • Detaillierte Funktionsaufrufstatistik
  • Genauere Messwerte
  • Gut geeignet für kleinere Programme oder spezifische Codeabschnitte

• Sampling: Wenn die Reduktion des Laufzeit-Overheads im Fokus steht und eine grobe Übersicht der Performance ausreichend ist. Es ist besonders nützlich für große Anwendungen oder Produktionsumgebungen, bei denen der zusätzliche Overhead durch Instrumentierung inakzeptabel wäre.
• Instrumentierung: Wenn detaillierte Informationen über spezifische Bereiche des Codes benötigt werden und der zusätzliche Laufzeit-Overhead akzeptabel ist. Es eignet sich gut für die Analyse kleinerer Programme oder wenn man tiefergehende Einblicke in die Leistungsdetails spezifischer Funktionen erhalten möchte.

b)

Mathematikaufgabe: Angenommen, Du analysierst mit VTune die Speicherzugriffe einer Funktion. Du stellst fest, dass die Cache-Miss-Rate 15 % beträgt und die Funktion insgesamt 1.000.000 Speicherzugriffe durchführt. Berechne die Anzahl der Cache-Misses und erkläre, wie sich hohe Cache-Miss-Raten auf die Leistung einer Anwendung auswirken können. Hinweis: Die Cache-Miss-Rate ist definiert als der Anteil der Speicherzugriffe, bei denen Daten nicht im Cache gefunden werden.

Lösung:

Berechnung der Anzahl der Cache-Misses:Um die Anzahl der Cache-Misses zu berechnen, verwenden wir die Formel für die Cache-Miss-Rate:

• Cache-Miss-Rate = (Anzahl der Cache-Misses) / (Gesamtanzahl der Speicherzugriffe)

• Cache-Miss-Rate = 15 % = 0.15
• Gesamtanzahl der Speicherzugriffe = 1.000.000

• Anzahl der Cache-Misses = Cache-Miss-Rate * Gesamtanzahl der Speicherzugriffe= 0.15 * 1.000.000= 150.000

• Erhöhte Speicherlatenz: Wenn Daten nicht im Cache gefunden werden, muss der Prozessor die Daten aus dem Hauptspeicher abrufen, was erheblich mehr Zeit in Anspruch nimmt als der Zugriff auf den Cache. Dies führt zu erhöhten Wartezeiten und verringert die Gesamtleistung des Programms.
• Geringere CPU-Auslastung: Hohe Cache-Miss-Raten führen dazu, dass der Prozessor häufiger untätig ist, da er auf die Datenladevorgänge aus dem Hauptspeicher warten muss. Dies kann die CPU-Auslastung senken und somit die Effizienz des gesamten Systems beeinträchtigen.
• Erhöhte Energieverbrauch: Cache-Misses verursachen mehr Energieverbrauch, da zusätzliche Speicheroperationen durchgeführt werden müssen. Dies kann insbesondere bei Anwendungen, die auf Energieeffizienz angewiesen sind, nachteilig sein.
• Reduzierte Anwendungsleistung: Hohe Cache-Miss-Raten verlangsamen die Gesamtverarbeitungsgeschwindigkeit der Anwendung, da mehr Zeit auf Speicherzugriffe verwendet wird. Dies kann die Reaktionszeit und Durchsatzleistung der Anwendung verringern.
• Potenzielle Skalierungsprobleme: In großen verteilten Systemen kann eine hohe Cache-Miss-Rate dazu führen, dass die Synchronisation und der Datenaustausch zwischen verschiedenen Knoten beeinträchtigt wird, was die Skalierbarkeit des Systems verringert.