Parallelrechner


In die Vorlesung Parallelrechner bin ich mit der Vorstellung reingegangen, meine Programme auf einem Cluster aus Linux-Rechnern beschleunigt starten zu können.

1. Vorwort


Die Illusion hat uns Prof. Nowak gleich genommen. Es gebe kein Compiler-Flag oder ein System, so dass wir unsere Programme beschleunigt in einem Cluster oder Multiprozessor-Rechner laufen lassen können. Eine Ausnahme bietet hier das unten beschriebene MATLAB-Implicit-Multiprocessing. Generell, und vor allem dann, wenn es um rechnerische Höchstleistungen geht, müssen Programme mit einer ordentlichen Portion Sorgfalt und viel Kenntnis von dem verwendeten Standard (z.B. MPI oder OpenMP) und seiner Eigenarten umgeschrieben werden.

Der Standard der sich in der Klasse der des High-End-Parallelrechnens durchgesetzt hat, ist die Parallelrechner-Bibliothek MPI. Es wird in der Programmiersprache C programmiert und es wird das Betriebssystem OsLinux oder allgemein etwas Unix-basierendes verwendet. Mehrere Rechner sind über ein schnelles Netzwerk verbunden.


2. Parallelrechentechnologien im Überblick


MPI ist nicht automatisch das beste! Nicht immer müssen es mehrere Rechner sein. Mehrere CPUs sind Standard. GPUs und FPGA-Karten erobern den Markt. SSE gibt es schon länger. Und am schönsten macht es, meiner meinung nach, Mathworks mit dem MATLAB-Implicit-Multiprocessing. Nachfolgend ein kurzer Überblick der Technologien.

Threads sind nichts ungewöhnliches. Neben dem eigentlichen Gedanke ganze Programme in kleinen Scheibchen auf einen Prozessor laufen zu lassen, spielen Threads freilich eine neue Rolle seit dem die Mulitiprozessor-Rechner mit speichergekoppelten Architekturen auf dem Markt sind. Mehrere CPUs in einem System sind zwar gut, aber ein altes Programm läuft i.d.R. auf einer CPU. Klar läuft nicht nur ein Programm auf einem PC, aber was tun, wenn ein bestimmtes Programm möglichst die volle Rechenleistung ausschöpfen soll. Können die rechenintensiven Programmteile auf Threads aufgeteilt werden, so können diese jeweils einer CPU zugeordnet werden. Und schon wird die Last verteilt. Das ist der Anfang, aber selten ist das optimal. Viel besser und effizient in Hinblick auf die Entiwcklungszeit geht das mit OpenMP. Aber nur bei speichergekoppelten Rechnern (Multiprozessor-Rechner) - auf Clustern (über Netzwerk gekoppelt) nicht möglich.

SIMD vergessen? Wenn es um Leistungssteigerung geht, sollte das nicht unerwähnt bleiben. Ganz am Rande habe ich festgestellt, dass sich die Welt im Rahmen der Beschleunigung von rechenintensiven Programmen viel Gedanken um das Rechnen auf mehreren Prozessoren macht, aber von Technologien, wie SSEKeine Zugangsberechtigung von Intel oder das aus meiner Sicht schwächere 3DNow! von AMD lassen die Entwickler immer noch die Finger. Dabei sind hier beachtliche Beschleunigungen durch Parallelverarbeitung mit SIMDKeine Zugangsberechtigung schon auf einem Prozessor seit Pentium III möglich. So kann Beispielsweise mit SSE eine Operation (Addition, Multiplikation, Quadratwurzeln etc.) auf vier Gleitkommazahlen (einfacher Genauigkeit, in C "float") gleichzeitig mit einer Prozessoranweisung erschlagen werden. Das bring schon schnell eine Beschleunigung von Faktor 2.5 (wie in einem meiner BeispieleKeine Zugangsberechtigung gezeigt) ohne in Assembler abtauchen zu müssen. Unter Linux werden diese Befehlssätze auch mit den gebräuchlichen Compilern unterstützt (SEE mit GCCKeine Zugangsberechtigung) - der GNU-Compiler bietet hierfür spezielle Befehle in C und C++. Der Intel-Kompiler sollte hier natürlich noch mehr rausholen.

Graphics processing unit (GPU) sind im Prinzip die neuen Grafikkarten, die eigentlich inzwischen ganze System zum Rechnen darstellen. Eigentlich auf spezielle Probleme ausgelegt, neigen Entwickler diese Leitungspakete für Lineare Algebra, numerische Simulationen in allen Bereichen etc. zu verwenden. Beispielanwendung: Optische Tomografie mit GPUs bei der Suche nach Tumoren: Auswertung in Minuten, anstatt in Stunden (MEDIZIN+elektronikKeine Zugangsberechtigung, Heft xx/2011, S. 24).

GPGPU steht für General-purpose computing on graphics processing units. Die große Tendenz, GPUs für diese Zwecke zu verwenden, wird wohl den Herstellern hoffentlich bereits als Marktlücke einleuchten.

FPGA-basierte Co-Prozessorkarten entlasten den Hauptprozessor und lassen sich individuell Konfigurieren. Warum nicht eigene Prozessor-Befehle entwerfen? Die einfachen Befehle (ADD, MUL, MAC, Quadratwurzeln etc.), die Befehle des Koprozessor, selbst die SSE oder 3DNow! und sogar neue Grafikkarten stehen im Schatten, wenn ein Befehl des FPGA-basierten Coprozessors ganze 3D-Szenen berechnet oder einen ganzen Text im Speicher entschlüsselt, ohne die CPU zu belasten. Die Möglichkeiten FPGA-basierter Co-Prozessorkarten sind gewaltig! Aber die Programmierer werden hier vorerst noch eine Menge dazulernen müssen. Den die Befehle werden selbst entworfen. Die Hardware wird sozusagen mit Software beschrieben. Und das ist wie bei Assembler und Java. Langwierig zu entwickeln resp. nicht besonders Effektiv. Das kann dauern, bis es so richtig los geht. Die Technologie ist jetzt schon da.
http://www.elektroniknet.de/home/bauelemente/fachwissen/uebersicht/aktive-bauelemente/programmierbare-logikasics/aufbau-einer-fpga-basierten-co-prozessorkarte/
AMD stellt eine Plattform "onboard", die gleich mehrere Möglichkeiten für die Einbindung des FPGA bietet. Zur Auswahl steht das direkte Auflöten des FPGA, der Anschluss über einen HTx-Steckplatz oder die Nutzung eines der CPU-Sockel auf einer der Multiprozessor-Platinen. FPGA-Coprozessoren in AMD64-Systemen. Was macht die CPU in Zukunft dann noch? Leerlaufprozess auf 99 %? Immerhin etwas!

MPI, wenn es ein Cluster sein soll. Wenn die Rechenleistung dann noch nicht ausreicht, dann werden mehrere einfache Workstations oder spezielle Leistungsrechner (andere ProzessorarchitekturenKeine Zugangsberechtigung, Erweiterungen von oben) über ein Netzwerk zusammengeschaltet. Und los gehts! Nein leider nicht so schnell, dann ist MPI das Mittel der Wahl und quasi Standard.

Octave soll auch ohne Bibliotheken wie MPI und PVM auskommen, der Programmierer muss aber auch hier mehr tun und lernen. Debian Paket octave-parallel: This is a package to add parallel computing functions to Octave. The parallel computing functions are supported without any additional parallel computing libraries such as MPI and PVM. Siehe auch Octave-Forge - Package parallel. Das nur am Rande.
Ergänzung 2012: Octave kann bis zu 2 Kerne standardmäßig bie Matrizenoperationen verwenden. Auf dem 4-Kerne-Prozessor laufen nur 2 CPUs auf vollast, aber immerhin!

MATLAB-Implicit-Multiprocessing verwendet z.B. für die Sinus-Funktion, Logarithmus-Funktion oder die BLAS-Bibliothek (Basic Linear Algebra Subroutines) mehrere Threads um Rechnersysteme mit mehreren CPUs ohne Änderungen am Code auszunutzen! Wer mehr Beschleunigung aus MATLAB herausholen möchte, benötigt die Paralell-Toolbox und muss sich expliziter Anweisungen zur Parallelisierung von Rechenaufgaben bedienen.
Ergänzung 2012: MATLAB rechnet meine Matrizenoperation mitlerweile ohne spezieller Programmierung standardmäßig auf 4 Kernen meines i5. Danke!

PelicanHPCKeine Zugangsberechtigung: Faszinierend: Während ich noch mein MPI-Cluster müshsam auf mehreren Rechnern von Null auf Basis von Debian installieren dürfte, kann man jetzt einfach eine PelicanHPCKeine Zugangsberechtigung-CD in einen Recher schieben und dann über Netzwerk alle anderen Knoten booten und schon hat man einen Superrechner. Nichteinmal eine Stunde Einrichtungszeit, wenn man weiß was man tut und schon kann man Parallelrechen. Wahrscheinlich der schnellste Weg in den Genuß von Computerclustern zu kommen.

distccKeine Zugangsberechtigung erlaubt verteiltes Compilieren auf mehreren Rechnern.

Die Kombination dieser Technologien ist bereits Verbreitet und es liegt nahe sich darüber Gedanken zu machen. Am besten versucht man auf einem Cluster aus vernetzten Multiprozessorrechnern mit jeweils mehreren CPUs, FPGA-Karten und mehreren GPUs, unter Verwendung der SSE zu Rechnen und verwendet dafür die Bibliotheken OpenMP und MPI, um das letzte Teraflop herauszukitzeln. Aber wie sieht dann der Code aus? Ist er noch gut lesbar und gut zu pflegen. Wie ist die Fehlersuche? Wie schnell ist die Entwicklung?


3. Parallelrechner gestern und heute


Die ersten Parallelrechner gab es schon ein Jahrzehnt nach Einführung der Mikroprozessoren.
1983: Connection Machine 1 mit System mit bis zu 65536 1-Bit Prozessoren, speichergekoppelte Architektur, Hypercube-Verbindungsnetzwerk, Lösung von Problemen aus dem Bereich der Künstlichen Intelligenz
1987: Connection Machine 2 zusätzlich mit mit 2048 Koprozessoren Weitek 3132, für numerische Verfahren verwendet
1987: Intel iPSC/2 mit 16 Intel 80386-Prozessoren

Die Supercomputer heute:

Schavan: "Europas schnellster Rechner sorgt für Innovation" (Pressemitteilung, 26.05.2009)


4. Parllelrechnerarchitekturen


Nachrichten-gekoppelt: Mehrere CPUs besitzen jeweils einen eigenen Speicher und kommunizieren über ein Verbindungsnetzwerk (z.B. Ethernet). → Cluster aus Workstations.
Speicher-gekoppelt: Mehrere CPUs haben einen gemeinsamen Speicher un kommunizieren über ein sehr schnelles Verbindungsnetzwerk (Datenbus). → Multiprozessorrechner

Es gibt natürlich auch Nachrichten-gekoppelte Architekturen, also mehrere Workstations im Cluster, die wiederum aus Rechnern mit Speicher-gekoppelt Architekturen bestehen, also mit mehreren CPUs. Eigentlich gibt es viele davon.


5. Bibliotheken


Zwei Bibliotheken im Fokus:

  • MPI ist ein Standard, der beschreibt, wie Nachrichten und Daten zwischen Rechnern oder Prozessoren zur Parallelverarbeitung ausgetauscht werden können. Es gibt verschiedene Implementierungen (MPICH2, LAM/MPI, OpenMPI). Läuft auf Nachrichten-gekoppelten und Speicher-gekoppelten Parllelrechnerarchitekturen. Umständiger in der Programmierung als OpenMP. Für ein Cluster aus mehreren Rechnern wohl das Beste.
  • OpenMP ist nicht nur eine Bibliothek, es erweitert die Funktionalität des Compilers so, dass ein Programm in mehrere Threads aufgeteilt werden kann. Läuft nur auf Speicher-gekoppelten Parllelrechnerarchitekturen! Also nichts für Cluster. Hauptsächlich nur auf Schleifen aufwendbar. Meiner Ansicht nach die beste Alternative um aus einem Multiprozessorrechner mit möglichst wenig Aufwand viel herauszuholen. Effizient! Die gleichen Programme laufen übrigens auch auf Rechner mit einer CPU.

MPI und OpenMP - Pro und Contra


6. Inhalt der besuchten Vorlesung


Prof. Nowak

Ziele: Einführung in die Hardware und Programmierung von Parallelrechnern. Erwerben der Fähigkeit, Parallelanwendungen zu erstellen.

  • Architektur der Parallelrechner. Klassifizierungen
  • Statische und dynamische Verbindungsnetzwerke
  • Grundbegriffe der Leistungsbewertung
  • Message Passing: Kommunikationsmuster
  • Parallelprogrammierung mit der Standardbibliothek MPI
  • Parallelisierung durch Daten- und Funktionszerlegung
  • Abschätzung der Parallelprogramme; Zeitkomplexität
  • Numerische Algorithmen: Matrizenrechnung
  • Bibliotheken für Parallelrechner (Scalapack, PETSc, ...)

Voraussetzung:
  • Programmieren in C (Grundkenntnisse)


7. Literatur


Michael J. Quinn, Parallel Programmin in C with MPI and OpenMP (gut)
Using MPI-2. Advanced Features of the Message-Passing Interface
Sanders, Parallele Programmierung mit MPI
Chandra, Parallele Programmierung in OpenMP


8. Notizen zum Thema


Software Paket PVM: Parallel Virtual Machine
http://www.sorgonet.com/supercomputing/yourownsupercomputer/pvm.html
Deabin: aptitude search pvm

SISD: Single Instruction Single Data
MISD: Multiple Instruction Single Data
SIMD: Single Instruction Multiple DataKeine Zugangsberechtigung
MIMD: Multiple Instruction Multiple Data

MPMD: Multiple Programm Multile Data, Jeder Prozessor führt ein anderes Programm aus.
SPMD: Single Programm Multile Data, Alle Prozessoren führen das gleiche Programm aus, das evtl. Abschnitte für verschiedene Aufgaben enthält. (Wird hier ausschließlich verwendet)

Trace generation

MPI and Prolog

Parallel Computing
http://cnx.org/content/m18099/latest/

Artikel Parallel-Programmierung mit bekannten Mitteln auf elektroniknet.de.

Das Gesetz von Amdahl und Gustavson-Barsis (Mehr dazu lesen in [Queen] oder

Beispielkonfigurationen für ParallelrechnerKeine Zugangsberechtigung

VortragKeine Zugangsberechtigung

Rechnezentrumder Uni-Erlangen
http://www.rrze.fau.de/dienste/arbeiten-rechnen/hpc/

HPC2008Keine Zugangsberechtigung


CategoryStudiumSE
Siehe auch MasterStudieninhalte

There are no comments on this page. [Add comment]

Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by WikkaWiki