Timo Bingmann

Matthias Schimek

Abstract

Although there has been extensive work on sequential and shared-memory parallel string sorting, the problem has not yet been thoroughly studied for distributed systems. In this thesis we present two new distributed string sorting algorithms. Our first algorithm distributed Merge String Sort extends the – to our knowledge – only distributed string sorting algorithm with longest common prefix-related optimizations. Furthermore, we present a new approach to compute an ordered partition of a distributed string array such that the number of characters in each set of the partition has about the same value.

Our second algorithm distributed Prefix-Doubling String Sort addresses a major problem of distributed string sorting: the communication of characters which are not required to establish a lexicographical order of the input. Distributed Bloom filters are applied to approximately compute the distinguishing prefixes of the input without exchanging the actual strings. Afterwards, the algorithm operates on the (approximate) distinguishing prefixes only. By this means, a significant amount of communication can be saved provided that the distinguishing prefixes are short compared to the strings themselves.

Furthermore, we introduce a new string generator producing string data sets with the ratio of the distinguishing prefix length to the entire string length being an input parameter. Our evaluation on up to 1280 processors shows that the presented algorithms clearly outperform their competitors on both generated and real-world data.

Deutsche Zusammenfassung

Obwohl in den letzten Jahren das Sortieren von Zeichenketten sowohl im Sequentiellen als auch auf parallelen Systemen mit gemeinsamen Speicher intensiv untersucht wurde, ist das Problem auf verteilten Systemen ohne gemeinsamen Speicher noch weitgehend unbehandelt. In der vorliegenden Arbeit werden zwei Algorithmen für das verteilte Sortieren von Zeichenketten vorgestellt. Der erste Algorithmus, distributed Merge String Sort, erweitert den einzigen bisher publizierten verteilten Algorithmus zum Sortieren von Zeichenketten um Optimierungen, welche die Eigenschaften längster gemeinsamer Präfixe der Eingabe ausnutzen. Darüberhinaus wird ein neuer Algorithmus zum Berechnen einer geordneten Partition verteilter Zeichenketten präsentiert, welcher sicherstellt, dass die Anzahl an Zeichen in jeder Teilmenge der Partition annähernd identisch ist.

Der zweite Algorithmus, distributed Prefix-Doubling String Sort, geht eines der Hauptprobleme beim Sortieren von Zeichenketten auf verteilten Systemen an, das darin besteht, nur die für das Sortieren der Zeichenketten tatsächlich benötigten Teile derselben zu kommunizieren. Zu diesem Zweck werden verteilte Bloomfilter verwendet, die es erlauben, die für die Sortierung relevanten Präfixe der Zeichenketten approximativ zu berechnen, ohne diese als ganze auszutauschen. Ab diesem Zeitpunkt werden im Algorithmus nur noch Operationen auf den zuvor berechneten Präfixen durchgeführt. Hierdurch kann ein erheblicher Anteil des Kommunikationsvolumens eingespart werden – vorausgesetzt, dass die für die Sortierung relevanten Präfixe im Vergleich

zu den (Gesamt-)Zeichenketten kurz sind. Weiterhin wird ein Zeichenketten-Generator vorgestellt, welcher es erlaubt, Datensätze mit einem vorgegebenen Verhältnis zwischen Länge der für die Sortierung relevanten Präfixe und der Länge der Zeichenketten zu erzeugen. In der  abschließenden Evaluation auf bis zu 1280 Prozessoren wird gezeigt, dass distributed Merge String Sort und distributed Prefix-Doubling
String Sort deutlich bessere Laufzeiten als die Konkurrenzalgorithmen besitzen. Diese werden sowohl auf generierten als auch nicht-künstlichen Datensätzen erreicht.