Abb.1: Parallel Random Access Machine
Die Idee des parallelen Programmierens ist so alt wie Computer. In seinen Memoiren beschreibt Feynman, wie während des Zweiten Weltkrieges in Los Alamos Berechnungen auf mechanischen Computern durch Parallelisierung beschleunigt wurden. In die Abgründe des parallelen Programmierens stürzt man eigentlich aus den zwei Gründen: Um Berechnungen schneller ausführen zu können, als es auf einer Maschine möglich ist, oder für Berechnungen, die man aus Speichergründen nicht auf einer einzelnen Maschine berechnen kann.
Die 50-Jährige Geschichte des parallelen Programmierens hat einige verschiedene Architekturen gesehen, die alle sehr interessant waren. Da aber die Entwicklung der notwendigen Software zu teuer war, kamen sie nie so richtig zum Zuge, sondern verschwanden schnell wieder vom Markt oder wurden aufgekauft. Die bekanntesten Vertreter dürften wohl Danny Hillis' Thinking Machines und Seymour Crays Cray Corporation sein. Thinking Machines vernetzte 64.000 1-Bit Computer in der Connection Machine, die kein Mensch programmieren konnte, aber für bestimmte Spezialprobleme unschlagbar schnell war. Zuerst war Cray der Spezialist für Vektorcomputer, und im Cray T3D vernetzte er Alpha Chips mit einem 3D Torus Interconnect.
Das Hauptproblem des parallelen Programmierens war und ist die Software. Es gibt einfach nicht genug gute parallele Software, die zu vernünftigen Preisen produzierbar ist.
Mit dem Aufkommen von Beowulf-Clustern, also Clustern von Workstations oder gar billigen PCs (commodity), die mit einem billigen Interconnect (meistens nur eine 10 oder 100 MBit/s Netzwerkkarte) verbunden sind, begann der Untergang des exklusiven Clubs der High Performance Rechner. Beowulf Cluster können aber nicht alle teuren High End Maschinen ersetzen, da diese in der Regel einen sehr viel schnelleren (und sehr teuren) Interconnect haben, wodurch die hohe Performanz bei kommunkationsintensiven Problem erst möglich gemacht wird. Seymour Cray sagte einmal: "Jeder kann einen schnellen Prozessor entwickeln. Die Kunst ist es, ein schnelles System zu bauen."
Ein Designer für parallele Algorithmen möchte Code entwickeln, der linear mit der Zahl der verfügbaren Prozessoren skaliert: auf p Prozessoren soll das Programm p-.mal so schnell ablaufen wie auf einem Prozessor. Dieses Optimum kann nur erreicht werden, wenn der sequentielle Algorithmus selbst optimal ist und alle Prozessoren bei minimalen Kommunikationskosten gleichmäßig gut ausgelastet sind. Mit Caching-Effekten kann bei speziellen Anwendungen sogar sublinear beschleunigt werden.
Dieser Traum von der Geschwindigkeit wird durch die Abhängigkeiten der einzelnen Daten voneinander zerstört. Diese Datenabhängigkeiten legen die parallele Komplexität fest, das heißt die minimale Anzahl von Rechenschritten, die ein PRAM-Computer brauchen würde. PRAM steht für Parallel Random Access Machine, gemeint ist ein idealer Parallelrechner mit einem gemeinsamen Speicher, der "unendlich viele" Prozessoren hat. Wären die für ein Problem notwendigen Rechenoperationen völlig unabhängig, könnte jede CPU eine übernehmen, und die Lösung wäre nach einem Rechenschritt derPRAM vorhanden.
Natürlich ist dies eine theoretische Grenze, die ähnlich der Lichtgeschwindigkeit nicht überschritten werden kann.
Abb.1: Parallel Random Access Machine
Wirkliche Systeme, die ihren Speicher unter mehreren Prozessoren aufteilen, skalieren nicht linear, da das Speichermanagement mit zunehmender Anzahl von Prozessoren immer teurer, also langsamer wird. Wir haben in einem Benchmark von Alpha Clustern (Swiss-T1) mit unterschiedlichen Interconnects für Clustersolutions ( siehe [1] im Linkkasten am Artikelende) die Tauglichkeit der Maschinen als hochverfügbarer Cluster-Webserver untersucht.
Abb. 2: Swiss-T1 Architektur
Die Swiss-T1 Architektur mit neun Rechnerknoten reserviert acht Knoten zum Rechnen und einen für das Front End. Daneben gibt es noch eine Entwicklungsunit. Das System mit insgesamt 70 Prozessoren (Alpha 21264, 500MHz) hätte einen theoretischen Gesamtwert von 70 Gflop/s, der erreichbare Wert hängt stark von der Art der Rechnungen ab.
Die Knoten sind durch einen 12x12 Crossbar-Switch verbunden. Die kleinen Zahlen auf der Zeichnung bezeichnen die Gewichte für ein optimales Routing einer all-to-all Kommunikation, die großen Zahlen nummerieren einfach die Nodes durch. Schließlich verfügt das System noch über ein Bandsystem zum Backup (DLT). Das System wurde mit Compaqs True 64 Unix und mit Linux betrieben. Zum Datenaustausch wurden die Bibliotheken MPI und BSP verwendet.
In Forschungsinstituten finden vor allem drei Bibliotheken Einsatz: PVM [2], MPI [3] und BSP [4]. PVM ist am einfachsten zu benutzen, MPI ist die am weitesten verbreitete und BSP ist die für Theoretiker interessantesteBibliothek.
PVM und MPI sind Varianten eines Message Passing Protokolls, d.h. Programme schicken sich gegenseitig Messages zu, wenn sie kommunizieren müssen. Message Passing kann zwar schnell implementiert werden, ist jedoch der Grund, weshalb paralleles Programmieren so schwierig ist. Schon zwei Prozesse können sich gegenseitig in einem Deadlock lahmlegen, da sie endlos darauf warten, dass der andere eine Ressource freigibt. Wir werden uns in diesem Artikel auf MPI und BSP beschränken. Beide sind "Single Instruction, Multiple Data"-Protokolle (SIMD): alle Prozessoren führen die gleichen Anweisungen aus, jedoch mit verschiedenen Daten.
Der Message Passing Interface (MPI) Standard wurde im April 1994 als ein "community effort" festgelegt. Der treibende Faktor war die Portierbarkeit. Verschiedene Hardwarehersteller sollten MPI auf ihren Maschinen anbieten, sodass Kunden änlich wie bei ANSI-C Programmen ihren Code auf verschiedenen Architekturen kompilieren können. Es gibt sowohl Software- als auch Hardware-Implementationen von MPI.
MPI ist der de facto Standard für wissenschaftliches Numbercrunching. Für Linux empfehlen wir die LAM/MPI Implementation. Die Installation ist absolut unproblematisch via rpm oder durch Kompilation des Quellcodes einfach zu erledigen. MPI enthält kein Prozess-Management (die Fähigkeit, Prozesse starten zu können), keine (virtuelle) Maschinen-Konfiguration und auch keine Unterstützung für Input und Output. Folglich ist MPI nur ein Kommunikationsinterface, auf das höhere Schnittstellen aufbauen können. So wurde das PVM-Protokoll in MPI implementiert, um von der hohen Geschwindigkeit dieses Low Level Verfahrens zu profitieren. Ebenso könnte man BSP in MPI implementieren.
Um MPI für die Softwareentwicklung einzusetzen, muss man eigentlich nur wissen, dass allen beteiligten Prozessoren ein so genannter "Rank" zugewiesen wird, über den sie identifiziert werden. Anschließend können sie Messages senden und empfangen und damit mit den übrigen Prozessoren des Clusters kommunizieren. Natürlich stellt MPI Routinen für häufig benötigte Funktionen zur Verfügung, darunter broadcast (ein Prozessor schickt die gleichen Daten an alle Prozessoren) und reduce (Sammeln von Informationen).
| MPI_Init | MPI Initialisieren |
| MPI_Comm_size | herausfinden, wie viele Prozessoren vorhanden sind |
| MPI_Comm_rank | Welcher Prozessor bin ich? |
| MPI_Send | eine Message schicken |
| MPI_Recv | eine Message empfangen |
| MPI_Finalize | MPI terminieren. |
Mit diesem schlichten Interface können alle benötigten Funktionen implementiert werden. Insgesamt umfasst MPI aber stolze 125 Funktionen die man grob in folgende Gruppen einteilen kann: Flexibilität (Datentypen), Robustheit (nonblocking send/receive), Effizienz ("ready mode"), Modularität (Gruppen, Communicators) und Praktikabilität (convenience, kollektive Operationen, Topologien).
Wir haben für das Beispielprogramm ( siehe Listing 1) Ruby gewählt, weil es eine sehr leicht lesbare und zugleich ausdrucksstarke Sprache ist, mit der die wesentlichen Ideen gut vermittelt werden können. Emil Ong hat MPI Bindungen für Ruby geschrieben.
MPI Ruby passt die Leistungsfähigkeit von MPI in das objektorientierte Modell der Sprache ein. So können das Buffer- und Datentyp-Management, wie sie in C, C++ oder Fortran nötig sind, von Ruby intern erledigt werden. Die MPI Messages werden in Ruby als Objekte behandelt, MPI Ruby unterstützt die meisten MPI-Funktionen.
Listing 1:
myrank = MPI::Comm::WORLD.rank() # wer bin ich?
csize = MPI::Comm::WORLD.size() # wie viele Prozessoren gibt es?
if myrank % 2 == 0 then
# "gerade" Prozessoren senden
if myrank != csize - 1 then
# der letzte hat keinen Empfänger mehr
hello = "Hello, I'm #{myrank}, you must be #{myrank+1}"
MPI::Comm::WORLD.send(hello, myrank + 1, 0)
end
else
# "ungerade" Prozessoren empfangen
msg, status = MPI::Comm::WORLD.recv(myrank - 1, 0)
puts "I'm #{myrank} and this message came from " +
#{status.source} with tag #{status.tag}:"
puts " '#{msg}'"
end
Und wenn man das Programm mit sechs Prozessoren laufen lässt:
% mpirun -np 6 mpi_ruby example.rb
I'm 1 and this message came from 0 with tag 0:
'Hello, I'm 0, you must be 1'
I'm 3 and this message came from 2 with tag 0:
'Hello, I'm 2, you must be 3'
I'm 5 and this message came from 4 with tag 0:
'Hello, I'm 4, you must be 5'
Damit ist die Kommunikationsmethode zwischen den verschiedenen Prozessoren klar. Listing 2 zeigt ein etwas sinnvolleres Beispiel, nämlich die Berechnung der Kreiszahl Pi durch numerische Integration. Jeder Prozessor ist für einen eigenen Teilbereich des Integrationsintervalls zuständig, sodass die Zahl der verfügbaren Rechenwerke voll zum Tragen kommt.
Listing 2:
PI25DT = 3.141592653589793238462643
NINTERVALS = 10000
$rank = MPI::Comm::WORLD.rank()
$size = MPI::Comm::WORLD.size()
$startwtime = MPI.wtime()
$h = 1.0 / NINTERVALS
$sum = 0.0
($rank + 1).step(NINTERVALS, $size) do |i|
x = $h * (i - 0.5)
$sum += (4.0 / (1.0 + x**2))
end
mypi = $h * $sum
$pi = MPI::Comm::WORLD.reduce(mypi, MPI::Op::SUM, 0)
if $rank == 0 then
printf "pi is ~= %.16f, error = %.16f\n",
$pi, ($pi - PI25DT).abs
$endwtime = MPI.wtime()
puts "wallclock time = #{$endwtime-$startwtime}"
end
Wie oben wird beim Programaufruf die Zahl der Prozessoren mit angegeben: % mpirun -np 5 mpi_ruby my-mpi-prog.rb
Seit 1955 ist von Neumanns Modell des sequenziellen Rechnens akzeptiert, aber es gibt bis heute kein echtes Gegenstück für das Parallel Computing. Die meisten aktuellen Ansätze basieren auf dem message-passing, sind aber oft nicht optimal geeignet und haben das Problem, dass der oben erwähnte Deadlock-Zustand mit zunehmender Komplexität der Software immer häufiger eintreten kann. Außerdem ist es beim Message Passing auch nicht möglich, die Rechenzeit vorherzusagen.
Das BSP-Modell bietet eine abstrakte Low Level Programstruktur, die auf Supersteps basiert. Dadurch wird die Fehlersuche einfacher und das Deadlock Problem beseitigt. Ein weiterer Nebeneffekt ist, dass man fast genauso einfach über die Korrektheit von Code argumentieren kann wie im sequenziellen Fall.
Die BSPlib besticht durch ihre Schlankheit: Es sind nur 20 Funktionen im Gegensatz zu den 125 von MPI. Die Installation erfolgt durch einfaches Übersetzen der bsplib Bibliothek oder der Paderborner Bibliothek (PUB). Die PUB-Version ist aktueller, da sich das Core-Team der BSP-Forschungsgruppe mit einen Startup selbstständig gemacht hat und sich nur noch hobbymäßig um BSP kümmert, auch wenn viele Konzepte aus BSP in ihren Startup (Sychron) eingeflossen sind.
Ein BSP Computer besteht aus Prozessor/Speicher Paaren, einem globalen Kommunikationsnetzwerk und einem Mechanismus zur effizienten Barriersynchronisation der Prozessoren. Der Begriff wurde bewusst so vage gefasst. In der Praxis kann ein BSP Computer fast alles sein, ein PC, ein Cluster von Workstations, eine echte parallele Maschine wie ein Cray T3D.
Die grundlegende Idee von BSP sind Supersteps. Während eines Supersteps sind Kommunikation und Rechnen entkoppelt, sodass ein Deadlock nicht aufteten kann. Die Prozessoren erledigen so viel Arbeit, wie mit den aktuell vorhandenen Daten möglich ist. Ein Datenaustausch mit anderen Prozessoren findet erst statt, wenn alle ihre Arbeit abgeschlossen haben. Nach Beendigung des Datentransfers wird die Barriersynchronisation Aufgerufen, und der nächste Superstep fängt an.
Abb. 3: Supersteps
Mit einem Kostenmodell schafft man eine quantitative Grundlage für die Wahl eines Algorithmus. Durch die Trennung von Kommunikation und Synchronisation und die Einfachheit der Superstepstruktur ist es nicht schwer, ein passendes Kostenmodell zu finden. Die Kosten werden in Steps oder Floating Point Operations (FlOps) für jeden Teil des Programms gemessen. Die Kostenparameter sind die BSP-Parameter der Maschine sowie die Parameter, die durch den Algorithmus und seine Implementation festgelegt sind.
Da ein BSP-Programm aus einer Sequenz von Supersteps besteht, sind die Kosten für das gesamte Programm die Summe aller seiner Supersteps.
Mit welchen Kenngrößen kann man nun die Performanz vorhersagen? Ausführliche Untersuchungen haben gezeigt, dass vier Schlüsselparameter ausreichen [5]:
Da die Prozessorgeschwindigkeit s im Prinzip ein Normalisierungsfaktor ist, bleiben drei unabhängige Parameter: p, l und g.
Wenn wir mit w die maximale Zeit für die lokalen Rechnungen bezeichnen und mit h die maximale Zahl an notwendigen Messages pro Prozessor, können wir die Kosten für einen Superstep wie folgt berechnen:Kosten = w + g * h + l
Die Werte der Parameter werden in Benchmarks gemessen, in denen die durchschnittlichen Rechen- und Kommunikations-Lasten simuliert werden [6]. Zum Beispiel hat eine Silicon Graphics Power Challenger mit einer konstanten Node-Leistung von 75 MegaFlOps einen g-Wert von ungefähr 10 FlOps pro Wort und einen l-Wert von circa 1000 FlOps [7]. Ein CrayT3D hat einen niedrigeren l-Wert, da seine spezielle Kommunikatioinshardware schneller ist. Intuitiv klar ist hier, dass l stark von p abhängt: vier Prozessoren können viel schneller synchronisiert werden als 512.
Die wahre Laufzeit und die vorhergesagte Laufzeit eines parallelen Sortieralgorithmus auf einer IBM SP2. Das Bild ist nicht ganz einfach zu lesen, da die Rechenzeit die Kommunikationszeit dominiert.
Das BSP-Modell ist ein sehr einfaches Kostenmodell. Umso erstaunlicher ist, dass es sich in der Praxis sehr gut bewährt, um einen groben Überblick über die wahrscheinliche Rechenzeit zu erhalten. Damit hilft es bei der Auswahl des optimalen Algorithmus für die Lösung eines vorgegebenen Problems.
Mit dem Profiling Tool bsprof steht noch ein einfacher Profiler zur Verfügung, der es erlaubt, die Rechenzeit auf verschiedenen Plattformen vorherzusagen, wobei als Grundlage der Ablauf auf einer Referenzplattform verwendet wird. Rolls-Royce verwendet dieses Verfahren, um bei Strömungssimulationen für ihre Triebwerke die optimale Hardware-Konfiguration zu wählen.
Auf vorgegebener Hardware sind PVM und MPI in etwa gleich schnell. Die höherstufigen BSP-Implementationen sind gelegentlich langsamer, dafür ist die Entwicklungszeit jedoch kürzer.
Tabelle 2: BSP Befehle
Initialisation
bsp_init
bsp_begin
bsp_end
Halt
bsp_abort
Enquiry
bsp_pid
bsp_nprocs
bsp_time
Synchronisation
bsp_sync
DRMA
bsp_push_reg
bsp_pop_reg
bsp_put
bsp_get
BSMP
bsp_set_tagsize
bsp_send
bsp_qsize
bsp_get_tag
bsp_move
High Performance
bsp_hpput
bsp_hpget
bsp_hpmove
Die High Performance Befehle sind ungepufferte bidirektionale Kommunikationen, die zu jedem Zeitpunkt des Supersteps statffinden können. Wenn sich diese Daten während des Supersteps ändern sollten, sind fehlerhafte Resultate oft die Folge.
Listing 3 zeigt ein paar Beispielprogramme für BSP-Rechner. Sie werden mit bsprun gestartet.
Listing 3:
#include "bsp.h"
#include
void main(void) {
bsp_begin(bsp_nprocs());
printf("Hello BSP Worldwide from process %d of %d\n",
bsp_pid(),bsp_nprocs());
bsp_end();
}
Das folgende C-Programm jongliert mit den Prozessornummern.
#include "bsp.h"
void spmd_start();
char usage_str[] = "-p ";
int nprocs=0;
int reverse(int x) {
bsp_push_reg(&x,sizeof(int));
bsp_sync();
bsp_put(bsp_nprocs()-bsp_pid()-1,&x,&x,0,sizeof(int));
bsp_sync();
bsp_pop_reg(&x);
return x;
}
void spmd_start() {
int xbefore, xafter, i;
bsp_begin(nprocs);
xbefore = bsp_pid();
xafter = reverse(xbefore);
for(i=0;i= argc) {
command_line_opts = 0;
} else if ((strcmp(argv[i],"-p")==0) &&
(sscanf(argv[i+1],"%d",&temp))) {
nprocs = temp;
i += 2;
} else {
bsp_abort("{%s}: unknown option \"%s\"\n\t%s\n",
argv[0],argv[i],usage_str);
}
}
if (nprocs<1) bsp_abort("{%s} usage: %s",argv[0],usage_str);
spmd_start();
exit(0);
}
Die Industrie verwendet verschiedene Modelle, die alle mehr oder weniger an das alte RPC (Remote Procedure Call) erinnern.
CORBA (Common Object Request Broker Architecture) ist eine Architektur und Spezifikation, um in einem Netzwerk Programobjekte zu kreieren, zu verteilen und zu verwalten. Mittels eines "Interface Broker" können Programme auch von verschiedenen Herstellern miteinander kommunizieren. CORBA worde durch die Object Management Group (OMG) geschaffen, die über 500 Mitglieder umfasst. ISO und X/Open haben CORBA ihren Segen als Standardarchitektur für verteilte Objekte gegeben.
Das CORBA zugrundeliegende Konzept ist der Object Request Broker (ORB). Mittels ORB kann ein Klient von einem Serverprogramm oder -objekt Services anfordern, ohne nähere Informationen über den Server zu benötigen. Mittels dem Inter-ORB Protocol (GIOP, IIOP fürs Internet) werden die Requests gesendet. IIOP basiert auf TCP. Microsoft liefert als hauseigene Alternative zum CORBA-Standard sein Distributed Component Object Model (DCOM). Es gibt jedoch ein Gateway zwischen DCOM und CORBA. DCOM kommt zwar mit guten Tools, ist aber wohl nur auf Microsoft-Platformen von Interesse.
Suns Version von CORBA ist die Remote Method Invocation (RMI). RMI ist die Java-Version des Remote Procedure Call (RPC), mit der Erweiterung, dass Objekte mit ihren Methoden verschickt werden können. Sun nennt das "moving behavior".
Generell ist CORBA/RMI/DCOM geringfügig langsamer als MPI/RMI/DCOM, da bei ersterem ziemlich viel mit Reflexionsmethoden gearbeitet wird. Dafür erfordert CORBA/RMI/DCOM weniger Entwicklungsarbeit und ist objektorientiert. Der wahre Grund für die Vorherschaft von MPI im wissenschaftlichen Bereich dürfte aber wohl die gigantische Codemenge sein, die sich mittlerweile angehäuft hat. Zudem kann man mit den Ruby-MPI Bindings auch wieder objektorientiert arbeiten.
Verteilte Anwendungen wie Seti oder Webservices wie das aufkommende .NET, aber auch Peer-to-Peer-Anwendungen wie Napster fallen in die Kategorie paralleler Anwendungen, sind aber in der Regel weniger kommunikationsintensiv und zeitkritisch als wissenschaftliche MPI und BSP Anwendungen.
Eine andere, starke Konkurrenz für Parallele Systeme könnte aber von Startups wie Celoxica kommen, die FPGA-Systeme konstruieren. Field Programmable Gate Arrays können Programmanweisungen in Hardware kompilieren und dann mit der Geschwindigkeit und der massiven Parallelität von Chips agieren. Handel-C ist eine C-ähnliche Low Level Sprache, die direkt in FPGA-Gates kompiliert werden kann, die auf Xilinx-Gate Arrays ausgeführt werden können. Diese Technik kommt aus der Chipentwicklung: Intel benutzt zum Beispiel FPGAs um seinen Chips im Simulator zu testen (wenn normale Workstations zu langsam werden). Eine Schonfrist gibt es aber noch, denn es gibt zur Zeit noch keine Hochsprachen, mit der größere Applikationen effektiv programmiert werden können. Listing 4 zeigt ein Handel-C Code Beispiel. Die par-Anweisungen erlauben es parallel Code in C zu schreiben.
Listing 4:
#include "harp2.h"
const dw=16; /* bandwidth */
void main (chan (out) STDOUT: dw,
chan (in) STDIN : dw,
eram x0[127]= harp2lram : dw,
eram x1[127]= harp2hram : dw
)
{
int n:8;
int ndash:8;
int m0 : dw;
int i0 : 1;
.....
/* perform multiplication in parallel, using Russian Peasant's alg. */
par {
{
par { { b0=(5);}
{ if (a0\\15) {i0, a0= 1, -a0;} }
}
do { if (a0<-1) m0=m0+b0;
a0, b0 = a0 >>1, b0 <<1;
}
while (a0!=0);
if (i0) m0=-m0;
} /* end of 1 par process */
{
par { { b1=(12);}
{ if (a1\\15) {i1, a1= 1, -a1;} }
}
do { if (a1<-1) m1=m1+b1;
a1, b1 = a1 >>1, b1 <<1;
}
while (a1!=0);
if (i1) m1=-m1;
} /* end of 1 par process */
{
.....
[1] Clustersolutions, www.clustersolutions.com/
[2] PVM, www.epm.ornl.gov/pvm/pvm_home.html
[3] MPI, MPI, www.mpi-forum.org/
[4] BSP, www.bsp-worldwide.org/
[5] Questions and answers about BSP,
http://web.comlab.ox.ac.uk/oucl/publications/tr/tr-15-96.html
[6] Bspprobe,
www.bsp-worldwide.org/implmnts/oxtool/contrib.html
[7] Bspparameters,
www.bsp-worldwide.org/implmnts/oxtool/params.html
[8] www.seti.org
[9] www.napster.com
Richard P. Feynman, Sie belieben wohl zu scherzen, Mr. Feynman.
Piper, 1996
Thinking Machines, www.think.com
Cray, www.cray.com/
Beowulf, www.beowulf.org/
LAM-MPI, www.lam-mpi.org/linux/.
Ruby, www.ruby-lang.org
bsplib, www.bsp-worldwide.org/implmnts/oxtool/download.html
PUB, www.uni-paderborn.de/~pub
Sychron, www.sychron.com/
Handel-C, http://users.comlab.ox.ac.uk/ian.page/papers.html
Celoxica, www.celoxica.com/