Samplesort

Samplesort i​st ein Sortieralgorithmus, d​er 1970 v​on W. D. Frazer u​nd A. C. McKellar i​n der wissenschaftlichen Publikation Samplesort: A Sampling Approach t​o Minimal Storage Tree Sorting veröffentlicht wurde. Der Algorithmus arbeitet ähnlich w​ie Quicksort u​nd verfolgt w​ie dieser d​as Teile-und-herrsche-Verfahren. Der Algorithmus t​eilt die Eingabesequenz i​n mehrere Teilsequenzen auf, d​ie dann rekursiv sortiert werden.

Pseudocode

Der folgende Pseudocode stellt die Arbeitsweise des Algorithmus grundlegend dar.[1] Dabei enthält ${\displaystyle A}$ die zu sortierenden Daten, ${\displaystyle k}$ entspricht dem Oversamplingfaktor und ${\displaystyle p}$ der Anzahl der zu nutzenden Splitter. Die Anzahl der Splitter gibt an, in wie viele Teilsequenzen die Eingabedaten aufgeteilt werden (für ${\displaystyle p=2}$ entspricht der Algorithmus Quicksort), während sich durch einen großen Oversamplingfaktor die Größen der Buckets statistisch gesehen weniger unterscheiden.

${\displaystyle {\text{sampleSort}}(A[1..n],k,p)}$
  ${\displaystyle {\text{if }}n/k<{\text{ threshold then smallSort}}(A)}$ // if average bucket size is below a threshold switch to e.g. quicksort
  ${\displaystyle {\text{select }}S=[S_{1},\dots ,S_{p(k-1)}]{\text{ randomly from }}A}$ // select samples
  ${\displaystyle {\text{sort }}S}$ // sort sample
  ${\displaystyle [s_{0},s_{1},\dots ,s_{p-1},s_{p}]\leftarrow [-\infty ,S_{k},S_{2k},\dots ,S_{(p-1)k},\infty ]}$ // select splitters
  // classify elements
  ${\displaystyle {\text{for each }}a\in A}$
    ${\displaystyle {\text{find }}j{\text{ such that }}s_{j-1}<a\leq s_{j}}$
    ${\displaystyle {\text{place }}a{\text{ in bucket }}b_{j}}$
  ${\displaystyle {\text{return concatenate}}({\text{sampleSort}}(b_{1}),\dots ,{\text{sampleSort}}(b_{k}))}$

Die Wahl des richtigen Buckets in der Schleife kann für jedes Element mit binärer Suche in Zeit ${\displaystyle {\mathcal {O}}(\log p)}$ ausgeführt werden.

Der angegebene Pseudocode unterscheidet s​ich von d​er von Frazer u​nd McKellar beschriebenen Ursprungsform.[2] Im Pseudocode w​ird Samplesort rekursiv aufgerufen, u​m die erzeugten kleineren Teilmengen z​u sortieren. Frazer u​nd McKellar verwendeten dafür Quicksort, d. h. d​ie Funktion Samplesort w​ird nur einmal aufgerufen.

Die Anzahl Vergleiche, die dieser Algorithmus durchführt, nähert sich für große Eingabesequenzen asymptotisch dem informationstheoretischen Optimum ${\displaystyle \log _{2}(n!)}$ an und brauchte in den von Frazer und McKellar durchgeführten Experimenten mehr als 15 % weniger Vergleiche als Quicksort.

Oversampling

Der Oversamplingfaktor gibt an, wie groß die Stichprobe zur Auswahl der Splitter größer ist, als die Anzahl der Splitter. Ziel ist es, die Verteilung der Eingabedaten möglichst gut anzunähern. Nach der Klassifikation enthält im Idealfall jeder Bucket genau ${\displaystyle n/p}$ Elemente, um die folgende Arbeit des Algorithmus gleichmäßig auf die Buckets aufzuteilen.

Nach der Wahl des Samples ${\displaystyle S}$ der Größe ${\displaystyle p\cdot (k-1)}$ wird das Sample sortiert. Als Splitter, die als Bucketgrenzen verwendet werden, werden die Elemente in ${\displaystyle S}$ an den Stellen ${\displaystyle k,2k,3k,\dots ,(p-1)k}$ sowie ${\displaystyle -\infty }$ und ${\displaystyle \infty }$ als linke und rechte Grenzen des linkesten und rechtesten Buckets verwendet.

Größe der Buckets

Mit der Größe des Samples bzw. dem Oversamplingfaktor kann die erwartete Bucketgröße und insbesondere die Wahrscheinlichkeit dafür, dass ein Bucket eine gewisse Größe überschreitet, abgeschätzt werden. Für einen Oversamplingfaktor ${\displaystyle k\in \Theta ({\frac {\log n}{\epsilon ^{2}}})}$ werden wir zeigen, dass mit einer Wahrscheinlichkeit von weniger als ${\displaystyle 1/n}$ ein Bucket mehr als ${\displaystyle (1+\epsilon )n/p}$ Elemente enthält.

Sei dafür ${\displaystyle [e_{1},\dots ,e_{n}]}$ die Eingabe bereits in sortierter Form. Damit ein Prozessor mehr als ${\displaystyle (1+\epsilon )n/p}$ Elemente erhält, muss es eine Sequenz der Eingabe der Länge ${\displaystyle (1+\epsilon )n/p}$ geben, aus der maximal ${\displaystyle k}$ Elemente für das Sample gewählt werden. Das wird wie folgt als Zufallsvariable dargestellt:

${\displaystyle X_{i}:={\begin{cases}1,&{\text{falls }}s_{i}\in [e_{j},\dots ,e_{j}+(1+\epsilon )n/p]\\0,&{\text{sonst}}\end{cases}}}$

${\displaystyle X:=\sum _{i=0}^{k\cdot p-1}X_{i}}$

Daraus folgt:

${\displaystyle \mathbb {E} [X_{i}]=\mathbb {P} [X_{i}=1]={\frac {1+\epsilon }{p}}}$

${\displaystyle \mathbb {P} [X<k]\approx \mathbb {P} [X<(1-\epsilon ^{2})k]=\mathbb {P} [X<(1-\epsilon )\mathbb {E} [X]]}$

Dabei bezeichnet ${\displaystyle \mathbb {P} [X<k]}$ die Wahrscheinlichkeit, dass weniger als ${\displaystyle k}$ Samples im Bucket ${\displaystyle j}$ liegen. Mithilfe der Chernoff-Ungleichung sieht man, dass

${\displaystyle n\mathbb {P} [X<k]\leq n\exp({\frac {\epsilon ^{2}k}{2}})\leq n{\frac {1}{n^{2}}}}$ für ${\displaystyle k\geq {\frac {4}{\epsilon ^{2}}}\ln n}$

Samplesort auf Systemen mit verteiltem Speicher

Arbeitsprinzip von parallelem Samplesort für ${\displaystyle p=3}$ Prozessoren und einem Oversamplingfaktor ${\displaystyle k=3}$.

Samplesort wird oft in parallelen Systemen mit verteiltem Speicher verwendet[3][4][5][6], da es durch die variable Anzahl von Buckets im Gegensatz zum Beispiel zu Quicksort einfach an eine beliebige Anzahl Prozessoren angepasst werden kann. Die Eingabedaten liegen dabei verteilt auf ${\displaystyle p}$ Prozessoren vor, das heißt, jeder Prozessor hat ${\displaystyle n/p}$ Elemente gespeichert. Entsprechend werden ebenso viele Splitter ausgewählt, um für jeden Prozessor einen Bucket zu erzeugen.

Um die Splitter auszuwählen, ist es ausreichend, wenn jeder Prozessor aus seinen Eingabeelementen ${\displaystyle k}$ Elemente auswählt. Diese werden mit einem verteilten Sortieralgorithmus sortiert und an alle Prozessoren verteilt. Es entstehen Kosten von ${\displaystyle T_{\text{sort}}(kp,p)}$ für das Sortieren der ${\displaystyle kp}$ Elemente auf ${\displaystyle p}$ Prozessoren, sowie ${\displaystyle T_{\text{allgather}}(p,p)}$ für das Verteilen der ${\displaystyle p}$ gewählten Splitter auf ${\displaystyle p}$ Prozessoren.

Mit den erhaltenen Splittern partitioniert jeder Prozessor die eigenen Eingabedaten in lokale Buckets. Die Zeit dafür beträgt mit binärer Suche ${\displaystyle {\mathcal {O}}(n/p\log p)}$. Anschließend verteilen die Prozessoren die Buckets an die jeweiligen Prozessoren mit Zeit ${\displaystyle T_{\text{all-to-all}}(N,p)}$, wobei ${\displaystyle N}$ der Größe des größten Buckets entspricht. Prozessor ${\displaystyle i}$ enthält entsprechend von allen Prozessoren die lokalen Buckets ${\displaystyle b_{i}}$ und sortiert diese lokal. Der Zeitbedarf für die lokale Sortierung von allen Prozessoren beträgt ${\displaystyle T_{\text{localsort}}(N)}$.

Wählt man wie im vorherigen Abschnitt beschrieben ${\displaystyle k\in \Theta ({\frac {\log n}{\epsilon ^{2}}})}$, so erhält man eine Gesamtlaufzeit von

${\displaystyle T(n,p)=T_{\text{sort}}({\mathcal {O}}({\frac {p\log n}{\epsilon ^{2}}}),p)+T_{\text{allgather}}(p,p)+{\mathcal {O}}(n/p\log p)+T_{\text{all-to-all}}((1+\epsilon )n/p,p)+T_{\text{localsort}}((1+\epsilon )n/p)}$

Effiziente Implementierung von sequentiellem Samplesort

Arbeitsprinzip von Super Scalar Sample Sort. (Animation) In jedem Schritt werden Zahlen, die verglichen werden, blau eingefärbt und Zahlen, auf die anderweitig lesend oder schreibend zugegriffen wird, werden rot eingefärbt.

Wie oben beschrieben klassifiziert der Algorithmus die Elemente anhand der gewählten Splitter und partitioniert diese entsprechend. Eine effiziente Implementierung wird im Paper Super Scalar Sample Sort[1] beschrieben. Dort werden zwei Arrays der Größe ${\displaystyle n}$ genutzt: ein Array für die Eingabedaten, sowie ein temporäres Array. Entsprechend arbeitet Samplesort in diesem Fall nicht in-place. In jedem Rekurssionsschritt werden die Daten von einem zum anderen Array kopiert und währenddessen partitioniert. Falls die Daten nach dem letzten Rekursionsschritt im temporären Array vorliegen, so werden diese in das originale Array zurückkopiert. Die wesentlichen Schritte sind die Klassifikation der Elemente anhand der Splitter und die anschließende Partitionierung. Beides wird im Folgenden genauer erklärt.

Klassifikation der Elemente

In einem vergleichsbasierten Sortieralgorithmus ist der performancekritische Teil die Klassifikation der Elemente, d. h. die Zuordnung von Elementen zu Buckets. Diese Zuordnung benötigt ${\displaystyle {\mathcal {O}}(\log p)}$ Schritte pro Element. Super Scalar Sample Sort nutzt einen balancierten Suchbaum, der implizit in einem Array ${\displaystyle t}$ gespeichert ist. Das heißt, die Wurzel befindet sich an Stelle 0, und der linke Nachfolger eines Elementes ${\displaystyle t_{i}}$ befindet sich in ${\displaystyle t_{2i}}$, der rechte Nachfolger in ${\displaystyle t_{2i+1}}$. Bei einem gegebenen Suchbaum ${\displaystyle t}$ und einem Element ${\displaystyle a}$ berechnet der Algorithmus den Index des entsprechenden Buckets ${\displaystyle j}$ wie folgt (der Ausdruck ${\displaystyle a>t_{j}}$ sei 1 falls ${\displaystyle a>t_{j}}$ und 0 andernfalls, ${\displaystyle p}$ sei eine Zweierpotenz):

${\displaystyle j\leftarrow 1}$
${\displaystyle {\text{repeat}}\log _{2}p{\text{ times}}}$
  ${\displaystyle j\leftarrow 2j+(a>t_{j})}$
${\displaystyle j\leftarrow j-p+1}$

Da die Anzahl der Buckets ${\displaystyle p}$ bei der Übersetzungszeit bekannt ist, kann die Schleife vom Compiler ausgerollt werden. Falls die Prozessorarchitektur es unterstützt, kann in der Schleife ganz auf bedingte Sprünge verzichtet werden und es treten keine fehlerhaften Sprungvorhersagen auf.

Partitionierung

Zum effizienten Partitionieren muss der Algorithmus die Größen der Buckets vor dem Kopieren der Elemente kennen. In einer naiven Implementierung könnten alle Elemente klassifiziert werden, um die Bucketgrößen zu bestimmen. Anschließend könnten die Elemente an die richtige Stelle kopiert werden. So müsste der Bucket für jedes Element zweimal bestimmt werden (einmal für das Zählen der Elemente der Buckets und einmal zum Kopieren). Super Scalar Sample Sort vermeidet diese doppelte Klassifikation, indem das Ergebnis der Klassifikation in einem zusätzlichen Array ${\displaystyle o}$ (dem „Orakel“) zwischengespeichert werden. Dieses ordnet jedem Element ${\displaystyle a_{i}}$ den Bucketindex ${\displaystyle o_{i}}$ zu. Zuerst bestimmt Super Scalar Sample Sort die richtigen Werte von ${\displaystyle o}$, indem jedes Element klassifiziert wird. Danach werden die Größen der Buckets bestimmt und jedes Element anhand von ${\displaystyle o}$ an die richtige Stelle kopiert. Der Speicherbedarf von Array ${\displaystyle o}$ beträgt ${\displaystyle n\log p}$ bits, was im Vergleich zu den Eingabedaten nur wenig Speicher bedeutet.

Paralleler in-place-Samplesort für Systeme mit gemeinsamem Speicher

Die oben gezeigte Samplesort-Implementierung arbeitet nicht in-place, da ein zweites Array der Größe ${\displaystyle n}$ benötigt wird. Effiziente Implementierungen von z. B. Quicksort arbeiten in-place und benötigen daher weniger Speicher. Samplesort kann allerdings auch in-place für parallele Systeme mit gemeinsamem Speicher implementiert werden.[7] Im Folgenden wird eine solche Implementierung beschrieben. Zu beachten ist, dass der zusätzliche Speicherplatz des Algorithmus immer noch von ${\displaystyle n}$ abhängt, im Gegensatz zum oben erklärten Super Scalar Sample Sort aber nur ${\displaystyle {\mathcal {o}}(n)}$ zusätzlichen Speicherplatz benötigt. Eine modifizierte Variante des Algorithmus, der nur noch Speicherplatz unabhängig von ${\displaystyle n}$ benötigt, ist ebenfalls in[7] beschrieben.

Der in-place Algorithmus k​ann in v​ier Phasen aufgeteilt werden:

1. Sampling: Auswahl der Splitter.
2. Lokale Klassifikation: Gruppieren der Eingabe in Blöcke, so dass alle Elemente eines Blockes zu einem Bucket gehören (allerdings muss nicht jeder Bucket zusammenhängend im Speicher liegen).
3. Blockpermutation: Vertauschen der Blöcke, so dass diese global in der richtigen Reihenfolge liegen.
4. Aufräumen: Kopieren der übrigen Elemente an die Kanten der Buckets.

Da d​urch diesen Algorithmus j​edes Element zweimal gelesen u​nd geschrieben werden m​uss (einmal b​ei der Klassifikation u​nd einmal während d​er Blockpermutation) ergibt s​ich ein höherer Schreib- u​nd Leseaufwand. Trotzdem i​st der Algorithmus b​is zu dreimal schneller a​ls aktuelle in-place Wettbewerber u​nd bis z​u 1,5 m​al schneller a​ls andere aktuelle sequentielle Wettbewerber, einschließlich d​es oben beschrieben Super Scalar Sample Sort. Da d​as Sampling u​nd die Auswahl d​er Splitter bereits o​ben (Pseudocode) beschrieben ist, folgen a​n dieser Stelle n​ur noch d​ie detaillierten Erklärungen d​er drei anderen Phasen.

Lokale Klassifikation

Das Eingabearray wird zuerst in ${\displaystyle t}$ (Anzahl der Prozessoren/Threads) Bereiche gleicher Größe aufgeteilt. Jeder Prozessor enthält einen solchen Bereich und teilt diesen weiter auf in Blöcke, die jeweils ${\displaystyle b}$ Elemente enthalten. Zusätzlich allokiert jeder Prozessor ${\displaystyle p}$ (Anzahl Buckets) Puffer, die ebenfalls ${\displaystyle b}$ Elemente speichern können. Jeder Prozessor verarbeitet anschließend seinen zugewiesenen Bereich und kopiert die Elemente in die entsprechenden allokierten Puffer. Falls ein Puffer voll ist, wird dessen Inhalt in den vom Prozessor verarbeiteten Bereich kopiert. Die dortigen ${\displaystyle b}$ Elemente, die dadurch überschrieben werden, sind bereits verarbeitet, da ansonsten kein Puffer voll sein könnte. Zur Auswahl der richtigen Buckets/Puffer siehe Klassifikation der Elemente. Nach dieser Phase enthält jeder Bereich mehrere Blöcke mit Elementen jeweils eines Buckets und darauffolgend leere Blöcke. Die übrigen Elemente sind noch in den Pufferblöcken. Zusätzlich speichert jeder Prozessor die Größe jedes Buckets.

Blockpermutation

In dieser Phase werden d​ie Blöcke i​m Eingabearray i​n die richtige Reihenfolge gebracht. Mithilfe e​iner Präfixsumme über d​ie Größe d​er Buckets werden d​eren Grenzen bestimmt. Da i​n dieser Phase n​ur ganze Blöcke verschoben werden, werden d​ie Grenzen a​uf ganze Blöcke aufgerundet. Die fehlenden Elemente befinden s​ich noch i​n den Pufferblöcken. Da d​ie Größe d​es Eingabearrays n​icht zwangsläufig d​urch die Blockgröße teilbar ist, müssen einige Elemente d​es letzten (nicht vollständigen) Blockes i​n einen Überlaufpuffer verschoben werden.

Bevor mit der Blockpermutation begonnen wird, müssen eventuell einige leere Blöcke an das Ende ihres Buckets verschoben werden. Anschließend wird für jeden Bucket ${\displaystyle b_{i}}$ ein Schreibpointer ${\displaystyle w_{i}}$ angelegt, der auf den Beginn der Buckets zeigt und ein Lesepointer ${\displaystyle r_{i}}$, der auf den letzten nichtleeren Block im Bucket ${\displaystyle b_{i}}$ zeigt.

Um gegenseitige Blockierungen der Prozessoren zu vermeiden, verarbeitet jeder Prozessor anfangs einen eigenen (primären) Bucket ${\displaystyle b_{\text{prim}}}$. Außerdem erhält jeder Prozessor zwei Tauschpuffer, die jeweils genau einen Block speichern können. Falls beide Tauschpuffer leer sind, wird der Block an Stelle von ${\displaystyle r_{\text{prim}}}$ in einen der Tauschpuffer platziert. Durch Klassifikation des ersten Elements im Puffer wird der Zielbucket ${\displaystyle b_{\text{dest}}}$ dieses Blocks bestimmt und an Stelle ${\displaystyle w_{\text{dest}}}$ kopiert. Um zu verhindern, dass ein dortiger Block überschrieben wird, muss dieser vorher in einen freien Tauschpuffer kopiert werden. Mit diesem Block im Tauschpuffer wird dann analog verfahren. Die Pointer ${\displaystyle r_{\text{prim}}}$ und ${\displaystyle w_{\text{dest}}}$ werden entsprechend angepasst.

Sind a​lle Blöcke d​es primären Buckets a​n der richtigen Stelle, werden d​ie Blöcke d​es nächsten Buckets weiterverarbeitet, b​is alle Blöcke i​hren Zielbucket erreicht haben. Danach e​ndet diese Phase.

Aufräumen

Da n​ur ganze Blöcke i​n der Blockpermutationsphase verschoben wurden, können einige Elemente n​och an Stelle außerhalb i​hres Buckets liegen. Da e​s für a​lle Elemente n​och genug Platz i​m ursprünglichen Array gibt, können d​ie verbleibenden Elemente a​us den Puffern a​n die freien Plätze kopiert werden. Zuletzt w​ird der Inhalt d​es Überlaufpuffers kopiert.

Literatur

• W. D. Frazer, A. C. McKellar: Samplesort: A Sampling Approach to Minimal Storage Tree Sorting. In: Journal of the ACM. Band 17, Nr. 3, Juli 1970, ISSN 0004-5411, S. 496–507.
• Peter Sanders et al.: Vorlesung Parallele Algorithmen, Karlsruhe 2009, S. 75–80.

Erweiterungen für parallele Berechnungen:

• ohio-state.edu (Memento vom 8. Juni 2011 im Internet Archive) (PDF)
• citeseer.ist.psu.edu
• citeseerx.ist.psu.edu
• Verwendung auf der GPU (PDF; 869 kB)

Einzelnachweise

1. Peter Sanders, Sebastian Winkel: Super Scalar Sample Sort. In: Algorithms – ESA 2004 (= Lecture Notes in Computer Science). Springer, Berlin, Heidelberg, 2004, ISBN 978-3-540-23025-0, S. 784–796, doi:10.1007/978-3-540-30140-0_69.
2. W. D. Frazer, A. C. McKellar: Samplesort: A Sampling Approach to Minimal Storage Tree Sorting. In: Journal of the ACM (JACM). Band 17, Nr. 3, 1. Juli 1970, ISSN 0004-5411, S. 496–507, doi:10.1145/321592.321600 (acm.org [abgerufen am 22. März 2018]).
3. Guy E. Blelloch, Charles E. Leiserson, Bruce M. Maggs, C. Greg Plaxton, Stephen J. Smith: A comparison of sorting algorithms for the connection machine CM-2. ACM, 1991, ISBN 0-89791-438-4, S. 3–16, doi:10.1145/113379.113380 (acm.org [abgerufen am 23. März 2018]).
4. Alexandros V. Gerbessiotis, Leslie G. Valiant: Direct Bulk-Synchronous Parallel Algorithms. In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. Band 22, 1992, S. 22––251 (psu.edu [abgerufen am 1. April 2018]).
5. Jonathan M. D. Hill, Bill McColl, Dan C. Stefanescu, Mark W. Goudreau, Kevin Lang: BSPlib: The BSP Programming Library. 1998 (psu.edu [abgerufen am 1. April 2018]).
6. William L. Hightower, Jan F. Prins, John H. Reif: Implementations of randomized sorting on large parallel machines. ACM, 1992, ISBN 0-89791-483-X, S. 158–167, doi:10.1145/140901.140918 (acm.org [abgerufen am 1. April 2018]).
7. Michael Axtmann, Sascha Witt, Daniel Ferizovic, Peter Sanders: In-Place Parallel Super Scalar Samplesort (IPSSSSo). In: 25th Annual European Symposium on Algorithms (ESA 2017) (= Leibniz International Proceedings in Informatics (LIPIcs)). Band 87. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany 2017, ISBN 978-3-95977-049-1, S. 9:1–9:14, doi:10.4230/LIPIcs.ESA.2017.9 (dagstuhl.de [abgerufen am 30. März 2018]).