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

DesigningParallelAlgorithmsforSMPClustersDissertationderFakultat¨ fur¨ Informations undKognitionswissenschaftenderEberhard Karls Universit at¨ Tubingen¨zurErlangungdesGradeseinesDoktorsderNaturwissenschaften(Dr. rer. nat.)vorgelegtvonDipl. Inform. MartinSchmollingerausReutlingenTubingen¨2003Tagdermundlichen¨ Qualifikation: 29.10.2003Dekan: Prof.Dr.MartinHautzinger1. Berichterstatter: Prof.Dr.MichaelKaufmann2. Prof.Dr.WolfgangRosenstielDanksagungenEsgibtMomenteimLeben,indenenmanwichtigeundrichtungweisendeEntscheidungen treffen muss. Man sollte sich glucklich¨ schatzen,¨ wennmanrechtzeitigbemerkt,dasseinsolcherMomentvorliegt. Ichmochte¨ alldenen danken, die mich ermuntert haben, mir die Zeit fur¨ die Promotionzunehmen.Vor allem mochte¨ ich meinem Betreuer Prof. Dr. Michael Kaufmanndanken,dermirdieMoglichkeit¨ gegebenhatdieseArbeitanzufertigenundmichdabeiinallenBelangenunterstutzt¨ 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 vielenUnternehmungenwieBetriebssport,“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 derPromotiongeglaubthaben.
Publié le : mercredi 1 janvier 2003
Lecture(s) : 13
Tags :
Source : W210.UB.UNI-TUEBINGEN.DE/DBT/VOLLTEXTE/2003/968/PDF/MYDISS.PDF
Nombre de pages : 162
Voir plus Voir moins

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 is created concerning communication. In
general, communication within a node is faster than communication be
tween the nodes due to the use of shared memory. Therefore, there are at
least two levels of hierarchy. Due to modern trends like hierarchical inter-
connection structures, Metacomputing technology, where several parallel
machines are connected, or Grid computing technology that use the In
ternet to unify distributed computing resources in the whole world, there
mightbeevenmorelevelsofhierarchy. Basically,thelowerthelevelofthe
networkforacommunicationoperation,thefasterthecommunicationcan
bedone.
Onthisaccount,efficientalgorithmshavetobedesignedinthewaythat
theparallelaswellasthecommunicationhierarchyisconsidered. Usually,
this is not the case, and the SMP clusters are regarded as non hierarchic .
Moreover, the general approach for the design of a parallel application is
dominated by the use of a particular programming model. The program
mer relies on the efficiency of the implementation of the model for the re
spectiveplatform. Ofcourse,thisstrategydoesalsoleadtofastprograms,
butinordertoreachtheoptimum,itisadditionallyimportanttoadaptthe
algorithms to the hierarchical environment. Another problem is that the
design process of parallel algorithms is in general not supported by meth
ods. Obviously, the design of a parallel algorithm cannot be reduced to a
simplerecipe,however,theconsiderationofgeneraldesignmethodsmaxi
mizestheamountofconsideredoptionsandminimizesthethreatofwrong
ixx
algorithmdesignapproaches.
In the following chapters, we show an alternative way that shows the
dependencies between theoretical cost models, programming models and
SMP clusters. It enables the developer to convert a theoretical analysis of
an algorithm into an efficient implementation for SMP clusters. Besides
the bridge from a theoretical analysis to an efficient implementation, we
present several methods for designing and optimizing parallel algorithms
forSMPclusters. Withthehelpofcasestudies,weexplainthedesignmeth
odsandtheusageofthecostmodelforthealgorithmanalysis.
Chapter 1 is an introduction to the issues of developing parallel algo
rithms. Besides a motivating example for parallel algorithms, the connec
tions between theoretical cost models, programming models and parallel
architecturesaredepicted.
Chapter 2 gives an overview on parallel architectures, cost and pro
gramming models and shows their capability for the development of par-
allelalgorithmsforSMPclusters.
Afterthat,westartwiththeformulationofatheoreticalcostmodelfor
SMPclusters(κNUMA)inChapter3andshowitsusagebytheanalysisof
broadcastproblems,whereoneprocessorhastosendone(individualorgen
eral) message to each of the other processors. The model can be regarded
as a super set for the analysis of algorithms for SMP clusters. Depending
on the properties of a certain SMP cluster and because of the character of
theanalyzedproblem,theusageofareducedmodelmaybesufficientand
makestheanalysismorefeasible.
Chapter4introducesmethodsfordesigningandoptimizingparallelal
gorithmsforSMPclusters. Themethodscanbeappliedtodifferentstages
ofthedesignprocess,beginningatthestageofafine grainedproblempar-
titioning and ending with the optimization of single aspects of parallel al
gorithmsforSMPclusters.
Furtherchaptersarecasestudiesfortheusageofthemethodsforalgo
rithmdesignandfortheusageofthecostmodelfortheanalysis.
In Chapter 5, we show by means of the parallel dense matrix vector-
multiplication how a parallel algorithm is transferred to an SMP cluster,
how redundant data can be used to reduce the number of communica
tion operations and how an unnecessary usage of redundant data can be
avoided. Forthatpurpose,weanalyzeseveraldata distributions.
Chapter 6 presents an optimization method that tries to adapt exist
ing communication patterns to the respective structure of an SMP cluster.
Communicationpatternsofalgorithmscanoftenbeinfluencedbydatadis
tribution. Weattempttodistributethedatainordertoreducethecommu
nication cost maximally. The method is explained using the problem of
transposing distributed matrices in a parallel setting. We present a data
distributionwithwhichanalgorithmisabletotransposeadistributedma
trixwithoutcommunicationoverthenetwork. Atthesametime,thedata

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.