Architekturen von Superrechnern - Exam.pdf

Architekturen von Superrechnern - Exam

Architekturen von Superrechnern - Exam Aufgabe 1) In den 1950er bis 1970er Jahren entstanden die ersten Supercomputer, die aufgrund ihrer fortschrittlichen Hardware-Innovationen eine enorme Rechenleistung für ihre Zeit erbrachten. Zu den bekanntesten Beispielen zählen der ENIAC (1945), der als erster elektronischer Universalrechner auf Vakuumröhren basierte, und der CDC 6600 (1964), entwickelt von...

Architekturen von Superrechnern - Exam

Aufgabe 1)

In den 1950er bis 1970er Jahren entstanden die ersten Supercomputer, die aufgrund ihrer fortschrittlichen Hardware-Innovationen eine enorme Rechenleistung für ihre Zeit erbrachten. Zu den bekanntesten Beispielen zählen der ENIAC (1945), der als erster elektronischer Universalrechner auf Vakuumröhren basierte, und der CDC 6600 (1964), entwickelt von Seymour Cray, der als erster echter Supercomputer gilt. Weitere Meilensteine waren das IBM System/360 (1964), das die Einführung einer kompatiblen Mainframe-Architektur markierte, und der Cray-1 (1976), der durch seine Vektor-Architektur und innovative Design-Techniken große Leistungssprünge erzielte. Wesentliche Technologien dieser frühen Supercomputer waren Pipelining, Parallelverarbeitung und Vektorprozessoren.

a)

(a) Erkläre die Unterschiede zwischen den technologischen Ansätzen von ENIAC und CDC 6600. Gehe dabei insbesondere auf die verwendeten Komponenten und die Art der Rechenprozesse ein.

Lösung:

ENIAC (1945): Der ENIAC (Electronic Numerical Integrator and Computer) war einer der ersten elektronischen Universalrechner und verwendete Vakuumröhren zur Datenverarbeitung. Hier einige wesentliche Merkmale:

Komponenten: Der ENIAC bestand aus etwa 17.468 Vakuumröhren, 7.200 Dioden, 70.000 Widerständen, 10.000 Kondensatoren und 6.000 Schaltern. Diese Vakuumröhren trugen maßgeblich zur enormen Größe und dem hohen Energieverbrauch des Systems bei.
Rechenprozesse: Der ENIAC führte Rechenoperationen sequentiell durch, was bedeutet, dass er eine Aufgabe nach der anderen abarbeitete. Mit dieser Architektur konnte er rund 5.000 Additionen oder 357 Multiplikationen pro Sekunde durchführen.

CDC 6600 (1964):

Komponenten: Anstelle von Vakuumröhren verwendete der CDC 6600 Transistoren, was eine kompaktere Bauweise sowie eine höhere Zuverlässigkeit und geringeren Energieverbrauch ermöglichte. Der CDC 6600 hatte rund 400.000 Transistoren und war wesentlich kleiner und effizienter als der ENIAC.
Rechenprozesse: Der CDC 6600 führte erstmals Pipelining und Parallelverarbeitung ein. Dies ermöglichte es dem Computer, mehrere Befehle gleichzeitig zu verarbeiten, was die Rechengeschwindigkeit erheblich steigerte. Mit einer Taktgeschwindigkeit von etwa 10 MHz konnte der CDC 6600 rund 3 Millionen Rechenoperationen pro Sekunde durchführen.

Zusammenfassung: Während der ENIAC auf Vakuumröhren und sequentieller Verarbeitung basierte, nutzte der CDC 6600 Transistoren und führte fortschrittliche Techniken wie Pipelining und Parallelverarbeitung ein. Dies führte zu sehr unterschiedlichen Leistungsniveaus, wobei der CDC 6600 erheblich schneller und effizienter war als der ENIAC.

b)

(b) Der IBM System/360 führte die Mainframe-Architektur ein, die kompatibel und skalierbar war. Diskutiere die Auswirkungen dieser Innovation auf die Entwicklung zukünftiger Computersysteme bis hin zu modernen Mainframes.

Lösung:

Einführung des IBM System/360: Das IBM System/360, eingeführt im Jahr 1964, war bahnbrechend, da es eine einheitliche und kompatible Mainframe-Architektur bot. Diese Innovation ermöglichte es, verschiedene Modelle innerhalb derselben Produktlinie zu haben, die alle die gleiche Software ausführen konnten. Hier sind die Hauptauswirkungen dieser Neuerung:

Kompatibilität und Skalierbarkeit: Zum ersten Mal konnte Software, die für ein Modell des System/360 entwickelt wurde, ohne Änderungen auf anderen Modellen derselben Reihe ausgeführt werden. Diese Kompatibilität senkte die Kosten und den Aufwand für Unternehmen, die ihre Systeme erweitern oder aufrüsten wollten.
Standardisierung: Die Einführung einer standardisierten Architektur half dabei, die Entwicklung von Software und Peripheriegeräten erheblich zu vereinfachen. Hersteller und Entwickler konnten sich auf diese Plattform verlassen und ihre Produkte darauf ausrichten.
Skalierbarkeit: Die verschiedenen Modelle des System/360 boten unterschiedliche Leistungsstufen, wodurch Unternehmen ihre Hardware je nach Bedarf skalieren konnten. Dies bedeutete, dass die anfängliche Investition in ein Computersystem nicht verloren war, wenn die Bedürfnisse des Unternehmens wuchsen.
Geschäftszweige: Durch die standardisierte Architektur und die breite Akzeptanz des Systems/360 konnten viele neue Geschäftszweige entstehen, die sich auf die Entwicklung von Software und Dienstleistungen für diese Plattform spezialisierten.
Langlebigkeit und Weiterentwicklung: Das Konzept der kompatiblen und skalierbaren Architektur des System/360 setzte Maßstäbe für zukünftige Computersysteme. Es legte den Grundstein für moderne Mainframe-Architekturen, die immer noch auf der Idee der Kompatibilität und Skalierbarkeit basieren.
Einfluss auf moderne Mainframes: Die Prinzipien, die mit dem IBM System/360 eingeführt wurden, sind in modernen Mainframes weiterhin relevant. Aktuelle Mainframes sind extrem leistungsfähig, bieten hohe Zuverlässigkeit und Verfügbarkeit, und können flexibel skaliert werden, um den Anforderungen moderner Unternehmen gerecht zu werden.

Zusammenfassung: Die Einführung der IBM System/360 Mainframe-Architektur hatte tiefgreifende Auswirkungen auf die Entwicklung zukünftiger Computersysteme. Sie legte den Grundstein für die Kompatibilität, Standardisierung und Skalierbarkeit, die heute in modernen Mainframes und anderen Computersystemen allgegenwärtig sind.

c)

(c) Der Cray-1 setzte auf eine Vektor-Architektur. Erstelle eine detaillierte mathematische Analyse, wie Vektorprozessoren bestimmte Rechenoperationen beschleunigen können, indem Du ein Beispiel für Vektoraddition und -multiplikation ausführst.

Lösung:

Vektor-Architektur des Cray-1: Der Cray-1 nutzte eine Vektor-Architektur, die darauf ausgelegt war, bestimmte Rechenoperationen, insbesondere solche mit großen Datenmengen, zu beschleunigen. Vektorprozessoren können Operationen auf ganzen Vektoren (Arrays von Daten) gleichzeitig ausführen, anstatt sie nacheinander zu bearbeiten. Dies führt zu erheblichen Leistungssteigerungen bei berechnungsintensiven Aufgaben.

Mathematische Analyse:

Vektoraddition: Betrachten wir zwei Vektoren \(\textbf{A}\) und \(\textbf{B}\), die beide die Länge \(n\) haben: \[\textbf{A} = [a_1, a_2, \.\.\., a_n] \] \[\textbf{B} = [b_1, b_2, \.\.\., b_n] \] Die Vektoraddition berechnet das Ergebnis \(\textbf{C}\) wie folgt: \[\textbf{C} = \textbf{A} + \textbf{B} = [a_1 + b_1, a_2 + b_2, \.\.\., a_n + b_n] \] Bei einem skalarbasierten Prozessor würde jede Addition einzeln durchgeführt: \[c_1 = a_1 + b_1 \] \[c_2 = a_2 + b_2 \] \.\.\. \[c_n = a_n + b_n \] Dies bedeutet \(n\) Additionen nacheinander. Bei einem Vektorprozessor kann diese Operation parallel erfolgen, indem alle \(n\) Additionen gleichzeitig ausgeführt werden. Dies reduziert die Gesamtdauer der Berechnung erheblich.

Vektormultiplikation (elementweise): Betrachten wir dieselben Vektoren \(\textbf{A}\) und \(\textbf{B}\). Die Vektormultiplikation berechnet das Ergebnis \(\textbf{D}\) wie folgt: \[\textbf{D} = \textbf{A} * \textbf{B} = [a_1 * b_1, a_2 * b_2, \.\.\., a_n * b_n] \] Bei einem skalarbasierten Prozessor würde jede Multiplikation einzeln durchgeführt: \[d_1 = a_1 * b_1 \] \[d_2 = a_2 * b_2 \] \.\.\. \[d_n = a_n * b_n \] Auch hier würde ein skalarbasierter Prozessor \(n\) Multiplikationen nacheinander ausführen, während ein Vektorprozessor dies parallel tun kann, was erneut zu einer erheblichen Reduktion der Berechnungszeit führt.

Beispiel:

     A = [1, 2, 3, 4]     B = [5, 6, 7, 8]     -> Vektoraddition     C = A + B = [1+5, 2+6, 3+7, 4+8]     C = [6, 8, 10, 12]     -> Vektormultiplikation     D = A * B = [1*5, 2*6, 3*7, 4*8]     D = [5, 12, 21, 32]

In diesem Beispiel führt ein Vektorprozessor alle Additionen und Multiplikationen gleichzeitig durch, während ein skalarbasierter Prozessor jede Operation einzeln durchführen würde, was mehr Zeit in Anspruch nimmt. Vektorprozessoren im Cray-1 können daher bestimmte Operationen, die auf Vektoren arbeiten, stark beschleunigen.

Zusammenfassung: Vektorprozessoren beschleunigen Rechenoperationen erheblich, indem sie parallele Verarbeitung auf Vektoren ermöglichen. Im Gegensatz zu skalarbasierten Prozessoren, die nacheinander arbeiten, können Vektorprozessoren Operationen wie Addition und Multiplikation gleichzeitig auf ganzen Arrays ausführen. Dies macht sie besonders effektiv für berechnungsintensive Aufgaben, wie sie im Cray-1 implementiert wurden.

d)

(d) Sowohl Pipelining als auch Parallelverarbeitung waren wichtige Technologien in den frühen Supercomputern. Vergleiche diese beiden Konzepte und erkläre anhand eines konkreten Beispiels aus der Praxis, wie sie zur Leistungssteigerung beigetragen haben.

Lösung:

Pipelining: Pipelining ist ein Konzept, bei dem verschiedene Stufen eines Berechnungsprozesses parallel ausgeführt werden. Jeder dieser Stufen (Pipeline-Abschnitte) führt einen Teil eines Befehls aus. Während eine Stufe an einem bestimmten Schritt arbeitet, arbeitet die nächste Stufe bereits am nachfolgenden Schritt des vorherigen Befehls. Dies führt zu einer Überlappung der Befehlsausführung, was die Gesamtdurchsatzrate des Systems erhöht.

Parallelverarbeitung: Parallelverarbeitung bedeutet, dass mehrere Prozessoren oder Recheneinheiten gleichzeitig an verschiedenen Teilen eines Problems arbeiten. Im Gegensatz zum Pipelining, das die Ausführung eines einzelnen Befehls aufteilt, teilt die Parallelverarbeitung die gesamte Aufgabe oder das Programm in kleinere Teile auf, die unabhängig voneinander gleichzeitig verarbeitet werden können.

Vergleich: - Pipelining verbessert die Leistung, indem es die verschiedenen Stufen der Befehlsausführung überlappt. Es erhöht die Befehlsdurchsatzrate des Prozessors. - Parallelverarbeitung verbessert die Leistung, indem es die gesamte Arbeit auf mehrere Prozessoren verteilt, wodurch verschiedene Teile der Aufgabe gleichzeitig erledigt werden können.

Konkretes Beispiel:

Betrachten wir eine praktische Anwendung, z. B. das Rendern eines Bildes in einer Grafik-Software:

Pipelining im Rendering: Angenommen, das Rendern eines 3D-Bildes umfasst mehrere Schritte: 1. Objekterstellung, 2. Beleuchtung, 3. Texturierung, 4. Schattenberechnung. - In einem gepipelten System würde während die erste Stufe das nächste Objekt erstellt, die zweite Stufe bereits Beleuchtung für das vorherige Objekt berechnen. Währenddessen arbeitet die dritte Stufe an der Texturierung und die vierte Stufe berechnet die Schatten für Objekte, bei denen die Texturierung bereits abgeschlossen ist. - Dies ermöglicht eine kontinuierliche Auslastung der Hardware, da immer jede Stufe der Pipeline aktiv ist.

Parallelverarbeitung im Rendering: Angenommen, das Rendern eines Bildes kann in kleinere Segmente unterteilt werden, wobei jeder Prozessor an einem anderen Segment arbeitet. - Bei der Parallelverarbeitung könnte jeder Prozessor ein eigenes Segment des Bildes gleichzeitig rendern. Prozessor A rendert Segment 1, Prozessor B rendert Segment 2, usw. - Dies führt zu einer erheblich reduzierten Gesamtdauer des Renderprozesses, da jede Aufgabe parallel und unabhängig von den anderen bearbeitet wird.

Zusammenfassung: Sowohl Pipelining als auch Parallelverarbeitung sind entscheidende Technologien zur Leistungssteigerung in Computersystemen. Pipelining erhöht den Befehlsdurchsatz durch parallele Ausführungsstufen innerhalb eines Prozesses, während Parallelverarbeitung die Arbeitslast auf mehrere Prozessoren verteilt, um verschiedene Teile einer Aufgabe gleichzeitig zu bearbeiten. In der Praxis, wie im Beispiel des Bild-Renderings, tragen beide Ansätze dazu bei, die Effizienz und Geschwindigkeit der Verarbeitung erheblich zu steigern.

Aufgabe 2)

Symmetrische Multiprozessor-Architekturen (SMP):

SMP-Architekturen verwenden mehrere Prozessoren, die gleichberechtigt auf einen gemeinsamen Speicher zugreifen.

Gleiche Zugriffszeit auf gemeinsamen Speicher für alle Prozessoren
Kritische Abschnitte mit Locking-Mechanismen synchronisieren
Skalierbarkeit begrenzt durch Speicherbus
Beispielsweise in Servern und Workstations eingesetzt
Belästigungsfreiheit durch gleichwertige CPUs

b)

Erkläre die Bedeutung von Locking-Mechanismen in SMP-Architekturen. Implementiere eine einfache Synchronisationsaufgabe in pseudocode, bei der zwei Prozessoren auf denselben kritischen Abschnitt zugreifen. Diskutiere, wie der Einsatz von Locking-Mechanismen die Performance beeinflussen kann, insbesondere bei steigender Anzahl von Prozessoren.

Lösung:

Bedeutung von Locking-Mechanismen in SMP-Architekturen:

Vermeidung von Datenkorruption: Locking-Mechanismen werden verwendet, um sicherzustellen, dass nur ein Prozessor zur gleichen Zeit auf einen kritischen Abschnitt zugreift. Dies verhindert Datenkorruption und stellt die Konsistenz der Daten sicher.
Vermeidung von Race Conditions: Ohne Locking-Mechanismen könnten zwei oder mehr Prozessoren gleichzeitig auf den selben Speicherbereich zugreifen und unvorhersehbare Ergebnisse oder Race Conditions verursachen. Locking stellt sicher, dass kritische Abschnitte atomar ausgeführt werden.

Implementierung einer einfachen Synchronisationsaufgabe in Pseudocode:

Hier ist ein Beispiel in Pseudocode, bei dem zwei Prozessoren auf denselben kritischen Abschnitt zugreifen:

 mutex lock; // initialisierte Mutex-Lock void critical_section() {     lock_acquire(lock);    // Kritischer Abschnitt: nur ein Prozessor } // Wechselt Zeitgleich:// Simulation der Prozessor-Aktiongera 1. und auf mitte der LLIs hardware(variablen int shared_resource = 0; void processor_1() { lock_acquire(lock); shared_resource += 1; // kritischer Abschnitt lock_release(lock); }// Processor Return: 2. Startet: void processor_2() { lock_acquire(lock);shared_resource += 1 voide lock_release(lock);}

Diskussion über den Einfluss von Locking-Mechanismen auf die Performance:

Erhöhte Latenz: Locking-Mechanismen können zu Wartezeiten führen, bis ein Prozess in den kritischen Abschnitt eintreten kann. Dies erhöht die Latenz für den Zugriff auf gemeinsame Ressourcen.
Verringerte Parallelität: Während ein Prozessor den Lock hat, müssen andere wartende Prozessoren pausieren, was die Parallelität des Systems reduziert. Mit zunehmender Anzahl von Prozessoren kann dieses Problem noch verschärft werden.
Deadlocks: Bei unsachgemäßer Implementierung können Locking-Mechanismen zu Deadlocks führen, bei denen sich zwei oder mehr Prozessoren gegenseitig blockieren.
Skalierbarkeitsprobleme: Je mehr Prozessoren in einem SMP-System tätig sind, desto häufiger sind Zugriffe auf kritische Abschnitte und desto wahrscheinlicher wird der Speicherbus zum Flaschenhals, was zu Skalierbarkeitsproblemen führt.

Aufgabe 3)

Du sollst mithilfe von MPI ein einfaches paralleles Programm entwerfen, das die Summe aller Elemente eines Arrays berechnet. Verwende für die Umsetzung die Begriffe und Funktionen aus dem Lehrmaterial. Beginne das Programm indem Du alle Prozesse startest, die Daten verteilt und am Ende die Summe auf dem Root-Prozess sammelst. Beachte dabei, dass das Array gleichmäßig auf die Prozesse verteilt wird.

a)

Beschreibe das Konzept von Rank und Kommunikator in MPI. Erkläre dabei, wie diese Begriffe in Deinem Programm verwendet werden.

Lösung:

Um das Verständnis von Rank und Kommunikator in MPI zu erleichtern, ist es wichtig, das Konzept und die Verwendung dieser Begriffe in einem parallelen Programm zu erklären.

Rank: In MPI (Message Passing Interface) ist der Rank eine eindeutige Kennung eines Prozesses innerhalb eines bestimmten Kommunikators. Jeder Prozess in einem MPI-Programm hat eine eigene Rank-Nummer, die von 0 bis zur Gesamtzahl der Prozesse minus eins reicht. Der Rank wird verwendet, um die Prozesse zu identifizieren und ihnen spezifische Aufgaben zuzuweisen. Wenn ein Programm gestartet wird, erhält jeder Prozess einen Rank, den er nutzen kann, um zu wissen, welche Daten er verarbeiten soll und wie er mit anderen Prozessen kommunizieren kann. In Deinem parallelen Programm zur Berechnung der Summe eines Arrays wird der Rank dazu verwendet, die verschiedenen Teile des Arrays den einzelnen Prozessen zuzuweisen.
Kommunikator: Ein Kommunikator in MPI ist eine Gruppe von Prozessen, die miteinander kommunizieren können. Der standardmäßige Kommunikator in MPI ist MPI_COMM_WORLD, welcher alle Prozesse umfasst, die beim Start des MPI-Programms definiert wurden. Innerhalb dieses Kommunikators können Nachrichten zwischen Prozessen gesendet und empfangen werden. Der Kommunikator stellt dabei sicher, dass die Kommunikation nur zwischen den Prozessen innerhalb dieser Gruppe stattfindet. In Deinem Programm wird MPI_COMM_WORLD verwendet, um Daten zwischen allen gestarteten Prozessen zu verteilen und die Teilsummen am Ende wieder zusammenzuführen.

Zusammengefasst ermöglichen Rank und Kommunikator in MPI die Identifikation einzelner Prozesse und die Organisation der Kommunikation zwischen ihnen. In Deinem Programm wird der Rank verwendet, um jedem Prozess einen bestimmten Teil des Arrays zuzuweisen, während der Kommunikator sicherstellt, dass diese Prozesse effizient zusammenarbeiten, um die Gesamtsumme zu berechnen.

b)

Schreibe den Programmcode für die Initialisierung der MPI-Umgebung, die Verteilung des Arrays an die Prozesse und die Sammlung der Teilsummen auf dem Root-Prozess. Verwende dafür die Funktionen MPI_Init, MPI_Comm_rank, MPI_Comm_size, MPI_Scatter und MPI_Reduce. Achte darauf, dass der Code korrekt kommentiert ist.

Lösung:

Im Folgenden findest Du den Python-Code zur Initialisierung der MPI-Umgebung, Verteilung des Arrays an die Prozesse und Sammlung der Teilsummen auf dem Root-Prozess. Dieser Code verwendet die mpi4py-Bibliothek, um die MPI-Funktionen in Python zu implementieren.

from mpi4py import MPIimport numpy as np# Initialisiere die MPI-UmgebungMPI.Init()# Hole den Rank des aktuellen Prozesses und die Gesamtzahl der Prozessecomm = MPI.COMM_WORLDrank = comm.Get_rank()size = comm.Get_size()# Bestimme die Größe des Arrays und segmentiere esarray_size = 100segment_size = array_size // size# Initialisiere das Array und den Teiler-Arrayif rank == 0:    array = np.arange(array_size, dtype='i')  # Ein Beispiel-Array von 0 bis 99else:    array = None# Erstelle einen Empfangspuffer für die Teiler-Arrays auf jedem Prozesssegment = np.empty(segment_size, dtype='i')# Verteile das Array gleichmäßig auf alle Prozessecomm.Scatter(array, segment, root=0)# Jeder Prozess berechnet die Summe seiner Teiler-Arrayspartial_sum = np.sum(segment)# Sammle die Teilsummen und reduziere sie auf den Root-Prozessfinal_sum = comm.reduce(partial_sum, op=MPI.SUM, root=0)# Der Root-Prozess gibt die Gesamtsumme ausif rank == 0:    print(f'Die Summe aller Elemente im Array ist: {final_sum}')# Beende die MPI-UmgebungMPI.Finalize()

Kommentare zur Erklärung des Codes:
MPI.Init(): Hier wird die MPI-Umgebung initialisiert.
comm = MPI.COMM_WORLD: Holen des Kommunikators, der alle gestarteten Prozesse umfasst.
rank = comm.Get_rank(): Holen des Ranks des aktuellen Prozesses.
size = comm.Get_size(): Holen der Gesamtzahl der Prozesse.
array = np.arange(array_size, dtype='i'): Initialisieren eines Beispiel-Arrays von 0 bis 99 auf dem Root-Prozess.
comm.Scatter(array, segment, root=0): Verteilung des Arrays auf alle Prozesse.
partial_sum = np.sum(segment): Berechnen der Teilsumme jedes Teiler-Arrays durch die Prozesse.
comm.reduce(partial_sum, op=MPI.SUM, root=0): Sammeln und Reduzieren der Teilsummen auf dem Root-Prozess.
print(f'Die Summe aller Elemente im Array ist: {final_sum}'): Ausgabe der Gesamtsumme auf dem Root-Prozess.
MPI.Finalize(): Beenden der MPI-Umgebung.

c)

Analysiere die Skalierbarkeit Deines Programms. Berechne die theoretische Laufzeit deines parallelisierten Algorithmus im Vergleich zu einem rein sequentiellen Ansatz. Gehe dabei auf die Kommunikation und Synchronisation zwischen den Prozessen ein.

Lösung:

Um die Skalierbarkeit des parallelen Programms zu analysieren und die theoretische Laufzeit zu berechnen, müssen wir sowohl die parallele als auch die sequentielle Laufzeit berücksichtigen. Dabei spielen die Kommunikation und Synchronisation zwischen den Prozessen eine wesentliche Rolle.

Sequentielle Laufzeit: Die sequentielle Laufzeit ist einfach die Zeit, die benötigt wird, um alle Elemente des Arrays nacheinander zu summieren. Wenn wir annehmen, dass das Array eine Größe von N hat und es eine konstante Zeit T_{add} benötigt, um zwei Elemente zu addieren, ist die sequentielle Laufzeit: \[ T_{seq} = N \times T_{add} \]
Parallele Laufzeit: Die parallele Laufzeit besteht aus mehreren Teilen:
- Datenverteilung (Scatter): Die Zeit, die benötigt wird, um das Array gleichmäßig auf alle Prozesse zu verteilen. Wenn wir P Prozesse haben, wird die Größe jedes Segments N/P sein.
- Berechnung der Teilsummen: Jeder Prozess berechnet die Summe seines Teils des Arrays unabhängig von den anderen. Die Zeit, die dafür benötigt wird, beträgt: \[ T_{calc} = \frac{N}{P} \times T_{add} \]
- Kommunikation und Reduktion (Reduce): Danach müssen die Teilsummen aller Prozesse gesammelt und zu einer Gesamtsumme reduziert werden. Diese Zeit besteht aus der Kommunikation und Zusammenführung der Teilergebnisse. Die Kommunikationszeit kann als T_{comm} geschätzt werden, wobei diese Zeit abhängig von der Hardware und der Netzwerkverbindung ist.
Die Gesamtlaufzeit des parallelen Programms beträgt daher: \[ T_{par} = T_{scatter} + T_{calc} + T_{reduce} \]
Effizienz und Overhead: Die Effizienz der Parallelisierung hängt von der Kommunikation (Overhead) zwischen den Prozessen ab. Ideal wäre die Überprüfung des Speedups, der wie folgt definiert ist: \[ S(P) = \frac{T_{seq}}{T_{par}} \] wobei S(P) der Speedup bei P Prozessen ist. Eine weitere wichtige Kenngröße ist die Skalierbarkeitseffizienz, die wie folgt definiert ist: \[ E(P) = \frac{S(P)}{P} = \frac{T_{seq}}{P \times T_{par}} \]

So sind folgende Aspekte zu beachten:

Die Datenverteilung (Scatter) und das Sammeln und Reduzieren (Reduce) erfordern Synchronisation, was zusätzlichen Overhead erzeugt. Bei sehr großen Arrays und einer hohen Anzahl von Prozessen kann dieser Overhead signifikant werden und die Effizienz der Parallelisierung verringern.
Um den Overhead zu minimieren, ist eine ausgeglichene Lastverteilung wichtig, bei der jedes Segment des Arrays ungefähr gleich groß ist.

Zusammengefasst kann durch die Analyse der sequentiellen und parallelen Laufzeit die Effizienz des Parallelisierungsansatzes bestimmt werden. Dabei spielt die Kommunikation und Synchronisation zwischen den Prozessen eine entscheidende Rolle für die Skalierbarkeit des Programms.

Aufgabe 4)

Überlege Dir ein paralleles Programm, bei dem der parallelisierbare Anteil P geschätzt wird und wie sich die Anzahl der Prozessoren n auf die Leistung auswirkt. Du solltest sowohl das Amdahlsche Gesetz als auch das Gustafsons Gesetz verwenden, um die theoretische und praktische Skalierbarkeit zu bewerten. Dies wird Dir helfen, ein besseres Verständnis der Grenzen und Möglichkeiten der Parallelverarbeitung zu entwickeln.

a)

Teilaufgabe 1: Angenommen, ein paralleles Programm hat einen parallelisierbaren Anteil von P = 0,8 und Du möchtest wissen, wie sich die Ausführungszeit ändert, wenn die Anzahl der Prozessoren von n = 1 bis n = 16 variiert. Berechne den Beschleunigungsfaktor S(n) für jede Anzahl von Prozessoren unter der Annahme, dass der sequentielle Anteil 1 - P als Engpass bleibt. Benutze dafür das Amdahlsche Gesetz, um die Werte darzustellen und interpretiere die Ergebnisse.

Lösung:

Um den Beschleunigungsfaktor S(n) zu berechnen, verwenden wir das Amdahlsche Gesetz. Das Amdahlsche Gesetz lautet:

Amdahlsches Gesetz:

 S(n) = \frac{1} {(1 - P) + \frac{P} {n}}

Hier ist P der parallelisierbare Anteil des Programms und n die Anzahl der Prozessoren.

Setzen wir P = 0,8 und variieren n von 1 bis 16:

Für n = 1:

 S(1) = \frac{1} {(1 - 0,8) + \frac{0,8} {1}} = \frac{1} {0,2 + 0,8} = 1

Für n = 2:

 S(2) = \frac{1} {(1 - 0,8) + \frac{0,8} {2}} = \frac{1} {0,2 + 0,4} = 1,67

Für n = 3:

 S(3) = \frac{1} {(1 - 0,8) + \frac{0,8} {3}} = \frac{1} {0,2 + 0,27} = 2,13

Für n = 4:

 S(4) = \frac{1} {(1 - 0,8) + \frac{0,8} {4}} = \frac{1} {0,2 + 0,2} = 2,5

Für n = 5:

 S(5) = \frac{1} {(1 - 0,8) + \frac{0,8} {5}} = \frac{1} {0,2 + 0,16} = 2,86

Für n = 6:

 S(6) = \frac{1} {(1 - 0,8) + \frac{0,8} {6}} = \frac{1} {0,2 + 0,13} = 3,16

Für n = 7:

 S(7) = \frac{1} {(1 - 0,8) + \frac{0,8} {7}} = \frac{1} {0,2 + 0,11} = 3,45

Für n = 8:

 S(8) = \frac{1} {(1 - 0,8) + \frac{0,8} {8}} = \frac{1} {0,2 + 0,1} = 3,33

Für n = 9:

 S(9) = \frac{1} {(1 - 0,8) + \frac{0,8} {9}} = \frac{1} {0,2 + 0,09} = 3,57

Für n = 10:

 S(10) = \frac{1} {(1 - 0,8) + \frac{0,8} {10}} = \frac{1} {0,2 + 0,08} = 3,70

Für n = 11:

 S(11) = \frac{1} {(1 - 0,8) + \frac{0,8} {11}} = \frac{1} {0,2 + 0,07} = 3,85

Für n = 12:

 S(12) = \frac{1} {(1 - 0,8) + \frac{0,8} {12}} = \frac{1} {0,2 + 0,07} = 3,92

Für n = 13:

 S(13) = \frac{1} {(1 - 0,8) + \frac{0,8} {13}} = \frac{1} {0,2 + 0,06} = 4,00

Für n = 14:

 S(14) = \frac{1} {(1 - 0,8) + \frac{0,8} {14}} = \frac{1} {0,2 + 0,06} = 4,08

Für n = 15:

 S(15) = \frac{1} {(1 - 0,8) + \frac{0,8} {15}} = \frac{1} {0,2 + 0,05} = 4,17

Für n = 16:

 S(16) = \frac{1} {(1 - 0,8) + \frac{0,8} {16}} = \frac{1} {0,2 + 0,05} = 4,17

Interpretation der Ergebnisse:

Du siehst, dass der Beschleunigungsfaktor S(n) steigt, wenn die Anzahl der Prozessoren zunimmt. Allerdings steigt S(n) nicht linear mit der Anzahl der Prozessoren, sondern zeigt abnehmende Zuwächse. Dies liegt daran, dass der sequentielle Anteil von 20% die maximale Beschleunigung begrenzt. Für n = 8 und darüber hinaus stabilisieren sich die Werte zunehmend.

b)

Teilaufgabe 2: Betrachte dasselbe Programm mit einem parallelisierbaren Anteil von P = 0,8. Du möchtest jetzt untersuchen, wie sich die Problemlösung beim Einsatz von bis zu 16 Prozessoren verbessert, indem Du das Gustafsons Gesetz anwendest. Berechne den Beschleunigungsfaktor S(n) und diskutiere, wie sich die Effizienz der Parallelisierung mit zunehmender Anzahl von Prozessoren und vergrößerter Problemgröße verändert. Ziehe Vergleiche mit den Ergebnissen aus Teilaufgabe 1 und stelle dar, in welchem Fall die Parallelisierung vorteilhafter ist.

Lösung:

Um den Beschleunigungsfaktor S(n) nach Gustafsons Gesetz zu berechnen, verwenden wir die folgende Formel:

Gustafsons Gesetz:

 S(n) = n - (1 - P) * (n - 1)

Hier ist P der parallelisierbare Anteil des Programms und n die Anzahl der Prozessoren.

Setzen wir P = 0,8 und variieren n von 1 bis 16:

Für n = 1:
```
 S(1) = 1 - (1 - 0,8) * (1 - 1) = 1 
```

Für n = 2:

 S(2) = 2 - (1 - 0,8) * (2 - 1) = 2 - 0,2 = 1,8

Für n = 3:

 S(3) = 3 - (1 - 0,8) * (3 - 1) = 3 - 0,4 = 2,6

Für n = 4:

 S(4) = 4 - (1 - 0,8) * (4 - 1) = 4 - 0,6 = 3,4

Für n = 5:

 S(5) = 5 - (1 - 0,8) * (5 - 1) = 5 - 0,8 = 4,2

Für n = 6:

 S(6) = 6 - (1 - 0,8) * (6 - 1) = 6 - 1 = 5

Für n = 7:

 S(7) = 7 - (1 - 0,8) * (7 - 1) = 7 - 1,2 = 5,8

Für n = 8:

 S(8) = 8 - (1 - 0,8) * (8 - 1) = 8 - 1,4 = 6,6

Für n = 9:

 S(9) = 9 - (1 - 0,8) * (9 - 1) = 9 - 1,6 = 7,4

Für n = 10:

 S(10) = 10 - (1 - 0,8) * (10 - 1) = 10 - 1,8 = 8,2

Für n = 11:

 S(11) = 11 - (1 - 0,8) * (11 - 1) = 11 - 2 = 9

Für n = 12:

 S(12) = 12 - (1 - 0,8) * (12 - 1) = 12 - 2,2 = 9,8

Für n = 13:

 S(13) = 13 - (1 - 0,8) * (13 - 1) = 13 - 2,4 = 10,6

Für n = 14:

 S(14) = 14 - (1 - 0,8) * (14 - 1) = 14 - 2,6 = 11,4

Für n = 15:

 S(15) = 15 - (1 - 0,8) * (15 - 1) = 15 - 2,8 = 12,2

Für n = 16:

 S(16) = 16 - (1 - 0,8) * (16 - 1) = 16 - 3 = 13

Interpretation der Ergebnisse:

Nach Gustafsons Gesetz steigt der Beschleunigungsfaktor S(n) nahezu linear mit der Anzahl der Prozessoren. Dies liegt daran, dass Gustafsons Gesetz davon ausgeht, dass die Problemgröße mit steigender Anzahl der Prozessoren zunimmt, während der sequentielle Anteil konstant bleibt.
Vergleich mit den Ergebnissen aus Teilaufgabe 1 (Amdahlsches Gesetz): Das Amdahlsche Gesetz zeigt, dass es eine Obergrenze für den Beschleunigungsfaktor gibt, da der sequentielle Anteil einen Flaschenhals darstellt. Im Gegensatz dazu geht Gustafsons Gesetz davon aus, dass größere Probleme von mehr Prozessoren stark profitieren und somit der Beschleunigungsfaktor steigen kann, ohne durch den sequentiellen Anteil begrenzt zu werden.
Die Parallelisierung nach Gustafsons Gesetz ist vorteilhafter, wenn die Problemgröße mit der Anzahl der Prozessoren skaliert. Bei festen Problemgrößen ist jedoch das Amdahlsche Gesetz realistischer und zeigt die Grenzen der Parallelisierung auf.

Architekturen von Superrechnern - Exam.pdf

Architekturen von Superrechnern - Exam

Aufgabe 1)

a)

b)

c)

d)

Aufgabe 2)

b)

Aufgabe 3)

a)

b)

c)

Aufgabe 4)

a)

b)

Melde dich kostenlos an, um Zugriff auf das vollständige Dokument zu erhalten