Dissertation "Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools"

This dissertation focuses on two fundamental sorting problems: string sorting and suffix sorting. The first part considers parallel string sorting on shared-memory multi-core machines, the second part external memory suffix sorting using the induced sorting principle, and the third part distributed external memory suffix sorting with a new distributed algorithmic big data framework named Thrill.

Sorting strings or vectors is a basic algorithmic challenge different from integer sorting because it is important to access components of the keys to avoid repeated operations on the entire string. We focus on sorting large inputs which fit into the RAM of a shared-memory machine. String sorting is needed for instance in database index construction, suffix sorting algorithms, and to order high-dimensional geometric data.

We first survey engineered variants of basic sequential string sorting algorithms and perform an extensive experimental evaluation to measure their performance. Furthermore, we perform experiments to quantify parallel memory bandwidth and latency experiments as preliminary work for designing parallel string sorting algorithms.

We then propose string sample sort as an adaptation of sample sort to string objects and present its engineered version Super Scalar String Sample Sort. This parallel-ready algorithm runs in O(D/w + n log n) expected time, makes effective use of the cache hierarchy, uses word- and instruction-level parallelism, and avoids branch mispredictions. Our parallelization named Parallel Super Scalar String Sample Sort (pS⁵) employs voluntary work sharing for load balancing and is the overall best performing algorithm on single-socket multi-core machines in our experiments.

For platforms with non-uniform memory access (NUMA) we propose to run pS⁵ on each NUMA node independently and then merge the sorted string sequences. To accelerate the merge with longest common prefix (LCP) values we present a new LCP-aware multiway merge algorithm using a tournament tree. The merge algorithm is also used to construct a stand-alone LCP-aware K-way mergesort, which runs in O(D + n log n + n/K) time and benefits from long common prefixes in the input.

Broadly speaking, we propose both multiway distribution-based with string sample sort and multiway merge-based string sorting with LCP-aware merge and mergesort, and engineer and parallelize both approaches. We also present parallelizations of multikey quicksort and radix sort, and perform an extensive experimental evaluation using six machines and seven inputs. For all input instances, except random strings and URLs, pS⁵ achieves higher speedups on modern single-socket multi-core machines than our own parallel multikey quicksort and radix sort implementations, which are already better than any previous ones. On multi-socket NUMA machines pS⁵ combined with the LCP-aware top-level multiway merging was fastest on most inputs.

We then turn our focus to suffix sorting, which is equivalent to suffix array construction. The suffix array is one of the most popular text indexes and can be used for fast substring search in DNA or text corpora, in compression applications, and is the basis for many string algorithms. When augmented with the LCP array and additional tables, the suffix array can emulate the suffix tree in a myriad of stringology algorithms. Our goal is to create fast and scalable suffix sorting algorithms to generate large suffix arrays for real-world inputs. As introduction to suffix array construction, we first present a brief survey of their principles and history.

Our initial contribution to this field is eSAIS, the first external memory suffix sorting algorithm which uses the induced sorting principle. Its central loop is an elegant reformulation of this principle using an external memory priority queue, and our theoretical analysis shows that eSAIS requires at most Sort(17 n) + Scan(9 n) I/O volume. We then extend eSAIS to also construct the LCP array while suffix sorting, which yields the first implementation of fully external memory suffix and LCP array construction in the literature. Our experiments demonstrate that eSAIS is a factor two faster than DC3, the previously best external memory suffix sorting implementation. After our initial publication of eSAIS, many authors showed interest in the topic and we review their contributions and improvements over eSAIS.

For scaling to even larger inputs, we then consider suffix sorting on a distributed cluster machine. To harness the computational power of a such a system in a convenient data-flow style functional programming paradigm, we propose the new high-performance distributed big data processing framework Thrill. Thrill's central concept is a distributed immutable array (DIA), which is a virtual array of C++ objects distributed onto the cluster. Such arrays can be manipulated using a small set of scalable primitives, such as mapping, reducing, and sorting. These are implemented using pipelined distributed external memory algorithms encapsulated as C++ template classes, which can be efficiently coupled to form large complex applications. Our Thrill prototype is evaluated using five micro benchmarks against the popular frameworks Apache Spark and Flink on up to 16 hosts in the AWS Elastic Compute Cloud. Thrill consistently outperforms the other frameworks in all benchmarks and on all numbers of hosts.

Using Thrill we then implement five suffix sorting algorithms as a case study. Three are based on prefix doubling and two are variants of the linear-time difference cover algorithm DC. The implementation of these complex algorithms demonstrates the expressiveness of the scalable primitives provided by Thrill. They also are the first distributed external memory suffix sorters presented in the literature. We compare them experimentally against two hand-coded MPI implementations and the fastest non-distributed sequential suffix sorters. Our results show that algorithms implemented using Thrill are competitive to MPI programs, but scale to larger inputs due to automatic usage of external memory. In the future, these implementations can benefit from improvements of Thrill such as fault tolerance or specialized sorting algorithms.

Die vorliegende Dissertation behandelt zwei grundlegende Sortierprobleme: Sortieren von Zeichenketten und Sortieren aller Suffixe eines Texts. Der erste Teil betrachtet paralleles Sortieren von Zeichenketten auf Mehrkernrechnern mit gemeinsam genutztem Speicher, der zweite Teil ein neues Verfahren zum Sortieren von Suffixen im Externspeicher und der dritte Teil Sortieren von Suffixen auf verteilen Parallelrechnersysteme mit dem neuen algorithmischen Framework Thrill.

Das Sortieren von Zeichenketten oder Vektoren unterschiedet sich von Sortieren von Zahlen durch die zusätzliche Komponentenstruktur der Schlüssel, die systematisch ausgenutzt werden muss um teure Operationen auf den ganzen Objekten zu vermeiden. Wir betrachten dabei Eingaben die in den gemeinsamen Speicher einer modernen Mehrkernmaschine passen. Große Mengen von Zeichenketten werden beispielsweise sortiert bei der Konstruktion von Datenbankindices, beim Sortieren von Suffixen, oder um hochdimensionale geometrische Daten anzuordnen.

Als vorbereitende Arbeit für den Entwurf von parallelen Sortieralgorithmen für Zeichenketten diskutieren wir zuerst hochentwickelte Varianten der bestehenden sequentiellen Basisalgorithmen und führen eine umfangreiche experimentelle Auswertung dieser durch. Darüber hinaus berichten wir von einer quantitativen Untersuchung der parallelen Speicherbandbreiten und -latenz in modernen Mehrkernsystemen.

Mit dem Wissen aus dieser Vorarbeit entwickeln wir als ersten Algorithmus String Sample Sort, der eine Anpassung von Samplesort für Zeichenketten ist und präsentieren dessen optimierte Version Super Scalar String Sample Sort. Dieser neue Algorithmus ist leicht zu parallelisieren, benötigt O(D / w + n log n) erwartete Zeit, nutzt die Cache-Hierarchie effektiv, verwendet Parallelität auf Wort- und Anweisungsebene und vermeidet teure Fehlvorhersagen von Verzweigungen. Seine Parallelisierung namens Parallel Super Scalar String Sort (pS⁵) verwendet ein freiwilliges Lastbalanceverfahren und ist in unseren Experimenten der insgesamt leistungsfähigste Algorithmus für Mehrkernrechner mit einem Sockel.

Für Plattformen mit non-uniform memory access (NUMA) entwerfen wir einen Hybridansatz, in dem zuerst pS⁵ auf jedem NUMA-Knoten unabhängig voneinander ausgeführt wird und dann gemeinsam die vorsortierten Zeichenkettenfolgen zusammen gemischt werden. Um die Zusammenführung durch ein Array der längsten gemeinsamen Präfixe (LCP) zu beschleunigen, präsentieren wir einen neuen LCP-beschleunigten Mehrwege-Mischalgorithmus (multiway merge), der auf einem Turnierbaum basiert. Der Mischalgorithmus wird darüber hinaus auch verwendet, um einen eigenständigen LCP-beschleunigten K-Wege-Mischsortieralgorithmus (multiway mergesort) zu entwerfen. Dieser läuft in O(D + n log n + n/K) Zeit und profitiert von langen gemeinsamen Präfixen in der Eingabe.

Kurz gesagt, schlagen wir sowohl Sortieralgorithmen auf Basis von Mehrwege-Verteilen mit String Sample Sort als auch von Mehrwege-Mischen mit LCP-beschleunigten Merge und Mergesort vor und optimieren und parallelisieren beide Ansätze. Darüber hinaus entwickeln wir auch Parallelisierungen von Multikey Quicksort und Radix Sort und führen eine umfangreiche experimentelle Analyse auf sechs Maschinen und sieben Eingaben durch. Auf allen Instanzen, außer zufälligen Zeichenketten und URLs, erreicht pS⁵ höhere Geschwindigkeiten auf modernen Mehrkernrechnern mit einem Sockel als unsere Multikey-Quicksort- und Radix-Sort-Parallelisierungen, die bereits besser sind als alle bestehenden Verfahren. Auf Mehrsockel-NUMA-Rechnern war der Hybridansatz bestehend aus pS⁵ und LCP-beschleunigten Mehrwege-Mischen auf den meisten Instanzen am schnellsten.

Danach konzentrieren wir uns auf das Sortieren der Suffixe eines Text, welches auch Suffix-Array-Konstruktion genannt wird. Das Suffix-Array ist eines der beliebtesten Textindizes und dient zur Beschleunigung des Suchen nach Teilzeichenfolgen in DNA- oder Textkorpora, wird in Kompressionsverfahren verwendet werden und ist die Grundlage für viele komplexe String-Algorithmen. Wenn das Suffix-Array um das LCP-Array und weitere zusätzliche Tabellen ergänzt wird, kann diese Kombination den Suffix-Tree in einer Vielzahl von String-Algorithmen ersetzen. Unser Ziel sind schnelle und skalierbare Suffix-Sortieralgorithmen, um große Suffix-Arrays für reale Eingaben zu generieren. Als Einführung präsentieren wir zunächst einen kurzen Überblick über die Prinzipien und Geschichte von Suffix-Sortieralgorithmen.

Unser erster Beitrag zu diesem Gebiet ist eSAIS, der erste Suffix-Sortieralgorithmus für Externspeicher, der das induzierte Sortierprinzip (induced sorting) verwendet. Seine zentrale Schleife ist eine elegante Neuformulierung dieses Prinzips mittels einer Prioritätswarteschlange für Externspeicher. Unsere theoretische Analyse zeigt, dass eSAIS höchstens Sort(17 n) + Scan(9 n) I/O-Volumen erfordert. eSAIS wird daraufhin um die gleichzeitige Konstruktion des LCP-Array während der Suffix-Sortierung erweitert. Dies ergibt die erste Implementierung eines vollständig externen Suffix- und LCP-Array-Konstruktionsalgorithmus in der Literatur. Unsere Experimente zeigen, dass eSAIS um einen Faktor zwei schneller ist als DC3, dem bisher besten Suffix-Sortierverfahren für Externspeicher. Nach unserer ersten Veröffentlichung von eSAIS zeigten viele weitere Autoren Interesse an dem Thema, und wir besprechen ihre Beiträge und Verbesserungen.

Um die Verfahren auf noch größere Eingaben zu skalieren, betrachten wir dann Suffix-Sortierverfahren für verteilten Parallelrechnersysteme. Hierzu präsentieren wir zuerst das neue verteilte Big-Data-Framework Thrill, mit dessen Hilfe komplexe Algorithmen für solch hochleistungsfähige Systeme leichter entworfen und programmiert werden können. Das zentrale Konzept von Thrill ist ein verteiltes unveränderbares Array (DIA), das nahezu beliebige C++ Objekte enthalten kann und transparent auf dem Cluster verteilt liegt. Es ist jedoch kein direkter Zugriff möglich. Statt dessen können DIAs nur mittels eines kleinen Satzes von skalierbaren Primitiven wie Map, Reduce und Sort manipuliert werden. Diese werden als verteilt-externe Basisalgorithmen implementiert und in C++ template Klassen gekapselt. Die Basisalgorithmen können mit anwendungsspezifischen Funktoren parametrisiert und effizient zu größeren Anwendungen gekoppelt werden. Unser Thrill-Prototyp wird anhand von fünf Mikro-Benchmarks mit den populären Frameworks Apache Spark und Apache Flink auf bis zu 16 Maschinen in der AWS Elastic Compute Cloud evaluiert. Thrill ist schneller als die anderen Frameworks in allen Benchmarks und für jede Anzahl von Maschinen.

Als Fallstudie implementieren wir dann fünf Suffix-Sortieralgorithmen mit Thrill. Drei basieren auf Präfixverdopplung und zwei sind Varianten des linearen difference cover Algorithmus DC. Die Implementierung dieser komplexen Algorithmen demonstriert die Ausdruckskraft der von Thrill bereitgestellten skalierbaren Primitiven. Darüber hinaus sind sie die ersten verteilten externen Suffix-Sortierer, die in der Literatur vorgestellt werden. Wir vergleichen sie experimentell mit zwei von Hand erstellten MPI-Implementierungen und mit den schnellsten nicht verteilten sequentiellen Suffix-Sortierern. Unsere Ergebnisse zeigen, dass mit Thrill implementierte Algorithmen mit MPI-Programmen konkurrieren können und dass sie aufgrund der automatischen Verwendung von externem Speicher auf größere Eingaben skalieren. Darüber hinaus können diese Implementierungen von zukünftigen Verbesserungen in Thrill so wie Fehlertoleranz oder spezialisierten Sortieralgorithmen profitieren.