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^[1]. Dies hat den Nachteil, dass der erste Rekursionslevel nicht parallelisiert ist und der Speedup gegenüber Quicksort auf O ( log ⁡ n ) {\displaystyle 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 ) {\displaystyle O((n/p+\log p+\log \log n)\log n)} implementiert werden^[2].

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 erzeugten Untermengen des Arrays, die auf der gleichen Stufe der Rekursion sind, können von zwei weiteren Prozessoren parallel ohne Speicherkonflikte verarbeitet werden^[1]. Die Zuweisung der Untermengen an die 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, die Zeiger auf noch nicht partitionierte Untermengen zu speichern. 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.

Die Reihenfolge bei der Allokation von Prozessoren an Untermengen wird dynamisch angepasst. Prozessor 1 partitioniert die Menge der Elemente mit Index ( 1 , n ) {\displaystyle (1,n)} . Die erste entstandene Untermenge, ( 1 , k 1 − 1 ) {\displaystyle (1,k_{1}-1)} , verarbeitet wieder Prozessor 1 und die zweite, ( k 1 + 1 , n ) {\displaystyle (k_{1}+1,n)} , Prozessor 2. Die Menge der Elemente ( k 1 + 1 , n ) {\displaystyle (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 {\displaystyle 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)

Dieser Ansatz erreicht eine niedrigere Beschleunigung gegenüber dem sequentiellen Quicksort^[3].

Um eine n {\displaystyle n} -elementige Menge mit einem Pivotelement aus der gleichen Menge zu partitionieren, braucht man n − 1 {\displaystyle 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 {\displaystyle n=2^{k}-1} , die Anzahl an Prozessoren p = 2 m {\displaystyle p=2^{m}} mit m < k {\displaystyle 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 ) = { n − 1 + 2 T n − 1 2 , falls  n = 7 , 15 , 31 , . . . 2 , falls  n = 3 {\displaystyle 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 − 2 n {\displaystyle 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 allen p {\displaystyle p} Prozessoren, die zur Verfügung stehen, nur einer genutzt. Die p − 1 {\displaystyle p-1} weiteren Prozessoren bleiben inaktiv. Diese Iteration braucht n − 1 {\displaystyle n-1} Zeiteinheiten, um n − 1 {\displaystyle n-1} Vergleiche durchzuführen. Bei der zweiten Partitionierung sind nur zwei Prozessoren aktiv und p − 2 {\displaystyle p-2} warten. Wenn p ≥ 2 {\displaystyle p\geq 2} , werden ( n − 1 ) 2 − 1 {\displaystyle {\frac {(n-1)}{2}}-1} Zeiteinheiten für n − 3 {\displaystyle n-3} Vergleiche benötigt. Die dritte Partitionierung braucht analog bei p ≥ 4 {\displaystyle p\geq 4} mindestens [ ( n − 1 ) / 2 − 1 ] 2 − 1 {\displaystyle {\frac {[(n-1)/2-1]}{2}}-1} Zeiteinheiten für n − 7 {\displaystyle n-7} Vergleiche. Bei der ersten log ⁡ p {\displaystyle \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 − 1 p ) − log ⁡ p {\displaystyle 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 ) {\displaystyle 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 gleich viele Vergleiche durchführt, ist die Laufzeit die Anzahl der Vergleiche dividiert durch p {\displaystyle p} . Daher folgt:

C 2 ( n ) = T ( n ) − C 1 ( n ) {\displaystyle C_{2}(n)=T(n)-C_{1}(n)}

T 2 ( n ) = C 2 ( n ) p {\displaystyle T_{2}(n)={\frac {C_{2}(n)}{p}}}

Die erwartete Beschleunigung beträgt:

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

Die beste Beschleunigung bei z. B. n = 1023 {\displaystyle n=1023} und p = 8 {\displaystyle p=8} ist ca. 3.375 {\displaystyle 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.

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

Der Algorithmus wird in drei Schritten ausgeführt. Erstens wird die ursprüngliche Menge S {\displaystyle S} von n {\displaystyle n} Elementen in p {\displaystyle p} Blöcke aufgeteilt, sodass jeder Block ⌈ n / p ⌉ {\displaystyle \lceil n/p\rceil } Elemente hat, außer der letzte, welcher weniger als ⌈ n / p ⌉ {\displaystyle \lceil n/p\rceil } Elemente haben kann. Jedem Prozessor wird ein Block zugewiesen, d. h. Prozessor i {\displaystyle i} verarbeitet Block i {\displaystyle i} . Ein Pivotelement a {\displaystyle 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 {\displaystyle 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 {\displaystyle B} zu speichern. Der Index vom Element in B {\displaystyle B} wird anhand seines Ranks und der Nummer seines Blocks berechnet. So hat man alle Elemente aus der ursprünglichen Menge S {\displaystyle S} in zwei Teile aufgeteilt – die Menge S 1 {\displaystyle S_{1}} mit allen "0"-Elementen und S 2 {\displaystyle S_{2}} mit allen "1"-Elementen.

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

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

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

Annehmend, kann ein Prozessor eine zufällige ganze Zahl k {\displaystyle k} von dem Bereich { 1 , 2 , . . , n } {\displaystyle \{1,2,..,n\}} in konstanter Zeit generieren, dann entspricht die Partitionierung mit Pivotelement – das Element mit Index k {\displaystyle k} , einem Random Binary Search. Die Analyse^[4] besagt, dass für die Höhe, H n {\displaystyle H_{n}} , von einem Random-Binary-Search-Tree mit n {\displaystyle n} Elementen, gilt lim n → ∞ ( H n ln ⁡ n ) = 4.31107... {\displaystyle \lim _{n\to \infty }(H_{n}\ln n)=4.31107...} . Daher liegt die Tiefe der Rekursion bei O ( log ⁡ n ) {\displaystyle O(\log n)} . Das Pivotelement muss zusätzlich noch verschickt werden. Dies erfolgt in O ( log ⁡ p ) {\displaystyle O(\log p)} ^[5]. Jeder Prozessor muss dann die Elemente in seinem Block markieren, die Präfix Summe muss berechnet werden^[6] und die Elemente verschoben werden. Dies braucht gesamt O ( n / p + log ⁡ p ) {\displaystyle O(n/p+\log p)} . Anschließend berechnet man die Gesamtlaufzeit für diesen Fall, diese ist O ( ( n / p ) + log ⁡ p ) log ⁡ n ) {\displaystyle 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 {\displaystyle S_{1}} und S 2 {\displaystyle S_{2}} ab. Die Rekursionstiefe vom Algorithmus kann auf O ( log ⁡ n ) {\displaystyle O(\log n)} begrenzt werden, wenn S 1 {\displaystyle S_{1}} und S 2 {\displaystyle 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 ) {\displaystyle O(\log \log n)} Zeit^[7] 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 ) {\displaystyle O((n/p+\log p+\log \log n)\log n)} deterministisch implementiert werden.

Eine parallele Implementierung für Quicksort ist in der MCSTL Bibliothek^[8] zu finden. Die zwei Funktionen p a r a l l e l _ s o r t _ q s b {\displaystyle parallel\_sort\_qsb} und p a r a l l e l _ s o r t _ q s {\displaystyle parallel\_sort\_qs} stehen zur Verfügung. Der Hauptunterschied bei p a r a l l e l _ s o r t _ q s {\displaystyle 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.

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.

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 M C S T L {\displaystyle 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.

1. ↑ ^{a b} D.J. Evans, R.C Dunbar: The parallel quicksort algorithm part i–run time analysis. In: International Journal of Computer Mathematics. Band 12, Nr. 1, Januar 1982, ISSN 0020-7160, S. 19–55, doi:10.1080/00207168208803323. 
2. ↑ ^{a b} Weixiong Zhang, Nageswara S. V. Rao: Optimal parallel quicksort on EREW PRAM. In: BIT. Band 31, Nr. 1, März 1991, ISSN 0006-3835, S. 69–74, doi:10.1007/bf01952784. 
3. ↑ Quinn, Michael J. (Michael Jay): Instructor's manual to accompany Designing efficient algorithms for parallel computers. McGraw-Hill Book Co, 1987, ISBN 0-07-051072-5. 
4. ↑ Luc Devroye: A note on the height of binary search trees. In: Journal of the ACM. Band 33, Nr. 3, 1. Mai 1986, ISSN 0004-5411, S. 489–498, doi:10.1145/5925.5930. 
5. ↑ Vishkin, U.: Synchronous parallel computation - a survey. Courant Institute of Mathematical Sciences, New York University, April 1983, OCLC 1085604497. 
6. ↑ Richard Cole, Uzi Vishkin: Approximate and exact parallel scheduling with applications to list, tree and graph problems. In: 27th Annual Symposium on Foundations of Computer Science (sfcs 1986). IEEE, 1986, ISBN 0-8186-0740-8, doi:10.1109/sfcs.1986.10. 
7. ↑ Akl, S. G. "Parallel Selection in O(log log n) Time Using O(n/log log n) Processors." Technical Report 88-221, Department of Computing and Information Science, Queen's University, Kingston, Ontario (1988).
8. ↑ Putze, Felix.: MCSTL: the multi-core standard template library. ACM, 2007, OCLC 854741854.