A more efficient set union operation on distributed memory machines

Abstract

Rechnen mit verteilten Systemen ist ein wichtiger Zweig des Fachbereiches Hochleistungsrechnen und ist die Grundlage für große, skalierbare Cluster und Supercomputer. Die Leistung solcher Rechenanlagen wird unter anderem durch Tests wie Graph500 (neben HPL, HPCG und NPB) bewertet. Graph500 nutzt als Hauptmerkmal die gemessene Zeit um eine BFS (Breadth-First-Search, dt. Breitensuche) durchzuführen. BFS und andere Algorithmen, die Graphen iterativ erforschen, haben oft auch Anwendung in der echten Welt. Ein wichtiger Baustein solcher Algorithmen ist dabei die Vereinigung von Mengen, die über unterschiedliche Prozesse verteilt sind. Für endliche Graphen sind sowohl die ursprünglichen Mengen als auch ihre Vereinigung Teilmengen einer endlichen Urmenge. Ziel dieser Arbeit ist eine solche Vereinigung effizienter zu machen.Eine bekannte Strategie für solch eine Vereinigung ist, dass Mengen als Bitmaps dargestellt werden, welche dann mittels einem binären ODER durch einen Allreduce kombiniert werden. Eine zweite Strategie ist, Mengen als Listen ihrer Elemente darzustellen. Ein Allgather hängt dann diese Listen aneinander an. Die Laufzeit der ersten Variante ist dabei abhängig von der Größe der Urmenge, während die Laufzeit der zweiten Variante mit der Größe der verteilten Mengen steigt. Es ist also erkennbar, dass es verschiedene Regime gibt in denen jeweils einer der beiden Strategien schneller ist.Wir stellen im Zuge dieser Arbeit zwei neue Algorithmen vor, die versuchen die Vorteile der beiden Darstellungsweisen von Mengen zu nutzen, um effizient eine Vereinigung zu berechnen. Einer dieser Algorithmen ist darauf optimiert (und auch darauf beschränkt) auf Computer-Systemen ausgeführt zu werden, deren Anzahl von Prozessoren eine Zweierpotenz ist und deren Hierarchie auch ein Zweierpotenzmuster zeigt. Der Andere ist nicht auf eine bestimmte Anzahl von Prozessoren beschränkt. Mittels einer linearen Modellierung der Kommunikationskosten wird die Laufzeit der neuen Algorithmen mit $T \leq \kappa \min(T_\mathrm{Allred}, T_\mathrm{Allgath})$ geschätzt, wobei $\kappa$ eine Konstante nahe 1 ist. Die Laufzeit der neuen Algorithmen wurde experimentell ermittelt und der Laufzeit der naiven Methoden gegenübergestellt. Die Messungen wurden auf dem Hydra Cluster des Lehrstuhls für Paralleles Rechnen an der TU Wien durchgeführt. Dabei konnte die theoretische Abschätzung der Laufzeiten bestätigt werden. Außerdem wurden die Algorithmen als Baustein für eine BFS verwendet, wo sie für große zusammenhängende Graphen (mindestens 10^6 Knoten) zu einer Verkürzung der Laufzeit von bis zu 10% beitragen. Bei nicht-verbundenen Graphen konnte teilweise eine Verbesserung von 70% gemessen werden.

Distributed memory computing is an important branch in the research field of high performance computing and is the foundation for building large, scalable clusters and supercomputers. To compare performance of these compute-systems different established benchmarks are available. Next to renowned benchmarks (e.g., HPL, HPCG and NPB) there is the Graph500 benchmark which uses the execution time of a BFS (Breadth First Search) as the main performance measure. BFS and other graph traversal algorithms are needed in real-world applications such as social network analysis, simulation or infrastructure planing. A base building block of such graph traversal algorithms is computing the union of sets that are distributed over the different processes. For finite graphs the proposed sets and therefore the resulting union are subsets of a universe set of finite size. It is of interest, and also the aim of this thesis, to optimize such a union operation.It is already known that such a union can be calculated by representing the sets as bitmaps and performing an Allreduce using a bitwise OR. Another strategy is to represent the sets as sparse lists of elements and concatenate these distributed lists by an Allgather. The execution time of the first method scales with the size of the universe, and the execution time of the latter method depends on the size of the sets submitted by the different processes. If the size of the submitted sets is large, the first strategy is expected to be faster and for small sets the second variant is expected to be more efficient.We propose in this thesis two new algorithms that take advantage of both (sparse and dense) representations and switch dynamically between them to calculate a union of distributed sets. One is optimized (but also constrained to) compute-systems that have a number of processors and a hierarchical structure that is a power of 2. The other one works for an arbitrary amount of processes. Using a linear cost model the execution time of these algorithms is estimated by $T \leq \kappa \min(T_\mathrm{Allred}, T_\mathrm{Allgath})$ with $\kappa$ being some constant which is close to 1.The performance of the newly proposed algorithms is tested and compared against the naive versions. This is done on the Hydra cluster of the Parallel Computing department at TU Wien. The evaluation confirms the expected run time, with the new algorithms matching (up to constant) the performance of the respective faster naive implementation. Moreover, the new algorithms are used as a building block for an BFS where they lead to a performance increase for large graphs (at least 10^6 vertices) of up to 10%. For disjoint graphs there are performance increases of nearly 70% possible.