\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\rank}{\textnormal{rank}} \newcommand{\merge}{\textnormal{merge}} \)

Leslie Valiant fand 1975 eine trickreiche Methode, zwei Arrays der Länge $n$ mit in $O(\log \log n)$ zu mergen. Der Algorithmus ist rekursiv und verwendet folgendes Lemma als Grundbaustein:

Lemma Sei $B$ ein sortiertes Arrays mit $|B| = n$ und $x$ gegeben. Dann können wir $\rank(x, B)$ mit $n$ Prozessoren in $O(1)$ Schritten berechnen.

Beweis von . Wir nehmen an, dass alle Listenelemente verschieden sind, und auch dass $x \not \in B$. Wir haben $n+1$ Prozessoren $P_0, P_1, \dots, P_n$. Prozessor $P_{j}$ überprüft, ob

\begin{align} B[j] \lt x_i \lt B[j+1] \label{ineq-where-is-x} \end{align}

gilt, wobei wir $B[0] = -\infty$ und $B[n+1]=\infty$ setzen. Falls es gilt, weiß $P_{j}$, dass $\rank(x, B) = j$ ist und schreibt diesen Wert in die Ergebniszelle. Da es immer genau ein $j$ gibt, das (\ref{ineq-where-is-x}) erfüllt, entstehen keine Schreibkonflikte. \(\square\)

Sei nun $A$ und B sortiertes Arrays aus $m$ bzw. $n$ Elementen. Wir nehmen an, dass alle Elemente in $A \circ B$ verschieden sind. Um nun $\merge(A,B)$ zu berechnen, wählen wir jedes $\sqrt{m}$-te Element aus $A$ und jedes $\sqrt{n}$-te Element aus $B$ aus

und speichern sie in einem Array:

\begin{align*} A' & := \left[ A[i \cdot \sqrt{m}] \ | \ 1 \leq i \leq \sqrt{m}-1 \right] \\ B' & := \left[ B[j \cdot \sqrt{n}] \ | \ 1 \leq j \leq \sqrt{n}-1 \right] \ . \end{align*}

Mittels bestimmen wir mit $|A'| \cdot |B'| = \sqrt{mn}$ Prozessoren in $O(1)$ Zeit den Rang $\rank(A'[i], B')$ für jedes $1 \leq i \leq \sqrt{m}-1$. Für bestimmtes $i$ bezeichnen wir diesen Rang mit $j$. Es gilt also

\begin{align*} B[j \sqrt{n}] \lt A[i\sqrt{m}] \lt B[ (j+1) \sqrt{n}] \ . \end{align*}

Bildlich gesprochen heißt dass, wir wissen, in welches "Teilstück" von $B'$ das Element $x=A[i\sqrt{m}]$gehört.

In einem nächsten Schritt bestimmen wir, wieder mit Hilfe von , den Rang von $x = A[\sqrt{i}]$ in "seinem Interval" $B[ j \sqrt{n}+1, \dots, (j+1)\sqrt{n}-1 ]$. Wir tun dies parallel für jedes $1 \leq i \leq \sqrt{m}-1$ und brauchen dafür wieder $\sqrt{mn}$ Prozessoren und $O(1)$ Zeit. Mit $O(\sqrt{mn})$ Prozessoren und $O(1)$ Zeit haben wir also folgendes berechnet:

Wir kennen also $\rank(x, B)$ für jedes $x \in A'$. So können wir $B$ in $\sqrt{m}$ Teilarrays $B_1, B_2, \dots, B_{\sqrt{m}}$ zerlegen und $A$ ebenso in $A_1, A_2, \dots, A_{\sqrt{m}}$, so dass

\begin{align*} A_i, B_i \leq A[i\sqrt{m}] \lt A_{i+1}, B_{i+1} \end{align*}

gilt. Mit der Schreibweise $U \lt x$ für eine Liste $U$ meinen wir, dass $z \lt x$ für jedes $z \in U$ gilt. Wir können nun also

\begin{align} \merge(A,B) = \merge(A_1, B_1) \circ \merge(A_2, B_2)\circ \dots \circ \merge(A_{\sqrt{m}-1}, B_{\sqrt{m}-1}) \circ \merge(A_{\sqrt{m}}, B_{\sqrt{m}}) \label{merge-recursive} \end{align}

wobei jedes $\merge(A_i, B_i)$ rekursiv gelöst wird.

Zeitkomplexität

Anfangs haben unsere Listen $A$ und $B$ die Längen $m$ und $n$. Nach einem Rekursionsschritt haben wir $\sqrt{m}$ Teilprobleme $(A_i, B_i)$ mit $|A_i| = \sqrt{m}$. Die Länge der "linken" Liste schrumpft also in $O(1)$ Zeitschritten von $m$ auf $\sqrt{m}$. Nach einem weiteren Rekursionsschritt haben die linken Listen Länge $\sqrt{\sqrt{m}}$ und ganz allgemein nach $t$ Rekursionsebenen Länge $\sqrt[2^t]{m}$. Für jedes Teilproblem $\merge(A',B')$ gehen wir davon aus, dass uns $\sqrt{|A'|\cdot |B'|}$ Prozessoren zur Verfügung stehen. Nach $T := \log \log m$ Ebenen haben wir Listen der Länge \begin{align*} m^{2^{-T}} = m^{2^{- \log \log m}} = m^{\frac{1}{\log m}} = \left(2^{\log m}\right)^{\frac{1}{\log m}} = 2 \end{align*}

erreicht. Das verbleibende Problem $\merge (A', B')$ für $|A'|\leq 2$ können wir mit $\sqrt{|A'|\cdot |B'|}$ Prozessoren in $O(1)$ Schritten berechnen. Insgesamt benötigen wir also $O(T) = O(\log \log m)$ Schritte, um $\merge(A,B)$ zu berechnen.

Anzahl der Prozessoren

Um die rechte Seite von (\ref{merge-recursive}) zu berechnen, müssen wir $\merge(A_i, B_i)$ für jedes $1 \leq i \leq \sqrt{m}-1$ berechnen. Dies tun wir rekursiv. Dafür statten wir das Teilproblem $\merge(A_i, B_i)$ mit $\sqrt{|A_i|\cdot|B_i|}$ Prozessoren aus. Sei $m_i := A_i$ und $n_i := B_i$. Wir wissen, dass $m_i = \sqrt{m}$ (bis eventuell auf das letzte Array); $n_i$ allerdings kann bis zu $n$ Elemente erhalten; wir wissen nur, dass $\sum n_i = n$ ist. Wir können daher die benötigte Anzahl an Prozessoren mit der Cauchy-Schwarz-Ungleichung abschätzen:

\begin{align} \sum_{i=1}^{\sqrt{m}-1} \sqrt{m_i n_i} \leq \sqrt{\sum_i m_i} \sqrt{\sum_i n_i} = \sqrt{mn} \ . \label{ineq-cauchy-schwarz} \end{align}

Wenn $A$ und $B$ anfangs also jeweiles $n$ Elemente haben, so können wir mit $n$ Prozessoren verfahren und diese dann auch auf die Teilprobleme aufteilen - wir haben für jedes Teilproblem ausreichend viele Prozessoren.

Was wir unterschlagen haben

Die obige Laufzeitanalyse unterschlägt zwei Dinge: im Basisfall der Rekursion, also $\merge(A,B)$ mit $|A|\leq 2$, also $A = [a_1, a_2]$ und $|B|=n$, können wir mit $O(\sqrt{n})$ Prozessoren in $O(1)$ Schritten zwar $\rank(a_1,B)$ und $\rank(a_2,B)$ berechnen. Wie aber führen wir dann das $\merge$ tatsächlich durch? Wir haben ja nur $O(\sqrt{n})$ Prozessoren, und um $a_1$ und $a_2$ in die Liste $B$ einzufühgen, müssen wir im Allgemeinen $\Omega(n)$ Elemente verschieben. Dies können wir nicht leisten.

Ein zweites Problem: die Ungleichung (\ref{ineq-cauchy-schwarz}) sagt uns zwar, dass wir unsere $\sqrt{mn}$ hinreichend viele sind, um jedes Teilproblem adäquat auszustatten, sagt uns aber nicht, welcher Prozessor auf welchem Teilproblem arbeiten muss. Betrachten wir den $l$-ten unserer $\sqrt{mn}$ Prozessoren für $\merge(A,B)$. Soll er zugeordnet werden? Für die ersten $k$ Teilprobleme benötigen wir

\begin{align} p_{k} := \sum_{i=1}^{k} \sqrt{m_i n_i} \label{pk-prefix-sum} \end{align}

Prozessoren. Prozessoren $1, \dots, p_1$ arbeiten also an $\merge(A_1, B_1)$; Prozessoren $p_1 + 1, \dots, p_2$ an $\merge(A_2, B_2)$ und so weiter. Der Haken hierbei: bei (\ref{pk-prefix-sum}) handelt es sich um eine Präfixsumme. Und um die zu berechnen bräuchten wir selbst wieder Zeit $O(\log n)$, wie wir in Kapitel 2.3 gelernt haben.

Valiant erkennt dieses Problem und unterscheidet zwischen Schritten, in denen tatsächlich Elemente aus der zu sortierenden Menge verglichen werden und "Overhead" und erwähnt, dass wachsender Overhead die Effizienzgewinne wieder zunichte macht. Auf der einen Seite ist das unbefriedigend, weil wir ja alle Berechnungsschritte zählen wollen, nicht nur die, in denen ein Vergleich ausgeführt wird; andererseits ist es vielleicht ganz interessant, zu untersuchen, was man alles machen kann, wenn man nur Vergleichsoperationen zählt.

Maximum in $O(\log \log n)$ parallelel Vergleichsschritten

Lassen wir uns also auf Valiants Gedankenexperiment ein, nur Schritte zu zählen, in denen wirklich Vergleichsoperationen durchgeführt werden. Wir nennen solche Schritte parallele Vergleichsschritte. Alle anderen Operationen, also Ergebnisse addieren, kopieren betrachten wir als kostenlos.

Theorem Mit $n$ Prozessoren kann man in einem Array von $n$ Elementen in $O(\log \log n)$ parallelen Vergleichsschritten das Maximum bestimmen.

Dies ist also deutlich schneller als der traditionelle binärbaumartige Algorithmus, der so vorgeht wie in der K.o.-Runde einer Weltmeisterschaft und $O(\log n)$ Schritte braucht.

Beweis. Kern der Idee ist, dass wir das Maximum von $l$ Elementen mit ${l \choose 2}$ Prozessoren in einem Schritt bestimmen können. Hierfür stellen wir uns einen vollständigen Graphen auf $l$ Knoten vor und ordnen jeder Kante $\{u,v\}$ einen Prozessor $P_{uv}$ zu.

Dieser führt nun folgende Schritte aus:

  1. Vergleiche $u$ und $v$.
  2. Markiere den Knoten $\min(u,v)$ rot.
  3. Kopiere den nicht-roten Knoten in die Zelle für das Ergebnis.

Punkt 2 führt natürlich zu Schreib-Schreib-Konflikten: im obigen Fall zum Beispiel wollen $P_{uv}$ und $P_{xu}$ beide den Knoten $u$ rot markieren, also in seine Speicherzelle schreiben. Wenn wir nun aber Zeitschritte ignorieren, indem keine Vergleichsoperationen auf den Eingabeoperation stattfinden, dann können wir die Konflikte auflösen, indem die ${l \choose 2}$ Prozessoren einfach nacheinander schreiben. Das benötigt ${l \choose 2}$ Runden, die aber in dem jetzigen Modell nicht zählen. Nach Schritt 2 sind nun $l-1$ der $l$ Knoten rot markiert, nur das Maximum (oben: der Knoten $x$) nicht. Also schreiben in Punkt 3 alle Prozessoren diesen Wert in die Ergebniss-Zelle. Die hier auftretenden Konflikte können wir wie oben lösen oder auch gar nicht erst einstehen lassen, indem wir zum Beispiel die ersten $l$ der ${l \choose 2}$ Prozessoren den Knoten zuordnen und derjenige, dessen Knoten nicht markiert ist, ihn in die Ergebnis-Zelle kopiert.

Wir beginnen nun mit $n$ Elementen und teilen diese in Gruppen der Größe 3:

Mit obigem Argument können wir in einem Zeitschritt pro Dreieck das Maximum bestimmen. Danach gibt es nur noch $n/3$ Elemente, die in Frage kommen. Es ist kein Problem, diese in ein vorgefertigtes Array der Größe $n/3$ zu kopieren. Nun müssen wir also auf einem Array der Größe $n/3$ das Maximum bestimmen und haben dafür $n$ Prozessoren zur Verfügung. Wir können also größere Gruppen als Dreiecke bilden:

Nach zwei Schritten verbleiben also $n/21$ mögliche Kandidaten für das Maximum. Wie groß sollen wir die Gruppen jetzt bilden? Verallgemeinern wir. Wir haben $n$ Prozessoren und $n/k$ Elemente (im Moment $k=21$; anfangs $k=1$). Wenn wir die $n/k$ Elemente in $\frac{n}{kl}$ Blöcke von je $l$ Elementen unterteilen und in jedem Block alle ${l \choose 2}$ paarweisen Vergleiche ausführen, dann sind das

\begin{align*} {l \choose 2} \cdot \frac{n}{kl} = \frac{l-1}{2k} \cdot n \end{align*}

Vergleichsoperationen. Für $l := 2k+1$ sind das $n$ Operationen, und wir können sie alle parallel mit unseren $n$ Prozessoren ausführen. Wir haben also nach einem Vergleichsschritt genug Information, um in jedem Block das Maximum zu bestimmen. Es verbleiben pro Block ein Kandidat, insgesamt also $\frac{n}{k (2k+1)}$ viele. Wir fahren fort, nun mit $k' := k(2k+1)$. Wie groß ist also die Menge der verbleibenden Kandidaten nach $i$ Vergleichsschritten? Wir definieren

\begin{align*} k_0 & := 1\\ k_{i+1} & := k_i \cdot (2k_i + 1) \end{align*}

Dann verbleiben nach $i$ Schritten nur noch $n / k_i$ Kandidaten. Wenn $n / k_i = O(1)$ erreicht ist (z.B. $n/k_i \leq 2$), dann ermitteln das Maximum in $O(1)$ verbleibenden Vergleichsschritten. Um uns die Rechnung zu erleichtern, definieren wir

\begin{align*} l_0 & := 2 \\ l_{i+1} & := l_i^2 \end{align*}

Per Induktion sieht man, das $k_i \geq l_i$ für alle $i \geq 2$ gilt und außerdem $l_i = 2^{2^i}$. Es verbleiben nach $i \geq 2$ Schritten also

\begin{align*} \frac{n}{k_i} \leq \frac{n}{l_i} = \frac{n}{2^{2^i}} \end{align*}

Kandidaten. Nach $T = \log \log n$ Schritten verbleibt noch $\frac{n}{2^{2^T}} = 1$ Kandidat und wir sind fertig (bzw. wir sind schon vor $T$ fertig, weil die Zahl der Kandidaten schon zuvor $1$ erreicht haben wird). \(\square\)

Übungsaufgabe Wir sind stillschweigend davon ausgegangen, dass man die $n/k$ Elemente in $\frac{n}{kl}$ Blöcke der Größe $l$ aufteilen kann. Das geht natürlich nur, wenn $\frac{n}{k}$ durch $l$ teilbar ist (und selbst eine natürliche Zahl ist). Passen Sie die Analyse so an, dass Sie diesen Teilbarkeitsschwierigkeiten Rechnung tragen.