ParAlg, Kapitel 6.3

6.3 Der Algorithmus von Goodrich, Sitchinava und Zhang

Zur Wiederholung: wir haben $P$ Maschinen, jede mit einem Speicherplatz $O (S)$ , und $N$ Items. Es gilt $P S \geq c \cdot N$ . Die Items liegen beliebig über die Maschinen verteilt, aber so, dass sie in den Speicher der jeweiligen Maschine passen. Es gelte $S = N^{ϵ}$ für ein $0 < ϵ < 1$ . Der Wert von $ϵ$ is konstant, hängt also nicht von $N$ ab. Wir wollen die Eingabemenge $X$ aus $N$ Items sortieren: am Ende der Berechnung soll für jedes $x \in X$ ein Item $(x, i)$ erzeugt worden sein, mit $i := rank (x, X)$ , und auf einer beliebigen Maschine liegen.

Die naive Quicksort-Implementierung aus dem letzten Teilkapitel benötigt $O (1 / ϵ^{2})$ Runden, was quadratisch mehr ist als unser "Goldstandard" $O (1 / ϵ)$ . Dies erinnert uns an die Situation auf der CREW PRAM: naives Mergesort benötigt $O (\log n^{2})$ Zeit, und es bedurfte eines doch recht komplizierten Algorithmus (Cole's parallel mergesort), um eine Laufzeit von $O (\log n)$ zu erreichen.

Goodrich, Sitchinava und Zhang geben in ihrem Paper einen Sortieralgorithmus, der in insgesamt $O (1 / ϵ)$ Runden läuft.

Übungsaufgabe 6.3.1 (Indexing). Sei $X$ die Menge der $N$ Eingabe-Items. Ziel ist es, eine Ausgabemenge von Items zu berechnen, so dass es

für jedes $x \in X$ genau einen Ausgabe-Item $(x, i)$ mit $1 \leq i \leq N$ gibt; die Zahl $i$ heißt der Index von $x$ ;
jedes $x \in X$ einen anderen Index hat: wenn also $(x, i)$ und $(x^{'}, i^{'})$ in der Ausgabemenge sind und $x \neq x^{'}$ , dann auch $i \neq i^{'}$ .

In anderen Worten: wir wollen eine injektive Funktion $X \to [N]$ berechnen. Hierbei ist muss die Ausgabemenge nicht sortiert sein: der Index $i$ von $(x, i)$ muss eindeutig sein, kann aber ansonsten beliebig in $[N]$ sein. Zeigen Sie, wie man das in $O (1 / ϵ)$ Schritten implementieren kann.

Als Baustein für einen schnelleren Quicksort-Algorithmus entwerfen wir uns einen Algorithmus

Übungsaufgabe 6.3.2 (Alle Paare bilden). Eingabe sind zwei Mengen $X$ und $Y$ mit $| X |, | Y | \leq \sqrt{N}$ . Ziel ist es, als Ausgabemenge das cartesische Produkt $X \times Y$ zu berechnen: jedes Item $(x, y) \in X \times Y$ soll genau auf einer Maschine liegen.

Zeigen Sie, wie man das in $O (1 / ϵ)$ implementieren kann.

Tip: Stellen Sie sich eine $(\sqrt{N} \times \sqrt{N})$ -Matrix vor, bei der die $i$ -te Zeile für $x_{i}$ und die $j$ -te Spalte für $y_{j}$ "zuständig" ist. Bauen Sie Bäume, um $x_{i}$ von links ausgehend zu jeder Zelle in Zeile $i$ zu schicken.

Übungsaufgabe 6.3.3 Zeigen Sie, wie man mit Hilfe der letzten Übung eine Menge $X$ von $\sqrt{N}$ Elementen in $O (1 / ϵ)$ Runden sortieren kann.

Gegeben seien zwei Mengen $X$ und $Y$ , beide mit $| X |, | Y | \leq \sqrt{N}$ . Beschreiben Sie, wie man in $O (1 / ϵ)$ Runden für jedes $x \in X$ den Rang $rank (x, Y)$ berechnen kann. Am Ende der Berechnung soll also für jedes $x \in X$ ein Item $(x, rank (x, Y))$ erzeugt worden sein.

Ab jetzt persönliche Notizen. Noch unausgereift!

Definition 6.3.1 ( $k$ -verzweigter Suchbaum für $Z$ ). Wir konstruieren einen Baum von unten (Blätter) nach oben (Wurzel), in der jeder Knoten $v$ eine Menge $Z_{v} \subseteq Z$ der Größe $k$ enthält.

Der unterste Level, also die Blätter, besteht aus $| X | / k$ Knoten. Wenn $l$ das $i$ -te Blatt ist, dann setzen wir $Z_{l} := {z_{i k}, z_{i k + 1}, \dots, z_{i k + k - 1}}$ .
Solange die oberste Ebene mehr als einen Knoten enthält:
- Fasse die Knoten der obersten Ebene in Blöcke von $k$ Knoten zusammen.
- Für so einen Block $v_{1}, \dots, v_{k}$ erschaffen wir einen gemeinsamen Elternknoten $u$ eine Ebene höher.
- Die Menge $Z_{u}$ besteht aus den $k$ Minima seiner Kinder, also $\begin{array}{r} Z_{u} := {max (Z_{v}) | v ein Kind von u} . \end{array}$

Sofern $k \leq S$ ist, können wir jedem Knoten in dem Baum eine Maschine zuordnen. Wenn $X$ sortiert ist, können wir den Baum effizient in $O (h)$ Runden bauen; $h = \log_{k} | Z |$ ist die Höhe des Baumes.

Unser neues Quicksort wählt nun eine Menge $Z$ von (circa) $\sqrt{N}$ Pivots und sortiert diese so wie in Übungsaufgabe 6.3.3. Sei nun $T$ so ein $k$ -ärer Suchbaum für die Menge $Z$ der Pivots, und sei $h$ seine Höhe. Für ein Eingabeitem $x \in X$ können wir mit Hilfe von $T$ den Rang $rank (x, Z)$ in $O (h)$ Runden bestimmen. Das geht, sofern $k \leq S$ ist, weil ja jeder Knoten $k$ Elemente speichern muss.

Wieviele Items können wir mit so einem Baum parallel verarbeiten? Sei $Q \subseteq X$ eine Menge von Items. Wenn $| Q | \leq S$ ist, können wir $Q$ der Wurzel-Maschine schicken; diese ist damit nicht überlastet. Sie bestimmt dann lokal für jedes $q \in Q$ , in welchem der $k$ Unterbäume weitergesucht werden muss.

Literatur

Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang: Sorting, Searching, and Simulation in the MapReduce Framework. ISAAC 2011, pages 374-383.