Robust Scalable Sorting

Sortieren ist eines der wichtigsten algorithmischen Grundlagenprobleme. Es ist daher nicht verwunderlich, dass Sortieralgorithmen in einer Vielzahl von Anwendungen benötigt werden. Diese Anwendungen werden auf den unterschiedlichsten Geräten ausgeführt -- angefangen bei Smartphones mit leistungseffizienten Multi-Core-Prozessoren bis hin zu Supercomputern mit Tausenden von Maschinen, die über ein Hochleistungsnetzwerk miteinander verbunden sind. Spätestens seitdem die Single-Core-Leistung nicht mehr signifikant steigt, sind parallele Anwendungen in unserem Alltag nicht mehr wegzudenken. ... mehrDaher sind effiziente und skalierbare Algorithmen essentiell, um diese immense Verfügbarkeit von (paralleler) Rechenleistung auszunutzen. Diese Arbeit befasst sich damit, wie sequentielle und parallele Sortieralgorithmen auf möglichst robuste Art maximale Leistung erzielen können. Dabei betrachten wir einen großen Parameterbereich von Eingabegrößen, Eingabeverteilungen, Maschinen sowie Datentypen.

Im ersten Teil dieser Arbeit untersuchen wir sowohl sequentielles Sortieren als auch paralleles Sortieren auf Shared-Memory-Maschinen. Wir präsentieren In-place Parallel Super Scalar Samplesort (IPS⁴o), einen neuen vergleichsbasierten Algorithmus, der mit beschränkt viel Zusatzspeicher auskommt (die sogenannte „in-place” Eigenschaft). Eine wesentliche Erkenntnis ist, dass unsere in-place-Technik die Sortiergeschwindigkeit von IPS⁴o im Vergleich zu ähnlichen Algorithmen ohne in-place-Eigenschaft verbessert. Bisher wurde die Eigenschaft, mit beschränkt viel Zusatzspeicher auszukommen, eher mit Leistungseinbußen verbunden. IPS⁴o ist außerdem cache-effizient und führt $O(n/t\log n)$ Arbeitsschritte pro Thread aus, um ein Array der Größe $n$ mit $t$ Threads zu sortieren. Zusätzlich berücksichtigt IPS⁴o Speicherlokalität, nutzt einen Entscheidungsbaum ohne Sprungvorhersagen und verwendet spezielle Partitionen für Elemente mit gleichem Schlüssel. Für den Spezialfall, dass ausschließlich ganzzahlige Schlüssel sortiert werden sollen, haben wir das algorithmische Konzept von IPS⁴o wiederverwendet, um In-place Parallel Super Scalar Radix Sort (IPS²Ra) zu implementieren.
Wir bestätigen die Performance unserer Algorithmen in einer umfangreichen experimentellen Studie mit 21 State-of-the-Art-Sortieralgorithmen, sechs Datentypen, zehn Eingabeverteilungen, vier Maschinen, vier Speicherzuordnungsstrategien und Eingabegrößen, die über sieben Größenordnungen variieren. Einerseits zeigt die Studie die robuste Leistungsfähigkeit unserer Algorithmen. Andererseits deckt sie auf, dass viele konkurrierende Algorithmen Performance-Probleme haben: Mit IPS⁴o erhalten wir einen robusten vergleichsbasierten Sortieralgorithmus, der andere parallele in-place vergleichsbasierte Sortieralgorithmen fast um den Faktor drei übertrifft. In der überwiegenden Mehrheit der Fälle ist IPS⁴o der schnellste vergleichsbasierte Algorithmus. Dabei ist es nicht von Bedeutung, ob wir IPS⁴o mit Algorithmen vergleichen, die mit beschränkt viel Zusatzspeicher auskommen, Zusatzspeicher in der Größenordnung der Eingabe benötigen, und parallel oder sequentiell ausgeführt werden. IPS⁴o übertrifft in vielen Fällen sogar konkurrierende Implementierungen von Integer-Sortieralgorithmen. Die verbleibenden Fälle umfassen hauptsächlich gleichmäßig verteilte Eingaben und Eingaben mit Schlüsseln, die nur wenige Bits enthalten. Diese Eingaben sind in der Regel „einfach” für Integer-Sortieralgorithmen. Unser Integer-Sorter IPS²Ra übertrifft andere Integer-Sortieralgorithmen für diese Eingaben in der überwiegenden Mehrheit der Fälle. Ausnahmen sind einige sehr kleine Eingaben, für die die meisten Algorithmen sehr ineffizient sind. Allerdings sind Algorithmen, die auf diese Eingabegrößen abzielen, in der Regel für alle anderen Eingaben deutlich langsamer.

Im zweiten Teil dieser Arbeit untersuchen wir skalierbare Sortieralgorithmen für verteilte Systeme, welche robust in Hinblick auf die Eingabegröße, häufig vorkommende Sortierschlüssel, die Verteilung der Sortierschlüssel auf die Prozessoren und die Anzahl an Prozessoren sind. Das Resultat unserer Arbeit sind im Wesentlichen vier robuste skalierbare Sortieralgorithmen, mit denen wir den gesamten Bereich an Eingabegrößen abdecken können. Drei dieser vier Algorithmen sind neue, schnelle Algorithmen, welche so implementiert sind, dass sie nur einen geringen Zusatzaufwand benötigen und gleichzeitig unabhängig von „schwierigen” Eingaben robust skalieren. Es handelt sich z.B. um „schwierige” Eingaben, wenn viele gleiche Elemente vorkommen oder die Eingabeelemente in Hinblick auf ihre Sortierschlüssel ungünstig auf die Prozessoren verteilt sind.
Bisherige Algorithmen für mittlere und größere Eingabegrößen weisen ein unzumutbar großes Kommunikationsvolumen auf oder tauschen unverhältnismäßig oft Nachrichten aus. Für diese Eingabegrößen beschreiben wir eine robuste, mehrstufige Verallgemeinerung von Samplesort, die einen brauchbaren Kompromiss zwischen dem Kommunikationsvolumen und der Anzahl ausgetauschter Nachrichten darstellt. Wir überwinden diese bisher unvereinbaren Ziele mittels einer skalierbaren approximativen Splitterauswahl sowie eines neuen Datenumverteilungsalgorithmus. Als eine Alternative stellen wir eine Verallgemeinerung von Mergesort vor, welche den Vorteil von perfekt ausbalancierter Ausgabe hat. Für kleine Eingaben entwerfen wir eine Variante von Quicksort. Mit wenig Zusatzaufwand vermeidet sie das Problem ungünstiger Elementverteilungen und häufig vorkommender Sortierschlüssel, indem sie schnell qualitativ hochwertige Splitter auswählt, die Elemente zufällig den Prozessoren zuweist und einer Duplikat-Behandlung unterzieht. Bisherige praktische Ansätze mit polylogarithmischer Latenz haben entweder einen logarithmischen Faktor mehr Kommunikationsvolumen oder berücksichtigen nur gleichverteilte Eingaben ohne mehrfach vorkommende Sortierschlüssel. Für sehr kleine Eingaben schlagen wir einen einfachen sowie schnellen, jedoch arbeitsineffizienten Algorithmus mit logarithmischer Latenzzeit vor. Für diese Eingaben sind bisherige effiziente Ansätze nur theoretische Algorithmen, die meist unverhältnismäßig große konstante Faktoren haben. Für die kleinsten Eingaben empfehlen wir die Daten zu sortieren, während sie an einen einzelnen Prozessor geschickt werden.
Ein wichtiger Beitrag dieser Arbeit zu der praktischen Seite von Algorithm Engineering ist die Kommunikationsbibliothek RangeBasedComm (RBC). Mit RBC ermöglichen wir eine effiziente Umsetzung von rekursiven Algorithmen mit sublinearer Laufzeit, indem sie skalierbare und effiziente Kommunikationsfunktionen für Teilmengen von Prozessoren bereitstellt.
Zuletzt präsentieren wir eine umfangreiche experimentelle Studie auf zwei Supercomputern mit bis zu 262144 Prozessorkernen, elf Algorithmen, zehn Eingabeverteilungen und Eingabegrößen variierend über neun Größenordnungen. Mit Ausnahme von den größten Eingabegrößen ist diese Arbeit die einzige, die überhaupt Sortierexperimente auf Maschinen dieser Größe durchführt. Die RBC-Bibliothek beschleunigt die Algorithmen teilweise drastisch – einen konkurrierenden Algorithmus sogar um mehr als zwei Größenordnungen. Die Studie legt dar, dass unsere Algorithmen robust sind und gleichzeitig konkurrierende Implementierungen leistungsmäßig deutlich übertreffen. Die Konkurrenten, die man normalerweise betrachtet hätte, stürzen bei „schwierigen” Eingaben sogar ab.

Sorting is one of the most important basic algorithmic problems. Thus, it is not a surprise that sorting algorithms are needed in a very large number of applications. These applications are executed on a wide range of different machines–from smartphones with energy-efficient multi-core processors to supercomputers with thousands of machines interconnected by a high-performance network. Since single-core performance has stagnated, parallel applications have become an indispensable part of our everyday lives. Efficient and scalable algorithms are key to take advantage of this immense availability of (parallel) computing power. ... mehrIn this thesis, we study sequential and parallel sorting algorithms aiming at robust performance for a diverse set of input sizes, input distributions, data types, and machines.

In the first part of this thesis, we study sequential sorting as well as parallel sorting on shared-memory machines. We propose In-place Parallel Super Scalar Samplesort (IPS⁴o), a new comparison-based algorithm that is provably in-place, i.e., the amount of additional memory does not depend on the size of the input. An essential result is that the in-place property improves the performance of IPS⁴o compared to similar non-in-place algorithms. Until now, the in-place feature has usually been associated with a loss of speed for most algorithms. IPS⁴o is also provably cache-efficient and performs $O(n/t\log n)$ work per thread when executed with $t$ threads. Additionally, IPS⁴o incorporates a branchless decision tree to minimize the number of branch mispredictions, takes advantage of memory locality, and handles many elements with equal keys–so-called duplicated keys–by separating them into "equality buckets". For the special case of sorting integer keys, we use the algorithmic framework of IPS⁴o to implement In-place Parallel Super Scalar Radix Sort (IPS²Ra).
We validate the performance of our algorithms in an extensive experimental study involving 21 state-of-the-art sorting algorithms, six data types, ten input distributions, four machines, four memory allocation strategies, and input sizes varying over seven orders of magnitude. On the one hand, the study shows that our algorithms have consistently good performance. On the other hand, it reveals that many competitors have large performance issues: With IPS⁴o, we obtain a robust comparison-based sorting algorithm that outperforms other parallel in-place comparison-based sorting algorithms by almost a factor of three. In the large majority of the cases, IPS⁴o is the fastest comparison-based algorithm. At this point, it is irrelevant whether we compare IPS⁴o to sequential or parallel, in-place or non-in-place algorithms. IPS⁴o even outperforms competing implementations of integer sorting algorithms in many cases. The remaining cases mainly include uniformly distributed inputs and inputs with keys containing only few bits. These inputs are usually "easy" for integer sorting algorithms. Our integer sorter IPS²Ra outperforms other integer sorting algorithms for these inputs in the large majority of the cases. Exceptions are some very small inputs for which most of the algorithms are very inefficient. However, algorithms dedicated for these input sizes are usually much slower for the remaining range of input sizes.

In the second part of this thesis, we study sorting algorithms for distributed systems and their robust scalability with regard to the number of processors, the input size, duplicated keys, and the distribution of input keys to processors. Our main contributions are four robust scalable sorting algorithms that allow us to cover the entire range of input sizes. Three of the four are new fast algorithms that implement low overhead mechanisms to make them scale robustly regardless of "difficult" inputs, e.g., inputs where the location of the input elements is correlated to the key values–so-called skewed element distributions–or inputs with duplicated keys. The fourth algorithm is simple and may be considered as folklore.
Previous algorithms for inputs of medium and large size have an unacceptably large communication volume or an unacceptably large number of message exchanges. For these input sizes, we describe a robust multi-level generalization of samplesort that represents a feasible compromise between a moderate communication volume and a moderate number of message exchanges. We overcome these previously incompatible goals with scalable approximate splitter selection and a new data routing algorithm. As an alternative, we present a generalization of mergesort with the advantage of perfect load balance. For small inputs, we design a variant of quicksort that overcomes the problem of skewed element distributions and duplicated keys with fast high-quality pivot selection, element randomization, and low overhead duplicate handling. Previous practical approaches with polylogarithmic latency either have at least a logarithmic factor more communication or only consider uniform input. For very small inputs, we propose a practical and fast, yet work-inefficient algorithm with logarithmic latency. For these inputs, previous efficient approaches are theoretical algorithms mostly with prohibitively large constant factors. For the smallest inputs, we recommend an algorithm that sorts the data while the input is routed to a single processor.
An important contribution of this thesis to the practical side of algorithm engineering is a communication library that we call RangeBasedComm (RBC). RBC allows an efficient implementation of recursive algorithms with sublinear running time by providing scalable and efficient communication primitives on processor subsets. The RBC library significantly speeds up the algorithms, e.g., one competitor even by more than two orders of magnitude.
We present an extensive experimental study involving two supercomputers with up to 262144 cores, 11 algorithms, 10 input distributions, and input sizes varying over nine orders of magnitude. For all but the largest input sizes, we are the only ones performing benchmarks on these large machine instances. The study also shows that our algorithms have a robust performance and outperform competing implementations significantly. Whereas our algorithms provide consistent performance on all inputs, our competitors' performance breaks down on "difficult" inputs or they literally break.