3. Paralleles Sortieren

Ein klassisches algorithmisches Problem ist das Sortieren. Im Zusammenhang von parallelen Algorithem ist dies sogar noch zentraler, weil viele weitere parallele Algorithmen das Sortieren als Baustein verwenden. Beim Sortieren betrachten wir eine geordnete Menge $(\mathcal{U},⪯)$, das Universum. Eingabe ist ein (noch nicht sortiertes) Array aus Elementen aus diesem Universum. Ein typisches Universum wäre zum Beispiel die Menge aller Strings, oder spezifischer aller Strings bestehend aus lateinischen Buchstaben. Das Array könnte dann z.B. die englischen Wörter der Länge 2 beinhalten. Wie bei sequentiellen Algorithmen können wir Vergleichsoperationen $$\begin{array}{r}x\stackrel{?}{⪯}y,\end{array}$$ durchführen und nehmen auch an, dass dies in einem Schritt geh.

Sortiernetzwerke

Wir kehren zeitweise zurück zu unserer Schaltkreis-Metapher. Ein Gate ist hier nun kein logisches Gate, sondern ein Vergleichs-Gate. Eingaben sind zwei Elemente $x,y$ aus unserem geordneten Universum und ausgaben sind $min(x,y)$ und $max(x,y)$:

In Kapitel 3.1 werden wir Batchers Merge- und Sortiernetzwerk kennenlernen, also ein Schaltkreis, bestehend aus Vergleichs-Gates, der seine Inputs sortiert. Es besteht aus $O(n{\log }^{2}n)$ Gates und hat Tiefe $O({\log }^{2}n)$. Dies wirft die Frage auf, ob man in $O(\log n)$ Zeit und $O(n\log n)$ Arbeit sortieren kann. Die Antwort lautet ja: das Paper An $O(n\log n)$ Sorting Network von Ajtai, Komlós und Szemerédi konstruiert ein Sortiernetzwerk von Tiefe $O(\log n)$. Allerdings ist die Konstruktion recht kompliziert und die $O$-Notation versteckt eine gigantische Konstante. Daher werden wir diese Konstruktion nicht näher betrachten.

Parallele Sortieralgorithemn

Jedes Sortiernetzwerk kann auf einer CREW PRAM implementiert werden (z.B. können wir jedem Gate einen Prozessor zuordnen). Andersum allerdings nicht unbedingt. In einem allgemeinen CREW-PRAM-Algorithmus kann ein Prozessor zum Beispiel $x$ mit $y_1,\dots ,y_k$ vergleich, und zählen, wie oft $y_i\prec x$ herauskam und aus dieser Zahl eine Adresse berechnen, in die er dann $x$ kopiert. Ein Sortiernetzwerk kann so etwas nicht tun. Wir werden verschiedene parallele Algorithmen kennenlernen, die von dem sequentiellen Algorithmus Mergesort inspiriert sind.

Vergleichsoperationen und andere Operationen

Wenn wir sequentielle Sortieralgorithmen untersuchen, dann geben wir statt deren Laufzeitkomplexität gerne an, wie viele Vergleichsoperationen sie im Worst Case / Expected Case vornehmen. So tätigt Selectionsort in jedem Fall $\mathrm{\Theta }(n^2)$ Operationen (TI 1, Kapitel 2.3) Mergesort im Worst Case $n{\log }_{2}n+O(n)$ Operationen (TI 1, Kapitel 2.4); Quicksort tätigt im Schnitt $2n\ln n+O(n)$ (TI 1, Kapitel 2.6). Bei sequentiellen Algorithmen ist der Fokus auf Vergleichsoperationen einigermaßen gerechtfertigt (aber auch nicht der Weisheit letzter Schluss; so ist Quicksort oft schneller als Mergesort, obwohl er mehr Vergleichsoperationen tätigt). Bei parallelen Algorithmen ist das nicht ganz so. In Kapitel 3.3 lernen wir einen Algorithmus von Leslie Valiant für $\mathrm{m}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}(A,B)$ kennen, der $O(\log \log n)$ Zeitschritte braucht, wenn man nur Vergleichsoperationen zählt; zählt man alle Operationen, so stellt sich seine Laufzeit als das weniger beeindruckende $O(\log n)$ heraus.

Als krönenden Abschluss lernen wir in Kapitel 3.4 Coles parallelen Mergesort-Algorithmus kennen. Dieser erreicht den "heiligen Gral", nämlich ein Array in $O(\log n)$ Zeit und mit $n$ Prozessoren zu sortieren. Darüberhinaus kann der Algorithmus sogar für EREW PRAMs angepasst werden (also exclusive read, exclusive write), in welcher pro Zeitschritt jede Zelle nur von einem Prozessor gelesen werden kann. Diese Anpassung werden wir hier aber nicht besprechen.

Literatur

• M. Ajtai, J. Komlós, E. Szemerédi, An $O(n\log n)$ sorting network. In STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing, Page 1-9.
• Richard Cole, Parallel merge sort. In SIAM Journal on Computing, Volume 17, Number 4 (1988).
• Torben Hagerup, A pictorial description of Cole's parallel merge sort. In Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, pages 143-157.
• Leslie G. Valiant, Parallelism in comparison problems. In SIAM Journal on Computing, Volume 4, Issue 3 (1975).