Designing parallel algorithms for SMP clusters [Elektronische Ressource] / vorgelegt von Martin Schmollinger

Sujets

• Informatik

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2003
• Nombre de lectures: 13
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

DesigningParallelAlgorithmsfor
SMPClusters
Dissertation
derFakultat¨ fur¨ Informations undKognitionswissenschaften
derEberhard Karls Universit at¨ Tubingen¨
zurErlangungdesGradeseines
DoktorsderNaturwissenschaften
(Dr. rer. nat.)
vorgelegtvon
Dipl. Inform. MartinSchmollinger
ausReutlingen
Tubingen¨
2003Tagdermundlichen¨ Qualifikation: 29.10.2003
Dekan: Prof.Dr.MartinHautzinger
1. Berichterstatter: Prof.Dr.MichaelKaufmann
2. Prof.Dr.WolfgangRosenstielDanksagungen
EsgibtMomenteimLeben,indenenmanwichtigeundrichtungweisende
Entscheidungen treffen muss. Man sollte sich glucklich¨ schatzen,¨ wenn
manrechtzeitigbemerkt,dasseinsolcherMomentvorliegt. Ichmochte¨ all
denen danken, die mich ermuntert haben, mir die Zeit fur¨ die Promotion
zunehmen.
Vor allem mochte¨ ich meinem Betreuer Prof. Dr. Michael Kaufmann
danken,dermirdieMoglichkeit¨ gegebenhatdieseArbeitanzufertigenund
michdabeiinallenBelangenunterstutzt¨ hat.
Bedanken mochte¨ ich mich auch bei Prof. Dr. Wolfgang Rosenstiel fur¨
seineArbeitalszweiterBerichterstatter.
Mein Dank gilt auch meinen aktuellen und fruher¨ en Kollegen des Ar-
beitsbereichs Paralleles Rechnen fur¨ die gute Atmosphar¨ e und die vielen
UnternehmungenwieBetriebssport,“Besseressen”oderBoule.
Zu guter Letzt bedanke ich mich auch bei meinen Freunden und El
tern, die im Gegensatz zu mir immer an den erfolgreichen Abschluss der
Promotiongeglaubthaben.
iiiivZusammenfassung
IndervorliegendenDissertationuntersuchenwirEntwurfs undOptimier
ungsmethoden fur¨ die Entwicklung von parallelen Algorithmen fur¨ SMP
Cluster. Dabei handelt es sich um eine spezielle Architektur von Parallel
rechnern, die zwei verschiedene Konzepte in einem System vereint. SMP
Cluster bestehen aus Rechenknoten, deren Prozessoren speichergekoppelt
sind (shared memory). D.h. die Prozessoren innerhalb eines Rechenkno
tens konnen¨ uber¨ den gemeinsamen Speicher kommunizieren und syn
chronisieren. Die Rechenknoten selbst werden durch ein Verbindungsnet
zwerk miteinander verknupft.¨ Die Kommunikation und Synchronisation
vonProzessoreninverschiedenenRechenknotenerfolgtuber¨ diesesNetz
werk und entspricht einem nachrichtengekoppeltem System bzw. einem
System mit verteiltem Speicher (distributed memory). Diese Organisation
fuhrt¨ zum einen zu einer parallelen Hierarchie, denn Parallelitat¨ gibt es
sowohl innerhalb als auch zwischen den Rechenknoten. Zum anderen
entsteht eine Hierarchie bezuglich¨ der Kommunikation. Im Allgemeinen
istdieKommunikationinnerhalbeinesRechenknotensbeidereingemein
samer Speicher verwendet wird schneller, als die Kommunikation uber¨
ein Verbindungsnetzwerk. Es existieren demnach mindestens zwei Hier
archiestufen. DurchmoderneEntwicklungenwiehierarchischeStrukturen
vonVerbindungsnetzwerken,MetacomputingTechnologien,beidermehr
ereParallelrechnerverbundenwerdenoderGridComputingTechnologien,
die das Internet verwenden um weltweit verteilte Rechenressourcen zu
vereinen, kann es jedoch weitere Hierarchiestufen geben. Auch hier gilt,
je “niedriger”die Ebene in der Netzwerkhierarchie, destoschneller ist die
Kommunikation.
Aus diesem Grund mussen¨ effiziente Algorithmen in der Art gestaltet
werden, dass sowohl die parallele Hierarchie als auch die Kommunikati
onshierarchie berucksichtigt¨ werden. Im Allgemeinen werden beim Ent
wurf von Algorithmen die Hierarchien vernachlassigt¨ und die Maschine
alsnichthierarchischangesehen. Daruber¨ hinausistdieallgemeineVorge
hensweise bei der Erstellung von Programmen dominiert durch das je
weilsverwendeteProgrammiermodell. DerEntwicklerverlasst¨ sichhaufig¨
auf die Effizienz der verwendeten Bibliotheken. Die Verwendung opti
mierter Bibliotheken fuhrt¨ sicherlich ebenfalls zu sehr schnellen Program
vvi
men,dochumwirklichdasOptimumzuerreichenistesnotig¨ auchdieAl
gorithmenandiehierarchischeUmgebunganzupassen. EinweiteresProb
lemist,dassderEntwurfprozessparallelerAlgorithmeninderRegelnicht
gestutzt¨ ist durch die Verwendung von Methoden. Sicherlich kann die
Entwicklung eines parallelen Algorithmus nicht auf ein einfaches Rezept
reduziert werden, dennoch kann die Verwendung allgemeiner Methoden
die Menge berucksichtigter¨ Alternativen erhohen¨ und fehlerhafte Ansatze¨
vermeiden.
In den folgenden Kapiteln zeigen wir einen alternativen Weg auf, der
die Zusammenhange¨ zwischen theoretischen Kostenmodellen, Program
miermodellenundSMPClusternaufzeigtundesdadurchermoglicht¨ eine
theoretischeAnalyseeinesAlgorithmusineineeffizienteImplementierung
fur¨ SMP Cluster munden¨ zu lassen. Neben dieser Brucke¨ von einer theo
retischenAnalysezureffizientenImplementierungstellenwirverschiedene
Methoden fur¨ den Entwurf und die Optimierung von parallelen Algorith
menfur¨ SMPClustervor. AnhandverschiedenerFallbeispieleerklar¨ enwir
dieMethodenunddieVerwendungdesKostenmodellsbeiderAnalyseder
entwickeltenAlgorithmen.
Kapitel 1 ist eine Einfuhr¨ ung in die Problematik der Entwicklung von
parallelen Neben einem motivierenden Beispiel wird der
ZusammenhangzwischentheoretischenKostenmodellen,Programmiermo
dellenundArchitekturendargestellt.
¨Kapitel2gibtdanneineUbersichtuber¨ paralleleArchitekturen,Kosten
und Programmiermodelle und zeigt ihre mogliche¨ Verwendung fur¨ den
EntwurfvonAlgorithmenfur¨ SMPClusterauf.
WirbeginnenmitderFormulierungeinestheoretischenKostenmodells
¨fur SMP Cluster (κNUMA) in Kapitel 3 und zeigen seine Verwendung an
hand der Analyse von broadcast Problemen, bei denen ein Prozessor eine
(individuelleodereinheitliche)NachrichtanjedenanderenPruber ¨
mitteln muss. Wir betrachten das vorgestellte Modell als eine Obermenge
fur¨ die Analyse von Algorithmen auf SMP Clusters. In Abhangigkeit¨ der
Eigenschaften eines speziellen SMP Cluster und aufgrund der Beschaffen
heit des zu untersuchenden Problems kann die Verwendung eines redu
ziertenModellsausreichendseinundmachtdieAnalyseleichter.
Kapitel4stelltMethodenzurEntwicklungvonparallelenAlgorithmen
und zur Optimierung fur¨ SMP Cluster vor. Die Methoden konnen¨ auf
den verschiedenen Ebenen des Entwicklungsprozesses angewendet wer-
den, beginnend bei einer fein granularen Zerlegung des gegebenen Prob
lemsbishinzurOptimierungeinzelnerAspekteparallelerAlgorithmenfur¨
SMPCluster.
Die weiteren Kapitel sind Fallstudien fur¨ die Verwendung der Meth
oden bei der Algorithmusentwicklung und die V des Kosten
modellsbeiderAnalyse.
In Kapitel 5 zeigen wir anhand der parallelen Matrix Vektor Multipli vii
kation, wie ein paralleler Algorithmus auf die SMP Cluster Architektur
ubertragen¨ wird,wieredundanteDatengenutztwerdenkonnen¨ umKom
munikationsoperationeneinzusparenundwieeineunnotige¨ Verwendung
vonredundantenDatenvermiedenwird. DazuwerdenverschiedeneDaten
verteilungenuntersucht.
Kapitel6stelltanhanddesProblemsderTransponierungvonverteilten
MatrizeninparallelerUmgebungeineOptimierungsmethodevor,diever-
sucht existierende Kommunikationsmuster durch geschickte Datenvertei
lungandiejeweiligeStrukturdesSMPClustersanzupassenumdieKom
munikationskosten zu reduzieren. Wir stellen eine Verteilung vor, durch
die das Transponieren einer verteilten Matrix keine Kommunikation uber¨
das Netzwerk benotigt¨ und gleichzeitig den Speicherbedarf je Prozessor
minimiert.
Kapitel 7 ist eine Fallstudie fur¨ den Entwurf eines hierarchisch sensi
tiven Algorithmus. Die Methode schlagt¨ vor ein Problem durch Informa
tionsaustauschinimmerniedrigereEbenenderHierarchiezuverschieben,
bis am Ende lediglich lokale Berechnungen notig¨ sind. Als Beispiel wird
dasRadixSortVerfahrenuntersucht. DiesesVerfahrenermoglicht¨ esganze
ZahlenanhandihrerBinar¨ darstellunginmehrerenIterationenzusortieren.
DabeiwerdeninjederIterationdieZahlenanhandeinesTeilsihrerbinar¨ en
DarstellungineineReihenfolgegebracht. WirzeigendenWegvonderse
quentiellen Version bis zu einer hierarchisch sensitiven parallelen Version
auf, die mit einem Minimum an Kommunikation auskommt und daher
exzellentfur¨ SMPClustergeeignetist.
DieErgebnissederArbeitsindinKapitel8zusammengefasst. DerAn
¨hang A gibt eine Ubersicht der begutachteten Publikationen, die zu den
¨einzelnenKapitelnveroffentlichtwurden.viiiPreface
Inthefollowingthesis, weobservemethodsfordesigningandoptimizing
parallel algorithms for SMP clusters. This particular architecture for par-
allel computers combines two different concepts. SMP cluster consist of
computingnodesthatareshared memorysystems,becausetheprocessors
have access to common resources and especially to the local memory sys
tem. Hence, the processors within the same node are capable to commu
nicateandsynchronizeusingtheshared memory. Aninterconnectionnet
work connects the nodes. Communication and synchronization of proces
sors from different nodes is done over this network and thus, correspond
to a distributed memory system. In the first place, this organization leads
toaparallelhierarchy,becauseparallelismisinvolvedwithinandbetween
the nodes. Secondly, a hierarchy