Parallel Quicksort

Parallel Quicksort beschreibt Parallelisierungen des sequentiellen Algorithmus Quicksort, welcher auf dem Teile-und-Herrsche-Prinzip basiert.

Wie Quicksort teilt Parallel Quicksort eine Menge von Elementen mithilfe eines Pivotelements in zwei Teilmengen auf, sodass die Elemente in der einen Teilmenge kleiner als das Pivot sind und die Elemente in der anderen Teilmenge größer oder gleich dem Pivot sind. Danach werden die neuen Mengen wieder jeweils in Teilmengen unterteilt.

Dieses Vorgehen kann auf verschiedene Arten parallel implementiert werden. Zum einen können mehrere Mengen von jeweils einem Prozess in neue Teilmengen aufgeteilt werden. Dies hat den Nachteil, dass der erste Rekursionslevel nicht parallelisiert ist und der Speedup gegenüber Quicksort auf $O(\log n)$ begrenzt ist. Zum anderen können mehrere Prozesse zusammen arbeiten und gemeinsam eine einzelne Menge aufteilen. Dieser Ansatz hat sich in der Praxis als effizienter erwiesen. Parallel Quicksort kann im PRAM Modell mit einer Laufzeit von $O((n/p+\log p+\log \log n)\log n)$ implementiert werden.

Naiver Ansatz

Arbeitsweise

Partitionierung von einem Array mit $n$ Elementen und Pivotelement $k_{i}$. Nach der Verarbeitung der Elemente mit Index $(1,n)$, werden die zwei Untermengen $(1,k_{1}-1)$ und $(k_{1}+1,n)$ gebildet und das Pivotelement an der Stelle $k_{1}$ platziert. Danach wird jede davon in zwei neue Untermengen aufgeteilt und weiter partitioniert.

Bei jedem rekursiven Aufruf von Quicksort wird die Menge der Elemente wiederholt in zwei aufgeteilt. Die erste Partitionierung kann nur von einem einzigen Prozessor durchgeführt werden. Alle weiter erzeugte Untermengen des Arrays, die auf der gleichen Stufe der Rekursion sind, können von zwei weitere Prozessoren parallel ohne Speicherkonflikte verarbeitet werden. Die Zuweisung von den Untermengen an den verschiedenen Prozessoren hat einen zusätzlichen Overhead. Wenn die zwei Mengen klein genug sind oder weniger Prozessoren zur Verfügung stehen, ist es manchmal effizienter einen sequenziellen Sortieralgorithmus anzuwenden, anstatt einen neuen rekursiven Aufruf von Quicksort zu machen.

Es ist dabei möglich, dass manche Prozessoren schneller mit der Partitionierung seiner Untermenge fertig sind, im Vergleich zu anderen. Eine Warteschlange kann dazu benutzt werden, wo die Zeiger auf noch nicht partitionierte Untermengen gespeichert werden. Bei der Entfernung von der Warteschlange sind die größeren Untermengen bevorzugt, da diese neue kleinere Untermengen erzeugen, die wiederum in die Warteschlange kommen. Das Ziel dabei ist, möglichst viele Untermengen zu haben, und dabei die Prozessoren dauerhaft besetzt zu halten.

Allokation von Prozessoren bei der Ausführung von Parallel Quicksort

Allokation von Prozessoren

Die Reihenfolge bei der Allokation von Prozessoren an Untermengen wird dynamisch angepasst. Prozessor 1 partitioniert die Menge der Elemente mit Index $(1,n)$. Die erste entstandene Untermenge, $(1,k_{1}-1)$, verarbeitet wieder Prozessor 1 und die zweite, $(k_{1}+1,n)$, Prozessor 2. Die Menge der Elemente $(k_{1}+1,n)$ ist o. B. d. A. die kleinere von beiden. Daher ist es plausibler, dass diese von Prozessor 2 schneller partitioniert wird. Prozessor 2 fordert also früher als Prozessor 1 für seine Untermengen einen neuen Prozessor an. Infolgedessen verarbeitet Prozessor 2 die eine erhaltene Untermenge, während Prozessor 3 die andere. Wenn Prozessor 1 einen neuen Prozessor anfordert, bekommt er Prozessor 4, weil dieser zurzeit frei ist.

Das folgende Pseudocode skizziert eine Implementierung von Parallel Quicksort. $M$ bezeichnet die maximale Größe des Array, welcher effizienter mit einem sequentiellen Sortieralgorithmus, z. B. Insertionsort, zu sortieren ist.

PROCEDURE QUICKSORT (L,U);
IF U-L > M THEN;
BEGIN
    PARTITION (L,U)
    FORK L1, L2
L1: QUICKSORT (L,K-1)
    GOTO L3
L2: QUICKSORT (K+1,U)
    GOTO L3
L3: JOIN L1, L2
END
ELSE IF U-L > 1 THEN INSERTION_SORT (L,U)

Laufzeit

Dieser Ansatz erreicht eine niedrigere Beschleunigung gegenüber dem sequentiellen Quicksort.

Um eine $n$-elementige Menge mit einem Pivotelement aus der gleichen Menge zu partitionieren, braucht man $n-1$ Vergleiche. Es sei angenommen, dass ein Vergleich eine Zeiteinheit braucht. Weiterhin, sei die ursprüngliche Größe des Arrays $n=2^{k}-1$, die Anzahl an Prozessoren $p=2^{m}$ mit $m<k$ und das ausgewählte Pivotelement immer der wahre Median von der zu partitionierenden Untermenge.

Unter diesen Annahmen kann die Anzahl der Vergleiche des sequentiellen Algorithmus durch die folgende Rekurrenzrelation bestimmt werden:

$T(n)={\begin{cases}n-1+2T{\frac {n-1}{2}},&{\text{falls }}n=7,15,31,...\\2,&{\text{falls }}n=3\end{cases}}$

mit Lösung:

$T(n)=(n+1)\log {n+1}-2n$

Die Laufzeit von Parallel Quicksort kann als die Summe der Laufzeiten von zwei Abschnitten bestimmt werden.

In dem ersten Abschnitt gibt es mindestens so viele Prozessoren wie Untermengen, die zu partitionieren sind. Für die erste Partitionierung wird von alle $p$ Prozessoren, die zur Verfügung stehen, nur einen genutzt. Die $p-1$ weiteren Prozessoren bleiben inaktiv. Diese Iteration braucht $n-1$ Zeiteinheiten, um $n-1$ Vergleiche durchzuführen. Bei der zweiten Partitionierung sind nur zwei Prozessoren aktiv und $p-2$ warten. Wenn $p\geq 2$, werden ${\frac {(n-1)}{2}}-1$ Zeiteinheiten für $n-3$ Vergleiche benötigt. Die dritte Partitionierung braucht analog bei $p\geq 4$ mindestens ${\frac {[(n-1)/2-1]}{2}}-1$ Zeiteinheiten für $n-7$ Vergleiche. Bei der ersten $\log {p}$ Iteration gibt es genug Prozessoren für jede Partition. Die Laufzeit für diesen Zeitabschnitt kann durch die folgende Formel ausgedrückt werden:

$T_{1}(n)=2(n+1)(1-{\frac {1}{p}})-\log {p}$

Die Anzahl der Vergleiche beträgt:

$C_{1}=(n+1)\log {p}-2(p-1)$

In dem zweiten Abschnitt gibt es mehr Untermengen als Prozessoren verfügbar. Wenn es angenommen wird, dass jeder Prozessor gleichviele Vergleiche durchführt, ist die Laufzeit die Anzahl der Vergleiche dividiert durch $p$. Daher folgt:

$C_{2}(n)=T(n)-C_{1}(n)$

$T_{2}(n)={\frac {C_{2}(n)}{p}}$

Die erwartete Beschleunigung beträgt:

${\text{Beschleunigung}}={\frac {T(n)}{T_{1}(n)+T_{2}(n)}}$.

Die beste Beschleunigung bei z. B. $n=1023$ und $p=8$ ist ca. $3.375$, welche niedrig ist. Das Problem ist, dass am Anfang nur wenige Prozessoren aktiv sind und es eine Menge Zeit dauert, bis alle Prozessoren Arbeit bekommen.

Parallelisierung von Quicksort auf EREW PRAM

Im Jahr 1991, stellen Zhang und Nageswara eine Möglichkeit für die Parallelisierung von Quicksort auf einer EREW PRAM vor. Der Algorithmus sortiert $n$ Elemente mit $p$ Prozessoren in $O((n/p+\log p)\log n)$ erwartete Laufzeit und in $O((n/p+\log p+\log \log n)\log n)$ deterministische Laufzeit mit $O(n)$ an Speicherbedarf. In dem Fall, dass $p=O(n/\log n)$ ist, dann sind die Kosten optimal in Bezug auf das Produkt von der Zeit und Anzahl von Prozessoren.

Arbeitsweise

Der Algorithmus wird in drei Schritten ausgeführt. Erstens wird die ursprüngliche Menge $S$ von $n$ Elementen in $p$ Blöcken aufgeteilt, sodass jeder Block $\lceil n/p\rceil$ Elemente hat, außer der letzte, welcher weniger als $\lceil n/p\rceil$ Elemente haben kann. Jedem Prozessor wird einen Block zugewiesen, d. h. Prozessor $i$ verarbeitet Block $i$. Ein Pivotelement $a$ wird auswählt und jedem Prozessor mit einem Parallel Broadcasting herausgeschickt.

In dem zweiten Schritt markiert jeder Prozessor alle Elemente aus seinem Block mit entweder 0 oder 1, abhängig davon, ob das Element kleiner oder größer als das Pivotelement $a$ ist. Mit einem parallelen Präfix Algorithmus kann der Rank von jedem Element innerhalb der Gruppe 0 bzw. Gruppe 1 berechnet werden. Die Idee ist, alle Elemente aus allen Blöcken, die mit "0" markiert wurden, vor alle "1"-Elemente aller Blöcken in einem weiteren Array $B$ zu speichern. Der Index vom Element in $B$ wird anhand seines Ranks und der Nummer seines Blocks berechnet. So hat man alle Elemente aus der ursprünglichen Menge $S$ in zwei Teile aufgeteilt – die Menge $S_{1}$ mit allen "0"-Elementen und $S_{2}$ mit allen "1"-Elementen.

Der dritte Schritt besteht aus der Überprüfung der Länge von $S_{1}$ und $S_{2}$ und wenn diese mehr als ein Element enthalten, folgt ein rekursiver Aufruf von Schritt eins auf beide.

Wahl des Pivotelements und Laufzeitberechnung

Nur ein zusätzliches Array $B$ mit Länge $n$ und konstanten Bedarf an weiteren Hilfsvariablen werden benötigt. Bei dem Rekursionsaufruf kann das ursprüngliche Array $A$ wiederverwendet werden und beim nächsten Aufruf andersrum. Daher bleibt der zusätzliche Speicherbedarf in $O(n)$.

Die Laufzeit von dem Algorithmus hängt von der Wahl des Pivotelements. Eine Möglichkeit ist, ein zufälliges Element als Pivot zu nehmen.

Annehmend, kann ein Prozessor eine zufällige ganze Zahl $k$ von dem Bereich $\{1,2,..,n\}$ in konstante Zeit generieren, dann entspricht die Partitionierung mit Pivotelement – das Element mit Index $k$, einem Random Binary Search. Die Analyse besagt, dass für die Höhe, $H_{n}$, von einem Random-Binary-Search-Tree mit $n$ Elementen, gilt $\lim _{n\to \infty }(H_{n}\ln n)=4.31107...$. Daher liegt die Tiefe der Rekursion bei $O(\log n)$. Das Pivotelement muss zusätzlich noch verschickt werden. Dies erfolgt in $O(\log p)$. Jeder Prozessor muss dann die Elemente in seinem Block markieren, die Präfix Summe muss berechnet werden und die Elemente verschoben werden. Dies braucht gesamt $O(n/p+\log p)$. Anschließend berechnet man die Gesamtlaufzeit für diesen Fall, diese ist $O((n/p)+\log p)\log n)$ erwartet.

In dem Fall, dass das Pivotelement nicht zufällig gewählt wurde, hängt die Laufzeit des Algorithmus von der Rekursionstiefe und damit auch von dem Verhältnis der Größen $S_{1}$ und $S_{2}$ ab. Die Rekursionstiefe vom Algorithmus kann auf $O(\log n)$ begrenzt werden, wenn $S_{1}$ und $S_{2}$ ungefähr gleich sind. Dies kann gewährleistet werden, indem die Auswahl des Pivotelements mit dem Parallel Median Finding Algorithm von Akl auf eine EREW PRAM in $O(\log \log n)$ Zeit erfolgt. Das Markieren, die Präfix Summe und das Verschieben der Elemente erfolgt analog zu dem anderen Fall. Mit dem Brent-Verfahren kann folglich der Algorithmus in $O((n/p+\log p+\log \log n)\log n)$ deterministisch implementiert werden.

Implementierung von Quicksort in MCSTL

Eine parallele Implementierung für Quicksort ist in der MCSTL Bibliothek zu finden. Die zwei Funktionen $parallel\_sort\_qsb$ und $parallel\_sort\_qs$ stehen zur Verfügung. Der Hauptunterschied bei $parallel\_sort\_qs$ liegt bei der durch Work stealing realisierten balancierten Lastverteilung. Bei beiden Funktionen ist die Pivotwahl von einem Prozessor und die Partitionierung parallel von mehreren Prozessoren durchgeführt. Die gewünschte Anzahl von Threads, die benutzt werden müssen, wird als Parameter an dem Algorithmus gegeben.

Arbeitsweise

Zuerst wird das Pivotelement gewählt. Dieses ist der Median mehrerer Elementen aus dem Array. Die Partitionierungsphase fängt mit der Aufteilung der Elemente in kleinere Gruppen, auch Chunks genannt, an. Anschließend erhält jeder Thread zwei Chunks zur Verarbeitung. Existieren nicht genügend Chunks um diese Bedingung zu erfüllen, werden weniger Threads als angefordert benutzt. Jeder Thread sortiert seine Elemente, sodass in seinem linken Chunk nur Elemente kleiner als das Pivotelement liegen bzw. nur größere im rechten. Dann reserviert jeder Thread parallel Platz für seine zwei Chunks. Die linken Chunks jedes Threads werden an den Anfang dieses Arrays geschrieben, die rechten Chunks am Ende. Damit ist die Partitionierung beendet.

Balancierte Lastverteilung

In dem ersten Schritt arbeiten alle Prozessoren gemeinsam an der Partitionierung des Arrays. Den zwei erhaltenen partitionierten Teilmengen wird jeweils die Hälfte aller Prozessoren zugewiesen. Im Laufe des Algorithmus wird es zu dem Punkt kommen, in dem jeder Prozessor eine Teilmenge mit mehreren Elementen zu bearbeiten hat. Es kann sein, dass diese Teilmengen verschiedene Längen haben und unterschiedlich lang bearbeitet werden. Infolgedessen haben manche Prozessoren ihre Teilmengen schon partitioniert, während andere noch nicht damit fertig sind. Dabei entsteht Inaktivität von Prozessoren. Die Lösung in $MCSTL$ besteht aus Prozessor-lokalen Warteschlangen. Wenn ein Prozessor zwei Untermengen nach einer Partitionierung bekommt, dann macht er mit der Partitionierung der größeren weiter, während die kleinere in seine Warteschlange eingefügt wird. Falls die Warteschlange eines Prozessors leer wird, kann dieser Arbeit von der Warteschlange der anderen Prozessoren entnehmen.