Detailansicht
Process reordering in MPI for Cartesian topologies and isomorphic communication neighborhoods
Konrad Johannes Rüdiger Von Kirchbach
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Physik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Computational Science
Betreuer*in
Jesper Larsson Träff
Mitbetreuer*in
Christian Schulz
DOI
10.25365/thesis.59775
URN
urn:nbn:at:at-ubw:1-28220.69536.141966-1
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In dieser Arbeit, stellen wir drei neue Herangehensweisen für eine eins-zu-eins
Zuweisung von Cartesischen Graphen C mit einer isomorphischen Kommunikations-
struktur (auch bekannt als Stempel) auf eine symmetrische Hardwarehierarchie vor.
Zuerst präsentieren wir zwei greedy Methoden, die eine zentralisiert, die andere
verteilt. Beide Methoden benutzten eine Priority Queue um die Ränge den Knoten
zuzuteilen und versuchen dabei die Kommunikation auf den Knoten zu maximieren.
Als Drittes, stellen wir den Hyperplane Algorithmus vor, der den Inputgraphen
rekursiv in zwei Teile teilt und dabei versucht die Kommunikation zwischen den
Partitionen zu minimieren. Das wiederholt er, bis alle Partitionen auf die Knoten
verteilt werden können. Der große Vorteil des Hyperplane Algorithmus ist, dass die
Laufzeit nicht mehr von der Anzahl der Knoten n oder der Kanten m in C abhängt.
Wir vergleichen die vorgestellten Methoden mit MPI’s standard Rangverteilung,
mit der Verteilung die durch das setzen der reordering Flagge in der Funktion
MPI_Cart_create erlangt wird und der allgemeinen Mappingsoftware VieM für unter-
schiedliche Kommunikationsmuster oder Stempel. Der Hyperplane Algorithmus findet
im Schnitt immer bessere Partitionen als die MPI Algorithmen und ist mindestens
genauso gut wie der Nodecart Ansatz, für die getesteten Instanzen. Im Falle des
generellen fünf-punkt Stempels, findet er sogar im Schnitt bessere Mappings als
VieM. Die beiden greedy Algorithmen konnten nur für bestimmte Kommunikations-
muster vorteilhafte Partitionen finden. Wir haben die Kommunikationszeit für die
MPI_Neighbor_alltoall Routine mit unterschiedlich großen Nachrichten gemessen
und konnten zeigen, dass die Rangzuweisungsstrategien, die in dieser Arbeit präsen-
tiert wurden einen positiven Effekt auf die Kommunikationsdauer hat. Schlussendlich
haben wir auch die Instantiierungszeit für die unterschiedlichen Methoden gemessen.
Abstract
(Englisch)
In this thesis, we introduce three new approaches for a one-to-one mapping of Carte-
sian graphs C with isomorphic communication (also called stencils) onto a symmetric
hardware hierarchy. First, we present two greedy approaches, one centralized, one
distributed, both using a priority queue to assign ranks onto the computation nodes,
trying to maximize the number of on-node neighbors. The third approach, the
hyperplane algorithm, recursively partitions the Cartesian graph C into two parts,
while trying to minimize the communication between each partition, until all par-
titions can be mapped onto the computation nodes. The big advantage of the
hyperplane algorithm is the fast runtime, which is no longer directly dependent
on the number of vertices n or edges m in C.
We compared our approaches to MPI’s default rank assignment, MPI’s reordering
scheme in the function MPI_Cart_create, Gropp’s approach Nodecart and the general
mapping tool VieM for different communication patterns or stencils. The hyperplane
algorithm outperformed on average both of MPI’s approaches and outperformed or
matched Nodecart for all stencils on the tested instances. For the general five-point
stencil it was even capable of finding on average partitions with less inter-node
communication than VieM. Both of the greedy approaches are only beneficial for
certain communication patterns, but performed poorly for the general five-point
stencil. We benchmarked the time needed for a MPI_Neighbor_alltoall exchange
and could show that the reordering schemes presented in this thesis improved the
bandwidth for various message sizes. For the sake of completeness, we measured
and compared the instantiation time of all methods.
Schlagwörter
Schlagwörter
(Englisch)
Cartesian Communicators Rank reordering Mapping MPI
Schlagwörter
(Deutsch)
Kartesische Kommunikatoren Rang Zuweisung Mapping MPI
Autor*innen
Konrad Johannes Rüdiger Von Kirchbach
Haupttitel (Englisch)
Process reordering in MPI for Cartesian topologies and isomorphic communication neighborhoods
Paralleltitel (Deutsch)
Prozess-Umstellung in MPI für Kartesische Topologien und Isomorphische Kommunikationsnachbarschaften
Publikationsjahr
2019
Umfangsangabe
121 Seiten : Diagramme
Sprache
Englisch
Beurteiler*in
Jesper Larsson Träff
Klassifikation
54 Informatik > 54.99 Informatik: Sonstiges
AC Nummer
AC15693991
Utheses ID
52802
Studienkennzahl
UA | 066 | 910 | |