Cluster-Computing

Einführung

Was ist Cluster-Computing?

Rechenleistung reicht nie aus
® Paralleles Rechnen

erstmals verwendet in Astrophysik

Rechenleistung kostet

spezielle Paralelrechner

"Number-Cruncher"
extrem teuer

Multiprozessor-Systeme

früher sog.

Power-RISC

Idee: verschiedene Desktop-Rechner vernetzen

R kostengünstig
Einzelrechner inzwischen sehr Leistungsstark
Netzwerke mittlerweile auch sehr leistungsstark

extremer Ansatz:

Beowulf-Cluster

Wer braucht Rechner-Cluster?

Life Sciences
Aerospace
E-Commerce
CAD/CAM
Digital Biology
Military Applications

Wie Rechenleisung steigern?

härter arbeiten"work harder"
intelligenter arbeiten"work smarter"
® schnellere Hardware
® schnellere Algorithmen
® Parallele Rechner

Allgemeiner Aufbau

Parallel Applications
Parallel Programming Environments
Cluster-Middleware

Single System Image
Availability Infrastructure

Arbeitet mit Checkpoints (Backups der Systemzustände)

verbirgt die vielen Rechner® fast zu einem Eintrittspunkt für Jobs zusammen

PC/Workstation
Treiber / Communication-Software

TCP/IP

Network-Interface-Hardware
Basis: High-Speed-Network
Beispiel:

NOW

Cluster des Minet

headnode:

dient der Einspeisung der Programme
dazu: Jobverwaltung

dient der Zuweisung der benötigten Rechner zu den Jobs
nicht unbedingt jeder Rechner jederzeit verfügbar
"man sagt was man will, und in derRegel kriegt man auch das was man will"

Adresse: cluster.inf-ra.uni-jena.de

Login per Putty

worker

einzelne Rechner des Cluster

MPI
Jobbeschreibung

normalerweise ein shell-script
spezielle Kommandos

qsub

Übermitteln eines Jobs

qstat

sehen was geht
-j - Datailinformationen zum Job

qdel

löschen eines Jobs

man

manual page anzeigen

ls

Ausgaben (Dateien) listen

cat

Ausgabe einer Datei

vim

Editieren eines Jobs

qacct -j

Accounting-Info für speziellen Job

i Infos: RA-Cluster an der Uni Jena Þ

Zugriff über SSH-Console

z.B. PuTTY SSH-Client
normaler FRZ-Login
muss aber erst freigeschaltet werden ® Mail an Kahaus

Programme für Cluster

Fortran

wir nicht

C
C++

Standartd-Aufrufe

MPI_Init

zuerst aufrufen

MPI_Finalize

zuletzt aufrufen

MPI_COMM_WORLD

alle Prozesse meines Programmes
Communicator-Informationen

MPI_Comm_Rank / MPI::COMM_WORLD.Get_Rank() - fragt Nummer des Prozesses ab

erster:

hat Rank0
Masterprozess

MPI_Comm_Size / MPI::COMM_WORLD.Get_Size() - fragt Zahl der Prozesse ab

zum starten:

compilieren
linken
dazu: mpicc

Shellscript
erspart Kommandozeilen-Parameter
Aufruf: mpicc.lam -showme hello1.c -o hello1

für C-Proggis

warnings abschalten: mpicc.lam -Wall hello1.c -o hello1
oder: mpic++.lam -Wall hello2.cc -o hello2

für C++ -Proggis

Debug-Informationen generieren: mpic++.lam -g hello.cpp -o hello

jobscript formulieren

shell-aufruf vim öffnet shell-editor
#$ -pe lam7 2-10
#$ -j y

Ressourcenangaben für Jobverwaltung
-pe : parallel environment
2-10 Knoten nutzen
lam7 - name des lam
ich habe einen Job, dieser nutzt die lam Bibliothek
-j y - join yes ® Fehlerausgabe und Standardausgabe in gleiche Datei

mpirun.lam C ./hello

C - shortcut zum verteilen auf allen Verfügbaren Rechnern

mpirun.lam C -t ./hello

tracing erstellen
dann:rm -f ring.ltr
lamtrace -mpi .ltr

löschen (rücksetzen der Tracing-Datei)
ausgeben der tracing-Datei

argv[0] = Name des aufgerufenen Programmes
argv[i] (i>0) ® Kommandozeilen-Parameter
Parameterübergabe mpirun.lam C ./hello
Sortieren (numerisch): mpirun.lam C ./hello | sort -n

makefile

zur Automatisierung des Compile-Prozesses
Struktur: 3 Targets

all: exchange

debug.o: debug.c debug.h
mpicc -c debug.c

exchanger.o: exchanger.cc exchanger.h
mpic++ -c exchanger.cc
main.o: main.cc
mpic++ -c main.cc
exchange: debug.o exchanger.o main.o
mpic++ debug.o exchanger.o main.o -o exchange

Name des Makefiles per default immer makefile
siehe auch: info make

iHinweis:

lam einheitlich nutzen!

"provisorisches" Starten:

lamboot
lamnodes: Ausgeben des LAM-Environment
mpirun -np 4 ./
lamhalt

Programmierumgebungen
für Cluster

zwei wichtigste

PVM
MPI
beide sind allgemein verwendbar für parallele Rechensysteme
nicht nur für Cluster

Message Passing vs.
gemeinsamer Speicher

eng gekoppelt:
Speicherkopplung

gemeinsamer Speicher

verteilter Speicher mit
gemeinsamen Adressraum

lose gekoppelt:

Nachrichten-Kopplung

wird bei den meisten Clustern verwendet
Eigenschaften

jede CPU / Cluster-Knoten hat eigenen lokalen Speicher
Q kein gemeinsamer Speicher
Architektur einfach skalierbar
Speicher-Schnittstelle kein Flaschenhals
Tasks kommunizieren explizit untereinander
weite Verbreitung von Sprachen, die auf Weitergabe
von Nachrichten beruhen, einige standardisiert
MPI und PVM sin dabei die mit Abstand bedeutendsten Umgebungen
virtueller gemeinsamer Speicher

"virtual shared memory"
hat sich bei verteilten Systemen wenig durchgesetzt

Programmieren

Kommunikation

zweiseitig

blockierend

Send

Point-to-point

Recv

Point-to-point

sendrecv(sbuf,scount,stype,rank,rbuf,rcount,rtype,rank,..)

nicht blockierend

Isend
Irecv
Wait

schließt Isend / Irecv ab

Waitall

mehrseitig

Get
Put
Barrier

keine Datenübertragung an sich
synchronisierend

Bcast

Broadcast
kollektiv

mehrere "Empfänger"

mehrseitig
blockierend

Scatter

aufteilen eines Werte-Vektors
von ausgezeichnetem Knoten auf alle

Gather

"Sammeln" von Werten zu einem Vektor
von mehreren Knoten zu einem ausgezeichneten

Prozessgruppe & Kommunikator
dynamische Arrays

mit malloc ®Speicher auf dem heap wird zugewiesen & Startadresse zurückgegeben
Beispiel:
foo(){
int *senddata = NULL;
int size;
if (!(senddata = malloc())){
perror("allocation impossible")
return -1;
MPI::COMM_WORLD.Abort();
}
}

an der Stelle muss entsprechend size*sizeof(); stehen!

Anwendungen auf Cluster-Rechnern

Ausführung partieller Differentialgleichungen
Klimamodellierung für Ozeane

wichtig für gegenwärtiges Klima
schwierig, da Meeresströmungen von Wirbeln verschiedenster Größe abhängig

an den Polen kleine Wirbel
am Äquator sehr große
®mehrere Skalierungen nötig

Partitionierug

Gesamtbereich in n Teilbereiche zerlegen
Hoffnung: Rechenzeit von T ® (T,n)/() reduzieren
regulär: Prozessoren gleichmäßig den Kartenkoordinaten zuordnen

Problem: 36% der Prozessoren sind Land zugeordnet und somit untätig
® ineffizient
notwendig: flexiblere Struktur

irregulär

ungenutzte Prozessoren markieren & entfernen
nächstliegenden aktiven finden

Simulation von Mikrosystemen

Parameterstudien für optimalen Detektor-Entwurf

z.B. Photodetektor

20 Parameter

Wellenlänge
Einfallswinkel
Schichtdicken
Schichtfolgen
Temperatur
...

Lösungen über System partieller Differentialgleichungen

Aufbau eines verteilten Lastverbundes mit

Condor

Konzepte

High-Performance-Computing
High-Througput-Computing
zur Parallelisierung: Vorgehensweise

1. Partionierung

was sind die atomaren Arbeitseinheiten
® möglichst viele möglichst kleine Einheiten
"Tasks"
Dekomposition kann

funktional oder
spatial sein

2. Kommunikation

wie stehen die Tasks in Beziehung?
Kommunikationsbeziehungen zwischen Tasks = Channels
Task-Channel-Modell
i.d.R. zu feingliedrig

3. Agglomeration

sinvolle Zusammenfassung von Channels?
Maximierung von

Auslastung
Lokalität

4. Abbildung

wie sind Agglomerate auf Prozessoren zu verteilen?
"Kochrezept": 1. ist Taskanzahl

statisch?

2. ist die Kommunikation

strukturiert?

3. Wie lange braucht ein Task?

konstante Ausführungszeit

® baue Agglomeration, die Kommunikation minimiert
ein Agglomerat pro Pozessor

verschiedene Ausführungszeiten

® zyklische Verteilung
einige wenige Agglomerate pro Prozessor

unstrukturiert?

® statische Lastverteilung
Bildung der Agglomerate durch Zusammenfassung immer sovieler Tasks, dass Aufwand pro Agglomerat etwa gleich ist

dynamisch?

2. sind die Tasks

eng gekoppelt?

(viel Kommunikation zwischen den Tasks)
® dynamischer Lastausgleich
schwierigster Fall

lose gekoppelt?

(viel Kommunikation zwischen den Tasks)
® zentrales Master-Worker-Schema

eine Zentrale Instanz, die Verwaltung übernimmt
viele Worker, die eigentliche Berechnung machen

holen sich "Aufgabenpaket" vom Master
bearbeiten dieses
schicken Lösung zu Master zurück

Beispiel: Wärmeleitung in einem Stab

Diskretisierungen: Raum und Zeit seien diskret

Teilung des Stabes in n Abschnitte
Zeitliche Taktung

kleinste Aufgabe (Task): berechne Temperatur einer Stützstelle zu einem Zeitpunkt
Kommunikation: Jeder Prozess braucht zu jedem Zeitpunkt Wert seiner Nachbarn und von sich selbst
aber: oft mehr Tasks (Stababschnitte) als Knoten im Cluster

Kommunikation würde zu bottleneck
ausserdem: Positionen zeitlich voneinander abhängig

® Agglomeration

Erhöhung der Lokalität

benachbarte Tasks zusammenfassen

im Beispiel: jeweils mehrere benachbarte Stababschnitte einem Prozess zuordnen

Abbildung

Leistungsanalyse Parallelrechner

allgemeine Speed-Up Formel
Amdahlsches Gesetz
Amdahl-Effekt
Gesetz von Gustafson-Barsis
Karp-Flatt-Maß
Iso-Effizienz-Metrik

Parallelisierungstechniken

zwei Arten parallelisierbarer Probleme:
peinlich oder inhärent parallele Probleme

quasi von selbst parallelisierbar
Problem zerfällt in große Zahl unabhängiger Teilprobleme
engl.: inherent parallel oder embarrasingly parallel
Beispiele:

Parameterstudien
Monte-Carlo-Simulationen
Datenauswertung

Auswertung großer Datenmengen
Beispiel: Auswertung der Experimente am Teilchenbeschleuniger LHC

Filmproduktion

digitale Bearbeitung: pro Sekunde 25 Bilder bearbeiten
® abendfüllender Spielfilm besteht aus 135 000 voneinander

kombinatorische Probleme

systematisches Testen aller Eingabewerte
brute force
jeder Testlauf unabhängig voneinander
Beispiele:

kryptographische Applikationen
Suchen von großen Primzahlen

® nahezu perfekte Parallelisierung
Kommunikation

Verteilung der Daten des Problemraumes am Anfang
unabhängige Berechnung ohne Kommunikation untereinander
Einsammlung der Teilergebnisse am Ende

Beispiel: Berechnung optischer Beugungsbilder am Rechner

Beschreibung

Maske mit vielen Löchern wird kohärent bestrahlt
Beugung am Mehrfachspalt
Huygensche Prinzip: Jedes Loch (jeder Punkt im Spalt) ist Ausgang einer kugelförmigen Punktwolke
durch konstruktive und destruktive Interferenz entstehen Interferenzmuster
5 optische quellen angeordnet in einem regelmäßigen Fünfeck
hinter Maske treffen Kugelwellen auf einen Schirm im Abstand d

Algorithmus:

Schirm aufteilen in Raster von N_x x N_y diskreten Punkten
in jedem Punkt intensität berechnen

I(x,y) = P_i=1^q(a_i)/(l((x,y),(x_i,y_i)))(cos (2p l((x,y),(x_i,y_i)))/(l)+i sin (2p l((x,y),(x_i,y_i)))/(l))

l = Abstand von Punkt auf Schirm zu Lichtquelle

verwendung einer zentralen Datenstruktur

Prtitionierungs-Schema:

Berechnung des Beugungsbildes auf p Prozesse aufteilen
entscheidend: keine Kommunikationn zwischen Teilgebieten während der eigentlichen Berechnung

geometrisch parallelisierbare Probleme

viele technisch-wissenschaftliche Probleme
Beispiele

partielle Differentialgleichungen
probleme der linearen Algebra
physische Modelle
zelluläre Automaten

Gemeinsamkeit:

Grundelemente der Simulation interagieren nur mit benachbarten Elementen

Gebietszerlegung

Aufteilung des Problemraumes in kleine Teilgebiete
jedes Teilgebiet wird von einem Prozessor bearbeitet
Teilgebiete nichtmehr völlig unabhängig voneinander
benachbarte Teilgebiete interagieren miteinander

Ansätze:

Randgebiete fest vorgegeben
zyklische Randbedingungen

Kommunikation:

möglichst kleine Schnittflächen
möglichst geringe Zahl an Nachbarblöcken

Schachbrettaufteilung oder
Blockstreifenzerlegung

falls Kommunikationsanteil zu groß:

ggf. Rechenlast erhöhen
Ausnutzung des

Amdahl-Effekt

® Speicherplatz für benachbarte Randdaten vorsehen ® "ghost points"
Gebietsaufteilungen

dreieckig
quadratisch
Sechsecke
gemischt
dynamisch

dynamischer Lastausgleich

load balancing
Quellen für ungleiche Lastverteilung

verschiedene CPUs
verschieden große/komplexe Teilprobleme

Beispiel:

Mandelbrotmengen

Ziel

vermeiden von ungleichen Rechnerauslastungen in einem parallelen Rechnersystem
gleiche Verteilung der Rechenlast auf beteiligte Prozessorelemente

vermeidet Wartezeiten
mehr Effizienz bei der gesamten Rechenleistung

Unterscheidung

statische Lastverteilung

static load balancing
Ausführungszeiten?
gleichmäßige Verteilung vorab möglich

dynamische Lastverteilung

Ausführungszeiten
Taskmigration

Beispiel für zentrale dynamische Lastverteilugnach Master-Worker-Schema:

~ @home - Anwendungen
Master-Worker-Schema

Maß für Homogenität:

m = (max T_i-min T_i)/(max T_i)
Ziel: max T_i - min T_i so klein wie möglich
durch sehr fein-granulierte Aufteilung des Problems auf Tasks T_i
aber: nicht zu fein fragmentiert, da sonst Aufwand für Kumminikation und Synchronisation

Algorithmen für den dynamischen Lastausgleich

Identifikation überlasteter und unterausgelasteter Einheiten
umzuverteilende Datenmenge beim Lastausgleich
hinzukommende Zusatzbelastung (overhead) durch DLA-Ausgleich
zwei Klassen von Algorithmen:

diffusions-basierte

lokale Strategie
Nachbarschaftsinformationen einholen
sukzessive Migration von Rechenlasten zwischen benachbarten Einheiten Þ lokaler Lastausgleich
für Punkt-zu-Punkt-Netzwerke

weitere Unterscheidung:

synchron
asynchron

synchron-parallele

globale Strategie
neu bestimmen und verteilen
"scratch and map"
Repartitionierung der Rechenlast
Neuverteilung der neuen Rechenlasten
für Schalter-basierte Netzwerke

Schalter = Switches
i.d.R. ausgelegt als

Kreuzschienen-Verteiler

interessant für Cluster-Rechner

Kommunikation mit beliebigen Knoten Þ globaler Lastausgleich

Anforderungen

Grobkörnigkeit der Aufteilung

Balance zwischen Rechnen und Kommunikation finden

Umgang mit ungleichen Last-Verteilungsmuster

hoher Betrag an ungleicher Last-Verteilung in lokalen Regionen

vorteilhafter: Scratch-and-map

gleichmäßigere globale ungleiche Lastverteilung

vorteilhafter: Diffusions-basierte Verfahren

hohe Adaptions-Frequenzen

vorteilhafter: Diffusions-basierte Verfahren

Beispiele:

Annahmen

SPMD-Programmier-Modell
sämtliche Tasks sind rechen-intensiv
können auf jedem beliebigen PE ausgeführt werden
benötigen (im Prinzip) gleiche Rechenzeit

Rechenlast definierbar durch Anzahl Tasks in der Warteschlange eines PEs!

Anstoß zum Lastausgleich « Anzahl Tasks sinkt unter vordefiniertes Limit

tree walking algorithm
switch walking algorithm

Kommunikation in Cluster-Rechnern

Basis Netzwerkdienste

Gateway

ISO/OSI-Referenzmodelle

Seminarraum 125 CZ
Literatur

< Folien im CAJ
& Heiko Bauke/Stephan Mertens: Cluster-Computing
& Buyya(Monash University Melbourne:
High-Performance-Cluster Compting
& Linux/Unix Befehlsreferenz
& Linux/Unix Kompaktreferenz
& William Gropp - Using MPI
& Michael Quinn - Parallel Programming

< shelldorado.de

iInfo

www.informatikjahr-jena.de Þ
Hauptveranstaltung am 7.10.2006
Scheine:

60% in der Übung
alternativ: Vorlesungsstoff abprüfen lassen ® 2 SWS
oder: beides :)

Erzeugt mit IntelliMind von SRSofware. 27.06.2006 / 10:50:17