Parallel Computing - Systemarchitekturen und Methoden der Programmierung

Inhaltsverzeichnis

1. Einleitung
1.1. Motivation
1.2. Erkenntnisgegenstand
1.3. Problemstellung
1.4. Geschichte und Ziele von Parallel Computing

2. Klassifizierung
2.1. Flynnsche Klassifikation
2.1.1. SISD – Single Instruction, Single Data
2.1.2. MISD – Multiple Instruction, Single Data
2.1.3. SIMD – Single Instruction, Multiple Data
2.1.4. MIMD – Multiple Instruction, Multiple Data
2.1.5. Weitere Klassen
2.2. Speicherverwaltung
2.2.1. Shared Memory
2.2.2. Distributed Memory
2.2.3. Hybrid Distributed-Shared Memory

3. Cluster und Grids
3.1. Cluster
3.1.1. Architektur und interne Strukturen
3.1.2. Kategorisierung nach Anwendungszweck
3.1.3. Clustersoftware
3.2. Grids
3.2.1. Architektur und Arbeitsweise
3.2.2. Kategorisierung

4. Supercomputer
4.1. Entwicklung
4.2. Aufbau
4.3. Einsatzbereiche
4.4. TOP500

5. Programmiermodelle
5.1. Shared Memory
5.1.1. Locks
5.1.2. Semaphore
5.2. Threads und gemeinsame Variablen
5.2.1. POSIX Threads
5.2.2. OpenMP
5.3. Message Passing
5.3.1. MPI
5.3.2. MPI-2
5.3.3. PVM

6. Zusammenfassung
A. Parallelisierter Sortieralgorithmus
B. Abkürzungsverzeichnis
C. Literaturverzeichnis
D. Abbildungsverzeichnis

Kapitel 1. Einleitung

1.1. Motivation

Im Rahmen meines Berufspraktikums kam ich das erste mal mit Clustern und Grids in Kontakt und fand so schnell Zugang zur allgemeinen Thematik des „Parallel Computings“. Dabei fiel mir auf, dass es zwar Unmengen an Informationen zu speziellen Teilbereichen der Materie gibt, aber so gut wie keine ausführliche Zusammenfassung über die Gesamtheit der Möglichkeiten und Architekturen, was den Gewinn eines allgemeinen Überblicks relativ umständlich gestaltet.

Dies hat mich dazu bewogen, genau eine solche Zusammenfassung zu erstellen – sowohl für mich selbst als vielleicht auch für andere, die ein allgemeines Interesse an diesem Gebiet besitzen.

1.2. Erkenntnisgegenstand

In vielen Bereichen des Lebens stellen wachsende Datenmengen die Technik vor immer neue Herausforderungen hinsichtlich der Verarbeitungsgeschwindigkeit und der Datendurchsatzrate. Die in Forschung, Wirtschaft, Finanzwesen, Industrie, Handel oder anderen Gebieten gesammelten Informationen sollen nicht nur gespeichert, sondern auch verarbeitet und ausgewertet werden, um neue Erkenntnise daraus zu gewinnen. Je größer dabei die Menge der zu verarbeitenden Daten wird, desto mehr gewinnen Lösungen zur Performancesteigerung an Bedeutung.

Der naheliegende Ansatz, die Daten auf sinnvolle Art in kleinere, schneller zu verarbeitende Stücke aufzuteilen, um sie getrennt voneinander bearbeiten zu können und die Teilergebnisse erst im Anschluss daran wieder zusammenzusetzen, ist sowohl im Softwareals auch im Hardwarebereich auf verschiedenen Wegen verwirklicht worden. Es ist offensichtlich, dass die Vorteile dieser Methode vor allem dann maximiert werden, wenn die einzelnen Teile gleichzeitig statt nacheinander verarbeitet werden – es kommt zum Einsatz von „Parallel Computing“.

Verwirklicht wird Parallel Computing über unterschiedliche Technologien und Algorithmen. Diese reichen von der logischen Aufteilung einzelner Rechenprozesse (Multithreading) über die Verwendung mehrerer Prozessoren (Multiprocessing) bis hin zur Parallelisierung vieler zusammenarbeitender Gesamtsysteme (Grids und Cluster). Ganz grundlegend lässt sich ein Parallelrechner folgendermaßen definieren: „Ein Parallelrechner ist eine Ansammlung von Berechnungseinheiten (Prozessoren), die durch koordinierte Zusammenarbeit große Probleme schnell lösen können.“ [2]

Entscheidend ist aber nicht nur die koordinierte Zusammenarbeit der Berechnungseinheiten, sondern auch die der Teilbereiche Hardund Software. Ein paralleler Algorithmus auf einer linearen Architektur ist genauso sinnlos wie die Ausführung eines linearen Programmes auf einem parallelen System. Beides ist zwar möglich, führt aber trotzdem nur zur herkömmlichen, sequenziellen Bearbeitung. Eine anschauliche Analogie hierfür kann über den Hörfunk hergestellt werden: Ein Mono-Empfänger gibt auch eine Stereo- Sendung immer nur mono wieder, genauso wie eine Mono-Sendung auf einem Stereo- Gerät immer mono gespielt wird.

1.3. Problemstellung

Welche Lösungen von Parallel Computing bei der Datenanlyse zum Einsatz kommen, hängt meist von der genauen Art der Anwendung und den damit verbundenen Anforderungen ab. Entscheidende Unterschiede ergeben sich hierbei beispielsweise im Bedarf an CPU-Rechenzeit, Hauptspeicher oder Festplattenspeicher.

Häufig befinden sich die zu verarbeiteten Daten auch nicht auf einem System, sondern sind an sich bereits auf unterschiedliche Orte verteilt: mehrere Rechner an einer Position oder überhaupt verschiedene Standorte. In diesem Fall ergeben sich weitere zu beachtende Komponenten durch den Bedarf an Übertragungsgeschwindigkeit, Verfügbarkeit und Auslastung des Netzwerks.

Darüber hinaus erfordert jedes Computersystem ganz eigene Methoden der Programmierung. Dies trifft somit auch auf parallele Architekturen zu.

Daraus ergeben sich folgende Fragestellungen:

- Welche Parallel Computing Architekturen gibt es? Wie kann man diese über die Unterscheidung nach Softund Hardwarelösung hinaus kategorisieren?
- Welche Konzepte stehen dahinter und wie funktionieren sie? Wo liegen die Unterschiede, wo ergeben sich Überschneidungen und Gemeinsamkeiten?
- Wie sind parallele Architekturen in der Softwareentwicklung zu berücksichtigen? Welche Möglichkeiten der Programmierung paralleler Systeme gibt es?

1.4. Geschichte und Ziele von Parallel Computing

Ursprünglich wurden Computer für die Verarbeitung serieller Aufgaben auf einer einzelnen Maschine entwickelt. Dabei werden Anweisungen sequenziell von der vorhandenen CPU abgearbeitet, was bedeutet, dass zu jeder Zeit immer nur genau eine Anweisung bearbeitet werden kann. Sobald jedoch auf diesem Weg größere Datenmengen verwertet oder mehrere unterschiedliche Probleme bearbeitet werden sollen, werden rasch Grenzen ersichtlich, was die Lösung der Aufgabe in einer vertretbaren Zeit betrifft. Zum Einen braucht die Bearbeitung eines einzelnden Prozesses zu lang, zum Anderen müssen alle anderen Prozesse auf die Fertigstellung des vorigen warten.

Parallel Computing verfolgt also vor allem folgende eng zusammenhängende Hauptziele: Die Rechenzeit für ein einzelnes Programm soll verringert, und in Folge dessen sollen mehr Aufgaben in der gleichen Zeit bearbeitet werden. Dadurch soll die Bearbeitung grö- ßerer Datenmengen und komplizierterer Probleme erleichtert oder überhaupt erst möglich gemacht werden.

Bei einigen Parallel Computing Systemen ergeben sich noch zusätzliche Möglichkeiten, wie beispielsweise der Zugriff auf Resourcen, die nicht direkt lokal vorhanden sind. Dabei kann es sich schlicht um Datenbestände handeln, aber auch um zusätzliche Rechen- leistung oder Speicher, auf den über größere Entfernungen zugegriffen wird. Und nicht zuletzt spielt auch der Kostenfaktor noch eine Rolle: parallele Systeme wie Cluster sind im Normalfall günstiger zu realisieren als ein einzelner Supercomputer der selben Leistung.

Doch nicht jede Problemstellung eignet sich für die parallele Ausführung. Es muss von Haus aus die Möglichkeit bestehen, eine Gesamtaufgabe in Teilaufgaben, also ein Programm in mehrere Berechnungsströme zu unterteilen, die dann mehr oder weniger unabhängig voneinander gleichzeitig ausgeführt werden können. Je geringer die Abhängigkeit der Teile voneinander ist, desto naheliegender ist der Einsatz von parallelen Lösungen. Zwar besteht die Möglichkeit der Synchronisierung voneinander abhängiger Prozesse, doch kostet dies wieder Zeit in Form von Wartezeiten oder zusätzlichen Datenübertragungen. Würde dieser Zeitverlust den Zeitgewinn durch den Einsatz eines parallelen Systems übersteigen, wären die Vorteile hinfällig. Es gilt also, den richtigen Mittelweg zu finden.

Kapitel 2. Klassifizierung

Parallele Architekturen lassen sich auf unterschiedliche Arten klassifizieren. Eine sehr grundlegende Einteilung von Computersystemen allgemein stellt „Flynn’s Taxonomy“ dar. Diese behandelt nicht allein parallele Systeme, beinhaltet diese aber, was verdeutlicht, dass Parallelisierung bereits vor über 40 Jahren ein Thema war. Eine mögliche Kategorisierung von ausschließlich parallelen Systemen kann nach der Art der Speicherverwaltung getroffen werden.

Unabhängig davon, welche Klassifizierung herangezogen wird, ist jedoch zu erwähnen, dass die Übergänge zwischen den Kategorien oft fließend sind. Viele Lösungen sind also durchaus in unterschiedlichen Bereichen einzuordnen.

2.1. Flynnsche Klassifikation

Eine der wohl ältesten, aber dennoch bis heute gängigen Einteilungen von Rechnerarchitekturen geht auf Michael J. Flynn zurück, der im Jahr 1966 „Flynn’s Taxonomy“ [16] veröffentlichte. Die Unterteilung findet dabei nach zwei unabhängigen Parametern statt: die Anzahl der Befehlsströme („Instruction“) und der Datenströme („Data“).

Für beide Kategorien gibt es jeweils die beiden möglichen Zustände „Single“ oder „Multiple“. Daraus ergeben sich folgende vier Klassen:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.1.: Flynnsche Klassifikation [9]

2.1.1. SISD – Single Instruction, Single Data

Hierbei handelt es sich um die herkömmliche serielle Datenverarbeitung, die bei traditionellen Einprozessor-Rechnern zum Einsatz kommt. SISD Systeme fallen also nicht in die Kategorie der Parallelrechner. Variablen für die Berechnung werden nacheinander geladen und verschiedene Berechnungen hintereinander durchgeführt. Abbildung 2.1 zeigt einen solchen sequenziellen Ablauf. A, B und C sind Variablen und bilden den Datensatz, jeder Kasten ist eine auszuführende Anweisung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1.: SISD – Single Instruction, Single Data [29]

2.1.2. MISD – Multiple Instruction, Single Data

MISD Systeme führen gleichzeitig unterschiedliche Berechnungen mit den gleichen Ausgangsdaten durch. Sie kommen in der Praxis jedoch selten zum Einsatz, da unterschiedliche Verarbeitungsanweisungen im Normalfall auch mit verschiedenen Dateninputs arbeiten. Ein denkbares Einsatzgebiet für die gleichzeitige Analyse eines Datensatzes auf mehrere Arten wäre beispielsweise das Untersuchen einer verschlüsselten Nachricht mit verschiedenen kryptographischen Algorithmen. [29]

In Abbildung 2.2 ist die Variable A(1) der zu analysierende Datensatz, der nach eventuell vorangegangenen Anweisungen („prev instruct“) parallel die unterschiedlichen Berechnungen durchläuft und in C(1) bis C(n) gespeichert wird. Anschließend können weitere Befehle („next instruct“) folgen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2.: MISD – Multiple Instruction, Single Data [29]

2.1.3. SIMD – Single Instruction, Multiple Data

Bei SIMD Systemen wird die gleiche Operation gleichzeitig auf unterschiedliche Dateninputs angewandt. Dies kommt bei sogenannten Vektorrechnern zum Einsatz, die genau nach diesem Prinzip arbeiten.

Unterschiedliche Dateninputs A(1) bis A(n) und B(1) bis B(n) werden gleichzeitig geladen und durchlaufen parallel die gleiche Berechnung, die zu den jeweiligen Ergebnissen C(1) bis C(n) führt (s. Abb. 2.3).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3.: SIMD – Single Instruction, Multiple Data [29]

2.1.4. MIMD – Multiple Instruction, Multiple Data

Hier kommen schließlich die vollen Möglichkeiten der Parallelität zum Einsatz. Mehrere Prozessoren bearbeiten gleichzeitig verschiedene Datenströme mit unterschiedlichen Operationen. Es können also diverse vollkommen unabhängige Berechnungen parallel durchgeführt werden. Dies trifft auf jegliche Form verteilter Systeme zu.

In Abbildung 2.4 sind exemplarisch drei voneinander vollkommen unabhängige Berechnungsabläufe ersichtlich. Die Arbeitsweise der Funktionen ist dabei an dieser Stelle zu vernachlässigen, da hiermit nur verdeutlicht werden soll, dass diese in keinster Weise mehr irgend welche Gemeinsamkeiten besitzen müssen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4.: MIMD – Multiple Instruction, Multiple Data [29]

2.1.5. Weitere Klassen

In der Literatur werden von diesen vier Kategorien häufig überhaupt nur SIMD und MIMD Systeme als Parallelrechner genannt. Dafür hat sich in diesen beiden Kategorien noch jeweils eine zusätzliche Erweiterung zu Flynns Klassifizierung entwickelt: SPMD („Single Program, Multiple Data“ oder auch „Single Process, Multiple Data“) und MPMD („Multiple Program, Multiple Data“) [43].

SPMD kann generell auch als SIMD bezeichnet werden, unterscheidet sich aber dadurch, dass zwar von den verschiedenen Prozessoren das gleiche Programm ausgeführt wird, aber unabhängig voneinander an verschiedenen Punkten, also nicht synchronisiert.

MPMD unterscheidet sich nicht wirklich von MIMD und dürfte vor allem zur Anpassung an die neu hinzugefügte Kategorie SPMD eingeführt worden sein.

2.2. Speicherverwaltung

Heutzutage sind hauptsächlich noch MIMD Systeme im Einsatz. Diese können nach der Art der Speicherverwaltung weiter unterschieden werden. Der Speicher kann entweder physikalisch zentral gemeinsam genutzt werden („Shared Memory“) oder dezentral verteilt („Distributed Memory“). Shared Memory Systeme werden auch als Multiprozessorsysteme bezeichnet, Distributed Memory Systeme als Multicomputersysteme. Eine Mischform beider Systeme ist möglich. Abbildung 2.5 bietet einen Überblick über die Unterteilung von MIMD-Rechnern nach ihrer Speicherorganisation.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5.: Unterteilung von MIMD-Rechnern nach Speicherorganisation, vgl. [40]

Aus Sicht eines Programmierers kann auch noch zwischen Rechnern mit verteiltem Adressraum und solchen mit gemeinsamem Adressraum unterschieden werden, was jedoch nicht mit der physikalischen Beschaffenheit übereinstimmen muss. [40]

2.2.1. Shared Memory

Beim Shared Memory Modell, auch kurz als SMM („Shared Memory Machine“) bezeichnet, teilen sich mehrere CPUs physikalisch einen gemeinsamen globalen Speicherbereich. Dieser ist meist aus einzelnen Speichermodulen zusammengesetzt. Die CPUs können unabhängig voneinander agieren, teilen sich aber den gleichen Adressraum, in dem alle Leseund Schreibzugriff besitzen. Änderungen, die von einer CPU im Speicher vorgenommen werden, sind also auch für alle anderen sofort sichtbar. Eine vereinfachte Darstellung einer SMM ist in Abbildung 2.6 zu sehen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.6.: Shared Memory Modell [29]

Die Vorteile eines Rechnermodells mit gemeinsamem Speicher gegenüber einer verteilten Speicherlösung liegen vor allem in der einfacheren Programmierung, wobei der Programmierer jedoch darauf achten muss, keine durch gleichzeitigen Zugriff enstehenden Schreibkonflikte im Speicher zu verursachen. Des Weiteren ist eine sehr effiziente Speicherausnutzung möglich, da ein Replizieren von Daten nicht nötig ist. Einen Nachteil hingegen stellt die geringe Möglichkeit der Skalierbarkeit dar. Ab einem gewissen Level gerät die Übertragungskapazität des Verbindungsnetzwerkes zwischen CPUs und Speicher an ihre Grenzen, weswegen Shared Memory Rechner meist mit nur wenigen Prozessoren arbeiten. [40, 29]

Eine spezielle und äußerst gängige Variante der SMMs sind symmetrische Multiprozessoren, kurz SMP („Symmetric Multiprocessor“) [6]. Die Architektur entspricht dem bereits kurz beschriebenen Aufbau von SMMs: mehrere (wenige) Prozessoren sind über einen zentralen Bus miteinander verbunden und haben über diesen Zugriff auf den gemeinsamen Speicher und angeschlossene I/O-Geräte. Die Bezeichnung „symmetrisch“ kommt daher, dass alle Prozessoren genau die gleiche Funktionalität und die gleiche Perspektive des Gesamtrechners besitzen, was eine einheitliche Zugriffszeit auf den Speicher unabhängig von der genauen Speicheradresse ermöglicht. Die bereits erwähnte Limitierung der Übertragungskapazität kommt auch hier zum Tragen, wodurch die maximale Anzahl an Prozessoren bei busbasierten SMP-Rechnern im Normalfall bei 32 oder 64 liegt. [40]

Es besteht die Möglichkeit, mehrere SMP-Rechner zu größeren Systemen zusammen zu hängen, wodurch ein Hybrid Modell aus Distributed und Shared Memory ergibt (s. Abschnitt 2.2.3), welches aber häufig noch als Teil der Kategorie der Shared Memory Systeme genannt wird. Mögliche unterschiedliche Zugriffszeiten führen hier zu einer weiteren Unterkategorisierung in UMA („Uniform Memory Access“) und NUMA („Non-Uniform Memory Access“) Maschinen. UMA-Systemen haben die gleiche Zugriffszeit für alle Speicherzugriffe, wie beispielsweise bei SMPs. Bei NUMA-Systemen hingegen hängt die Zugriffszeit von der Entfernung des zugreifenden Prozessors zu dem angesprochenen Speicherteil ab. Ein Verbund von mehreren SMPs fällt also in diese Kategorie.

2.2.2. Distributed Memory

Bei Distributed Memory Systemen, auch als DMM („Distributed Memory Machine“) bezeichnet, besitzt jeder Prozessor seinen eigenen lokalen Speicher, was dazu führt, dass es keinen globalen Adressraum gibt und die Prozessoren unabhängig voneinander agieren. Auch hier gibt es aber wieder ein Verbindungsnetzwerk zwischen den einzelnen Komponenten. Abbildung 2.7 zeigt die vereinfachte Darstellung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.7.: Distributed Memory Modell [29]

Änderungen, die von einer CPU in ihrem Speicher vorgenommen werden, haben keine direkte Auswirkung auf die Anderen Prozessoren und deren Speicher. Das Ermöglichen des Zugriffs von einem Prozessor auf den Speicher eines anderen ist daher Aufgabe des Programmierers und greift auf das Programmiermodell der Nachrichtenübertragung oder auch „Message-passing programming model“ (s. Kap. 5) zurück [40].

Die Arbeitsweise von DMM Systemen hängt stark von der Art des verwendeten Verbindungsnetzwerkes ab. Bei einem kleinen System bietet es sich noch an, jeden Computer mit jedem anderen zu verbinden. Bei größeren Systemen gerät man hierbei jedoch rasch an die Grenzen dessen, was sinnvoll ist, da für x Computer x (x − 1)/2 Verbindungen benötigt werden. Hier kommen nun Netzwerke mit begrenzten Verbindungen zum Einsatz, wobei es hier vor allem zwei relevante Typen gibt: „Mesh“ und „Hypercube“ Netzwerke. [43]

Mesh Netzwerk

Ein zweidimensionales Mesh wird gebildet, indem jeder Knoten mit seinen vier direkten Nachbarn verbunden wird (s. Abb. 2.8). Die freien Enden können wieder miteinander verbunden werden, so dass sich eine Art Ring bildet. Bei einem dreidimensionalen Mesh wird jeder Knoten mit seinen jeweils zwei direkten Nachbarn in der x-, yund z-Ebene verbunden. Der Vorteil dieser Netzwerkart liegt im einfachen Design und der einfachen Erweiterbarkeit. [43]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.8.: Zweidimensionales Mesh-Netzwerk (vgl. [43])

Hypercube Netzwerk

Bei einem Hypercube wird jeder Knoten über eine binäre Adresse angesprochen, die jeweils eine Länge von so vielen Bit hat, wie das Netzwerk Dimensionen. Veranschaulicht wird dies in den Abbildungen 2.9 und 2.10. Jeder Knoten ist mit jeweils einem anderen Knoten in jeder Dimension des Netzwerkes verbunden. Bei der einfachsten Form, einem dreidimensionalen Hypercube, wird also genau ein Würfel gebildet. Jedes Bit der Adresse steht für eine der Dimensionen. Beim dreidimensionalen Hypercube wird also der Knoten mit der Adresse 000 mit den Adressen 001, 010 und 100 verbunden, Knoten 111 grenzt an 110, 101 und 011, u.s.w. Auch bei höherdimensionalen Netzwerken lassen sich die Verbindungen leicht eruieren, da die verbundenen Adressen sich immer um genau ein Bit unterscheiden. Beispielsweise der Knoten 11101 eines fünfdimensionalen Hypercubes grenzt an die Knoten 11100, 11111, 11001, 10101 und 01101. [43]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.9.: Dreidimensionaler Hypercube (vgl. [43])

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.10.: Vierdimensionaler Hypercube (vgl. [43])

Die Schwierigkeit bei den hier beschriebenen Punkt-zu-Punkt-Verbindungen ist jedoch, dass einzelne Knoten immer nur ihren direkten Nachbarn addressieren und mit diesem kommunizieren können und dadurch die Kommunikation stark durch die Gestalt des

Netzwerkes bestimmt ist. Verbindungen zu weiter entfernten Knoten muss über Software gesteuert werden, was zu einer erheblichen Erhöhung der Laufzeit führt. Weiters muss die Kommunikation gleichzeitig aus beiden Richtungen stattfinden. Wenn ein Knoten auf einem Link sendet, muss sein Nachbar in dem Moment auch auf diesem Link empfangen. Üblicherweise sind zwar Puffer vorhanden, in denen die Nachricht zwischengespeichert werden kann, doch sind diese in ihrer Kapazität begrenzt.

Durch Einsatz eines sogenannten DMA-Controllers (DMA für „Direct Memory Access“) kann zumindest das Problem des gleichzeitigen Sendens und Empfangens behoben werden. Dieser Controller macht die eigentliche Kommunikation vom Prozessor unabhängig, indem er die Möglichkeit des direkten Datentransfers zwischen lokalem Speicher und I/O-Anschluss herstellt. Nach Absetzen des Sendebefehls kann sich der Prozessor sofort wieder anderen Berechnungen widmen. Auf der Empfängerseite nimmt ebenfalls der DMA-Controller die Nachricht entgegen und legt sie in einen extra dafür vorgesehenen Speicherbereich ab, bis sie vom dortigen Prozessor bearbeitet werden kann. Um auch die gegenseitige Erreichbarkeit aller Knoten zu vereinfachen und beschleunigen, wurden modernen Multicomputern bei jedem Knoten ein eigener Hardware-Router oder -Switch hinzugefügt. Die Netzwerkkommunikation selbst muss dann nur noch über diese Router erfolgen und nicht mehr über die CPU der Knoten. Die Kommunikationszeiten zwischen weiter entfernten Rechnern können auf diesem Weg nahezu auf die von direkten Nachbarn verringert werden. [40]

Baum Netzwerk

Bei einem binären Baum als Netzwerkstruktur (s. Abb. 2.11) fungiert jeder Knoten als Switch, der jeweils mit zwei Switches in der nächsten Ebene verbunden ist. Die „Höhe“ des Baums ergibt sich durch die Anzahl der Links von der Wurzel („Root“) bis zu einem Knoten der untersten Ebene. Der große Nachteil eines Netzwerkbaumes ist jedoch, dass der Datenverkehr zur Wurzel hin ansteigt und dadurch hier ein Engpass entstehen kann.[43]

Multistage Interconnection Netzwerk

Unter dem Begriff „Multistage Interconnection Netzwerk“, kurz MIN, werden schließlich unterschiedlichste Strukturen zusammengefasst, die eine bestimmte Anzahl an Ebenen

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.11.: Netzwerkstruktur mit binärem Baum (vgl. [43]) mit Switches besitzen. Switches einer Stufe sind dabei auf verschiedene symmetrische Weisen mit denen der nächsten Stufe verbunden, so dass sich diverse Wege von einer Seite des Netzwerkes zur anderen ergeben. Ein Beispiel hierfür ist das in Abbildung 2.12 dargestellte Omega Netzwerk. Hier werden die Switches über die Zieladresse gesteuert: Die jeweilige Stelle der Adresse kontrolliert die ihr zugehörige Stufe an Switches, wobei bei einer 0 der obere und bei einer 1 der untere Ausgang gewählt wird. [43]

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.12.: Omega Netzwerk (vgl. [43])

In seinem Aufbau ähnelt ein Rechner mit verteiltem Speicher stark sogenannten Clustern, bei denen eigenständige Computer über ein LAN („Local Area Network“) miteinander verbunden sind. Eine Nähere Beschreibung findet sich in Kapitel 3. Der Entscheidende Unterschied ist jedoch, dass das Verbindungsnetzwerk eines einzelnen Parallelrechners im Vergleich zu dem eines Clusters eine höhere Übertragungskapazität besitzt.

[...]