Danksagung

Diese Arbeit wäre nicht gelungen ohne die Hilfe vieler Menschen in meiner Umgebung. Bei einigen möchte ich mich an dieser Stelle ganz besonders bedanken:

Ich danke meinen Eltern für die vielen verschiedenen Anregungen, die mich mit zu dem gemacht haben, was ich heute bin. Meiner Mutter ganz besonders dafür, dass sie durch alle Höhen und Tiefen eine beständige Quelle der Kraft war und immer zu mir gehalten hat, egal wofür ich mich entschieden habe. Meinem Vater verdanke ich nicht nur ein Studium ohne finanzielle Sorgen, seine kritisch-besorgte Begleitung war Ansporn und Herausforderung zugleich.

Meine Großmutter hat mir mit vielen langen Gesprächen liebevoll durch eine entscheidende persönliche Krise geholfen. Ihr verdanke ich wahrscheinlich, dass ich nicht aufgegeben habe.

Ich danke allen meinen Lehrern, die mein Interesse für die jeweilige Materie geweckt oder intensiviert haben, ganz besonders aber Bernhard Fischer, der mich nicht nur immer wieder motiviert hat, sondern auch der ideale Diplomarbeitsbetreuer war.

Ein ganz besonders herzlicher Dank gebührt Tini, der besten Freundin und Gefährtin in allen Lebenslagen. Ich hoffe, ich kann immer so für sie da sein wie sie für mich...

3

Kurzfassung

Seit jeher ist die Wissenschaft bemüht, komplexe, oft mathematische Probleme, denen Hypothesen und theoretische Beweise zu Grunde liegen, rechnerisch zu überprüfen, oder aus vorhandenen Datenbeständen neue Erkenntnisse abzuleiten. Die Erfindung von Computern brachte einen gewaltigen Sprung in der Entwicklung, derartige Berechnungen, die zuvor manuell ausgeführt wurden, durchführen zu können. Damit stieg allerdings auch die Kreativität und die Neugier in der Erforschung noch schwierigerer, aufwändigerer Probleme mit erhöhten Datenmengen und dahinter stehenden, komplexeren Algorithmen, die damit rasch an die Grenzen klassischer Computer mit sequentiellem Ausführungsverhalten stießen.

Es wurden verschiedene Konzepte zur parallelen Bearbeitung entwickelt, die auch schnell ihre Anwendung fanden, und es enstand der Überbegriff „Parallel Computing“ für die gleichzeitige Bearbeitung von Daten und/oder Aufgaben. Die Parallelität wird sowohl im Bereich der Hardware als auch der Software gleichermaßen verwirklicht, wobei es hierfür jeweils unterschiedliche Ansätze und Kombinationsmöglichkeiten gibt, worüber der Leser einen gesamtheitlichen Überblick erhält.

Die häufigsten Begriffe in diesem Zusammenhang sind Cluster und Supercomputer, aber auch Grids, ein Verbund heterogener, vernetzter Systeme, denen die Wissenschaft seit einigen Jahren erhöhte Aufmerksamkeit schenkt. Es wird ein Überblick über diese Architekturen vor einem theoretischen Hintergrund gegeben.

Aus dem Bereich der Software werden Methoden zur parallelen Programmierung in Form einiger weit verbreiteter Modelle, wie MPI und Pthreads dargestellt sowie verschiedene einfache Anwendungsbeispiele gebracht.

4

Abstract

All times science strove to mathematically verify complex problems, based on hypotheses and abstract proof, or to deduct new conclusions from existing data. Invention of computers was a milestone in that regard - before, such calculations had to be done manually. But hand in hand with the enhancement of possibilities came a raise in creativity and curiosity. Exploration of more complicated, more elaborate problems with ever more data, based on more complex algorithms quickly showed the limits of the classical computers with sequential instruction execution behaviour.

Various concepts for parallel processing were developed and quickly applied. The umbrella term „parellel computing“ arose, meaning a simultanous processing of data and/or tasks. The parallelism is realised in the hardware sector as well as in the software sector, using different approaches and methods of combination. A collective overview of these will be given.

The most commonly used terms in this regard are clusters and supercomputers, but also grids, networks of heterogenous, interconnected systems, which have been getting more and more scientists’ attention during the last years. An overview of these architectures against a theoretical background will also be given.

Regarding software a few popular models of methods of parallel programming, e.g. MPI and Pthreads will be presented, as well as some simple examples of application.

5

Inhaltsverzeichnis

1.  Einleitung  8

1.1.  Motivation  8

1.2.  Erkenntnisgegenstand  8

1.3.  Problemstellung  9

1.4.  Geschichte und Ziele von Parallel Computing  10

2.  Klassifizierung  12

2.1.  Flynnsche Klassifikation  12

2.1.1.  SISD - Single Instruction, Single Data  13

2.1.2.  MISD - Multiple Instruction, Single Data  13

2.1.3.  SIMD - Single Instruction, Multiple Data  14

2.1.4.  MIMD - Multiple Instruction, Multiple Data  15

2.1.5.  Weitere Klassen  15

2.2.  Speicherverwaltung  16

2.2.1.  Shared Memory  16

2.2.2.  Distributed Memory  18

2.2.3.  Hybrid Distributed-Shared Memory  23

3.  Cluster und Grids  24

3.1.  Cluster  24

3.1.1.  Architektur und interne Strukturen  25

3.1.2.  Kategorisierung nach Anwendungszweck  28

3.1.3.  Clustersoftware  29

3.2.  Grids  30

3.2.1.  Architektur und Arbeitsweise  31

3.2.2.  Kategorisierung  34

6

Inhaltsverzeichnis

4.  Supercomputer  36

4.1.  Entwicklung  36

4.2.  Aufbau  37

4.3.  Einsatzbereiche  39

4.4.  TOP500  39

5.  Programmiermodelle  44

5.1.  Shared Memory  44

5.1.1.  Locks  45

5.1.2.  Semaphore  46

5.2.  Threads und gemeinsame Variablen  47

5.2.1.  POSIX Threads  49

5.2.2.  OpenMP  51

5.3.  Message Passing  53

5.3.1.  MPI  54

5.3.2.  MPI-2  57

5.3.3.  PVM  58

6.  Zusammenfassung  60

A.  Parallelisierter Sortieralgorithmus  62

B.  Abkürzungsverzeichnis  68

C.  Literaturverzeichnis  70

D.  Abbildungsverzeichnis  74

7

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.

8

Kapitel 1. Einleitung

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 Hard- und 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

9

Kapitel 1. Einleitung

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 Soft- und 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-

10

Kapitel 1. Einleitung

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.

11

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:

12

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.

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.

13

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).

Kapitel 2. Klassifizierung

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.

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.

15

Kapitel 2. Klassifizierung

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 Multiprozes-sorsysteme 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 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 Lese- und Schreibzugriff besitzen. Änderungen, die von einer CPU im Speicher

16