ParAlg, Kapitel 3.4

3.4 Coles paralleler Mergesort-Algorithmus

Dieser Teil ist sehr technisch und wahrscheinlich vorerst nicht Teil der Vorlesung.

Traditioneller paralleler Mergesort

In den vorherigen Kapiteln haben wir Mergesort "wie üblich" durchgeführt und uns darauf konzentriert, eine möglichst effiziente parallele Variante von Merge zu entwerfen. Die Makrostruktur des Algorithmus sah dann - unabhängig von dem Merge-Algorithmus - in etwas so aus:

In jedem Schritt $t$ verteilen sich die $n$ Prozessoren auf die $2^{\log (n) - t}$ Knoten auf Ebene $t$ (Ebene $0$ sind die Blätter), um pro Knoten die zwei von unten kommenden sortierten Listen zu mittels Merge zu einer sortierten List der Länge $2^{t}$ zu verschmelzen.

Versetzen Sie sich in die Lage eines Knotens auf Ebene $t$ . Sie haben in Schritt $t$ eine Menge von $2^{t}$ Prozessoren zur Verfügung. Um auf eine Gesamtlaufzeit von $O (\log n)$ zu kommen, müsste der Merge-Schritt in $O (1)$ Zeit ablaufen. Dies ist leider nicht möglich.

Vorkenntnisse. Für einen Knoten $u$ in dem Binärbaum sei $L_{u}$ die sortierte Liste aller Elemente, die an den Blättern im Teilbaum von $u$ stehen. Für das linkeste Blatt auf Ebene 2 im obigen Beispiel wäre dies [be, it, to, up]. Ziel ist es, $L_{r o o t}$ zu berechnen. Sei $u$ ein Knoten und seien $v$ und $w$ seine Kinder. Coles zentrale Entdeckung ist, dass man zwei Listen $A$ und $B$ dann in $O (1)$ verschmelzen kann, wenn man schon eine grobe Vorstellung hat, wie $A$ und $B$ aussehen. Zum Beispiel wenn man als "Skizze" eine Liste $U$ hat und (1) jedes Element in $U$ seinen Rang in $A$ und in $B$ kennt und (2) die Intervalle, in die $A$ und $B$ durch die Elemente aus $U$ geteilt wird, nur konstante Größe haben. Wir haben nun mehrere Herausforderungen.

Statt wie im obigen Beispiel einfach alle Elemente von Knoten $v$ zum Elternknoten $u$ zu schicken, müssen wir festlegen, wie Knoten $v$ eine Skizze seiner derzeitigen Liste nach $u$ . Jeder Knoten $u$ hat also "vorläufige" Liste $L (u, t)$ zum Zeitpunkt $t$ (die hoffentlich irgendwann wirklich zu $L_{u}$ wird).
Wir müssen die Bedingung (2), also die Teilintervalle haben konstante Größe sehr sorgfältig formulieren, damit wir es als Schleifeninvariante tatsächlich beweisen können.
Wir müssen zeigen, welche Zusatzinformation wir brauchen, damit wir alles Merge-Operationen wirklich in konstanter Zeit erledigen können.

Stichproben weiterschicken

Jeder Knoten $v$ enthält zum Zeitpunkt $t$ eine sortierte Liste $L (v, t)$ aus Elementen. Für einen inneren Knoten $v$ ist $L (v, 0) = []$ . Für ein Blatt $v$ ist $L (v, 0) = [x]$ , enthält also genau ein Element aus unserer zu sortierenden Eingabeliste. So weit alles so wie beim "traditionellen" parallelen Mergesort oben. Wir werden nun eine Choreographie entwickeln, nach der Knoten $v$ auf bestimmten Ebenen Stichproben $S (v, t)$ ihrer derzeitigen Liste $L (v, t)$ nach "oben" zu ihrem jeweiligen Elternknoten $u$ schicken. Wenn also $u$ die Kinder $v$ und $w$ hat, dann gilt

\begin{array}{r} L (u, t + 1) = merge (S (v, t) \cup S (w, t)) \end{array}

Beispiel. Wir beschreiben eine Choreographie, nach der ein Knoten $v$ bestimmt, welche Elemente er zum Zeitpunkt $t$ zu seinem Elternknoten weiterschickt.

Schicke jedes zweite Element nach oben (angefangen bei Element 1). Wenn also $L (u, t) = [x_{1}, x_{2}, \dots, x_{m}]$ ist, dann ist $S (u, t) = [x_{1}, x_{3}, x_{5}, \dots]$ .

Diese Choreographie führt natürlich nie zum Ziel, da zum Beispiel das Element mit Rang 2 nie über Level 1 hinauskommt (und es überhaupt nur das Minimum bis ganz oben schafft). Wir brauchen also eine Choreographie, in der ab irgendeinem Zeitpunkt ein Knoten seine Gesamtliste nach oben weiterleitet.

Beispiel. Wir beschreiben hier eine zweite Choreographie.

Wenn $t \geq 2$ und $L (u, t - 1) = L (u)$ ist, schicke die Gesamtliste weiter: $S (u, t) := L (u, t)$ .
Ansonsten schicke jedes zweite Element von $L (u, t)$ weiter, angefangen beim ersten; formal $S (u, t) := [x \in L (u, t) | rank (x, L (u, t)) ist ungerade]$ .

Die Bedingung $L (u, t - 1) = L (u)$ , dass also die Liste schon vor zwei Schritten vollständig geworden ist, stellen wir graphisch durch Punkte versus Kreuzchen dar: anfangs symbolisieren wir Elemente durch Punkte; wenn zum ersten Mal $L (u, t) = L (u)$ gilt, so werden sie ab Schritt $t + 1$ durch Kreuze dargestellt; wenn $L (v, t)$ aus Kreuzen besteht, schicken wir sie vollständig in Schritt $t + 1$ nach oben weiter.

Die Entwicklung von $| L (u, t) |$ in Abhängigkeit vom Level $i$ des Knotens $u$ und des Zeitschrittes $t$ können wir schön in einer Tabelle darstellen.

Übungsaufgabe 3.4.1 Betrachten Sie die folgende Choreographie:

Wenn $L (u, t - 1)! = []$ , dann setze $S (u, t) = L (u, t)$ , schicke also alle Elemente weiter.
Wenn $L (u, t - 1) = []$ , dann schicke jedes zweite Element weiter.

Jeder Knoten schickt also nur einmal eine nichtleere, aber auch nicht vollständige Stichprobe nach oben weiter. Die zweite Stichprobe ist dann schon die Gesamtliste, der er im Moment hat. Erkunden Sie die Dynamik dieser Choreographie und erstellen Sie eine Tabelle noch obigen Beispiel.

Die Dynamik in unserem zweiten Beispiel (wo wir jedes zweite Element weiterschicken bis $L (u, t - 1) = L (u)$ vollständig geworden ist) schaut recht freundlich aus; leider werden wir weiter unten feststellen, dass sie aus anderen Gründen nicht zu verwenden ist. Wir betrachten daher eine weitere Choreographie, für die der Algorithmus dann funktionieren wird.

Übungsaufgabe 3.4.2 Betrachte folgende Dynamik:

Wenn $t \geq 2$ und $L (u, t - 1) = L (u)$ ist, schicke die Gesamtliste weiter: $S (u, t) := L (u, t)$ .
Ansonsten schicke jedes vierte Element von $L (u, t)$ weiter, angefangen beim ersten; formal $S (u, t) := [x \in L (u, t) | rank (x, L (u, t)) ist ungerade]$ .

Untersuchen Sie die Dynamik dieser Choreographie, indem Sie eine Tabelle nach obigem Beispiel zeichnen.

Grobstruktur des Algorithmus

Wir nehmen an, dass die Länge $n$ der Eingabeliste $[x_{1}, x_{2}, \dots, x_{n}]$ eine Zweiterpotenz ist $n = 2^{d}$ . Wir betrachten einen Binärbaum der Höhe $d$ . Der $i$ -te Level des Baumes besteht aus den Knoten mit Abstand $d - i$ zur Wurzel; Level $0$ sind also die Blätter. Jedes Blatt trägt als Label ein Element der Inputliste. Für einen Knoten $u$ bezeichne $L (u)$ die Liste der Labels der Blätter seines Unterbaumes in sortierter Reihenfolge. Falls $u$ auf Level $i$ ist, so gilt also $| L (u) | = 2^{i}$ ; insbesondere ist $L (root)$ die sortierte Eingabeliste, also das gewünschte Ergebnis. Jeder Knoten $u$ des Baumes unterhält zum Zeitpunkt $t$ eine sortierte Liste $L (u, t)$ . Anfangs setzen wir

\begin{array}{r} L (u, 0) := {\begin{cases} x_{i} & falls u das i -te Blatt des Baumes ist \\ [] & falls u kein Blatt ist. \end{cases} \end{array}

Für eine Liste $L$ sei ${Sample}_{k} (L)$ die Liste bestehend aus jedem $k$ -ten Element, angefangen beim ersten. Formal

\begin{array}{r} {Sample}_{k} (L) := {x \in L | rank (x, L) \equiv 1 \mod k} \end{array}

So ist zum Beispiel

\begin{array}{r} S_{3} ([am, be, he, in, on, to, us]) = [am, in, us] \end{array}

Weiterhin definieren wir folgende Sampling-Choreographie:

\begin{array}{r} S (u, t) := {\begin{cases} S_{4} (L (u, t)) & falls L (u, t - 1) \neq L (u), \\ L (u, t) & sonst. \end{cases} \end{array}

In Worten: ein Knoten auf Level $i$ schickt jedes vierte Element seiner Liste weiter; wenn seine Liste vollständig geworden ist, also eine Länge von $2^{i}$ erreicht hat, dann schickt er noch ein weiteres Mal jedes vierte Element weiter, danach aber seine vollständige Liste. Schlussendlich erwähnen wir noch einmal die Regel, nach der die neue Liste $L (u, t + 1)$ gebildet wird:

\begin{array}{r} L (u, t + 1) = merge (S (v, t) \cup S (w, t)) \end{array}

Dies ist die Grobstruktur von Coles parallelem Mergesort-Algorithmus. Wir müssen nun verstehen, wie die merge-Operation in konstanter Zeit ausgeführt werden kann und wie man dafür die $n$ Prozessoren verteilen muss. Zuvor müssen wir aber noch eine strukturelle Eigenschaft der Listen $L (u, t)$ verstehen.

Dichte Listen

Sei $u$ ein Knoten mit Kindern $v$ und $w$ . Wie oben angekündigt, werden wir sehen, dass $L (u, t)$ bereits ein ganz gutes "Gerüst" für $S (v, t)$ und $S (w, t)$ darstellen und wir daher $merge (S (v, t) \cup S (w, t))$ schnell parallell ausführen können. Wir brauchen hierfür eine recht technische Definition.

Definition 3.4.1 (Rang und Distanz.) Sei $A$ eine Menge und $x \leq y$ Elemente (nicht notwendigerweise in $A$ ). Dann ist

\begin{array}{r} rank (x, A) := | {z \in A | z \leq x} | \end{array}

der Rang von $x$ in $A$ . Weiterhin ist

\begin{array}{r} dist (x, y, A) := rank (y, A) - rank (x, A) = | {z \in A | x < z < y} | . \end{array}

Definition 3.4.2 Seien $r, s \in N$ und $A$ und $B$ Mengen. Die Menge $A$ heißt $(r, s)$ -dicht in $B$ wenn

\begin{array}{r} dist (x, y, B) \leq r + s \cdot dist (x, y, A) \end{array}

gilt, für alle Elemente $x \leq y$ . Falls $r$ und $s$ aus dem Kontext klar sind, schreiben wir einfach $A \overset{dense}{⟶} B$ .

Wir betonen, dass die Elemente $x, y$ in Definition 3.4.2 nicht notwendigerweise in $A$ oder $B$ sein müssen. Die beiden Definitionen funktionieren generell für Mengen und Elemente aus einem geordneten Universum; in unserem Fall wird es sich bei den erwähnten Mengen $A$ und $B$ immer um bereits sortierte Listen handeln (dies spielt für den Dichtheitsbegriff allerdings keine Rolle). Unser Algorithmus berechnet ja $S_{4} (L (u, t))$ . Im Folgenden ist es allerdings vorteilhaft, allgemein für ${Sample}_{k} (L (u, t))$ zu rechnen. Insbesondere gilt

Beobachtung 3.4.3 Es gilt $dist (x, y, U) \leq k - 1 + k \cdot dist (x, y, {Sample}_{k} (U))$ .

Übungsaufgabe 3.4.3 Beweisen Sie die Behauptung.

Lemma 3.4.4 (Schleifeninvariante des Algorithmus). Seien $r$ , $s$ und $k$ so gewählt, dass $r \geq k - 1$ , $s \geq k$ und $r \geq ⌈ \frac{2 r + (k - 1) s}{k} ⌉$ gelten. Dann ist $S (u, t)$ immer $(r, s)$ -dicht in $S (u, t + 1)$ , falls es denn überhaupt nichtleer ist.

Beweis. Falls $L (u, t) = L (u)$ , also bereits vollständig ist, dann gilt $S (u, t + 1) = L (u, t + 1) = L (u)$ . Nun ist $S (u, t)$ entweder selbst $L (u)$ (falls es schon länger vollständig ist), und $L (u)$ ist trivialerweise $(r, s)$ -dicht in sich selbst; oder $S (u, t) = {Sample}_{k} (L (u))$ . In letzterem Fall gilt $dist (x, y, L (u)) \leq k - 1 + k \cdot dist (x, y, {Sample}_{k} (L (u)))$ und somit ist $S (u, t)$ auch $(k - 1, k)$ -dicht in $S (u, t + 1)$ und somit erst recht auch $(r, s)$ -dicht.

Im anderen Falle gilt $L (u, t) \neq L (u)$ , der Knoten $u$ hat also noch nicht seine Gesamtliste kennengelernt. Insbesondere ist $u$ kein Blatt und hat daher zwei Kinder $v$ und $w$ . Es gelten

\begin{aligned} L (u, t) & = S (v, t - 1) \cup S (w, t - 1) \\ S (u, t) & = {Sample}_{k} (S (v, t - 1) \cup S (w, t - 1)) . \end{aligned}

Per Induktion gilt die Schleifeninvariante für $v$ und $w$ zum Zeitpunkt $t - 1$ :

\begin{aligned} S (v, t - 1) & \overset{dense}{⟶} S (v, t) \\ S (w, t - 1) & \overset{dense}{⟶} S (w, t) \end{aligned}

Sei $A := S (v, t - 1)$ , $A^{'} := S (v, t)$ , $B := S (w, t - 1)$ und $B^{'} := S (w, t)$ . Wir wissen also per Schleifeninvariante, dass $A \overset{dense}{⟶} A^{'}$ und $B \overset{dense}{⟶} B^{'}$ . Wir müssen zeigen, dass $S (u, t) \overset{dense}{⟶} S (u, t + 1)$ . Es gilt $L (u, t) = A \cup B$ und $L (u, t + 1) = A^{'} \cup B^{'}$ und somit $S (u, t) = {Sample}_{k} (A \cup B)$ und $S (u, t + 1) = {Sample}_{k} (A^{'} \cup B^{'})$ . Wir müssen also zeigen, dass ${Sample}_{k} (A \cup B) \overset{dense}{⟶} {Sample}_{k} (A^{'} \cup B^{'})$ . Dies wird durch folgende Behauptung garantiert (Lemma 1 in A Pictorial Description of Cole’s Parallel Merge Sort von Torben Hagerup).

Behauptung. Sei $A \overset{dense}{⟶} A^{'}$ und $B \overset{dense}{⟶} B^{'}$ . Dann ist auch ${Sample}_{k} (A \cup B) \overset{dense}{⟶} {Sample}_{k} (A^{'} \cup B^{'})$ .

Beweis. Seien $x \leq y$ zwei Elemente in unserem geordneten Universum. Wir müssen zeigen, dass $dist (x, y, {Sample}_{k} (A^{'} \cup B^{'})) \leq r + s \cdot dist (x, y, {Sample}_{k} (A \cup B))$ gilt. Für jede Liste $U$ gilt $dist (x, y, {Sample}_{k} (U)) \leq ⌈ \frac{dist (x, y, U)}{k} ⌉$ und daher auch

\begin{aligned} (1) & dist (x, y, {Sample}_{k} (A^{'} \cup B^{'})) & \leq ⌈ \frac{dist (x, y, A^{'} \cup B^{'})}{k} ⌉ . \end{aligned}

Wir werden nun $dist (x, y, A^{'} \cup B^{'})$ nach oben abschätzen, wobei wir $A \overset{dense}{⟶} A^{'}$ und $B \overset{dense}{⟶} B^{'}$ verwenden.

\begin{aligned} dist (x, y, A^{'} \cup B^{'}) & = dist (x, y, A^{'}) + dist (x, y, B^{'}) \\ = r + s \cdot dist (x, y, A) + r + s \cdot dist (x, y, B) \\ = 2 r + s \cdot (dist (x, y, A) + dist (x, y, B)) \\ = 2 r + s \cdot dist (x, y, A \cup B) \\ \leq 2 r + s \cdot (k - 1 + k \cdot dist (x, y, S (A \cup B))), \end{aligned}

wobei die letzte Zeile aus Beobachtung 3.4.3 folgt. Wir setzen dies nun in ( $1$ ) ein:

\begin{aligned} dist (x, y, {Sample}_{k} (A^{'} \cup B^{'})) & \leq ⌈ \frac{dist (x, y, A^{'} \cup B^{'})}{k} ⌉ \\ \leq ⌈ \frac{2 r + s \cdot (k - 1 + k \cdot dist (x, y, S (A \cup B)))}{k} ⌉ \\ = ⌈ \frac{2 r + s (k - 1)}{k} ⌉ + s \cdot dist (x, y, S (A \cup B)) \\ \leq r + s \cdot dist (x, y, S (A \cup B)) \end{aligned}

da nach Annahme $r \geq ⌈ \frac{2 r + s (k - 1)}{k} ⌉$ ist. Es gilt also ${Sample}_{k} (A \cup B) \overset{dense}{⟶} {Sample}_{k} (A^{'} \cup B^{'})$ . $◻$

Da ${Sample}_{k} (A \cup B) = S (u, t)$ und ${Sample}_{k} (A^{'} \cup B^{'}) = S (u, t + 1)$ ist, wissen wir nun $S (u, t) \overset{dense}{⟶} S (u, t + 1)$ gilt, wie im Lemma behauptet. $◻$

Ränge kennen und `merge` schnell durchführen

Definition 3.4.5 Seien $A$ und $B$ zwei sortierte disjunkte Listen. Wir sagen, dass $A$ seine Ränge in $B$ kennt, wenn wir für jedes $a \in A$ den Rang $rank (a, B)$ kennen. Wir schreiben $A \overset{rank}{⟶} B$ .

Wir nehmen an, dass wir für jedes Element eine kleine konstante Anzahl von Speicherzellen haben, in denen wir z.B. eine solche Information speichern können. Bildlich sieht das so aus:

Invariante 3.4.6 Sei $v$ ein Knoten und der Elternknoten. Dann gilt zu jedem Zeitpunkt $L (u, t) \overset{rank}{⟶} S (v, t)$ . Und natürlich gilt auch die frühere Invariante $S (u, t) \overset{dense}{⟶} S (u, t + 1)$ aus Lemma 3.4.4.

Wir zeigen nun, wie man (1) mit Hilfe dieser Invariante die Operation $merge (S (L (v, t)), S (L (w, t)))$ schnell parallel berechnen kann. Auch müssen wir zeigen, wie man die Schleifeninvariante für den nächsten Zeitschritt $t + 1$ garantieren kann.

Lemma 3.4.7 (Bedingte Transitivität). Sei $A \overset{rank}{⟶} B$ und $B \overset{rank}{⟶} C$ . Sei weiterhin $B \overset{dense}{⟶} C$ . Dann können wir in $O (r + s)$ Zeitschritten und $(r + s) \cdot | A |$ Arbeitsschritten $A \overset{rank}{⟶} C$ berechnen, also $rank (a, C)$ für jedes $a \in A$ .

Beweis. Wir kennen $j := rank (a, B)$ . Betrachten wir die Elemente $b_{j}$ und $b_{j + 1}$ .

Um $rank (a, C)$ zu bestimmen, genügt es, $a$ mit allen $c \in C$ zu vergleichen, für die $b_{j} < c \leq b_{j + 1}$ gilt. Wieviele gibt es davon? Genau $dist (b_{j}, b_{j + 1}, C) \leq r + s \cdot dist (b_{j}, b_{j + 1}) = r + s$ viele.

Um genauer zu sein: der für das $i$ -te Element von $A$ (nennen wir es $a$ ) zuständige Prozessor bestimmt $j := rank (a, B)$ ; dies kann er, weil nach Annahme $A \overset{rank}{⟶} B$ , wir es also gespeichert haben. Daraufhin bestimmt er $l := rank (b_{j}, C)$ und $l^{'} := rank (b_{j + 1}, C)$ und vergleicht $a$ mit allen Elementen $c_{l + 1}, c_{l + 2}, \dots, c_{l^{'}}$ . Wenn von diesen $l^{'} - l$ Elementen genau $q$ viele $\leq a$ sind, dann gilt $rank (a, C) = l + q$ .

◻

Lemma 3.4.8 (Bedingte Symmetrie). Wenn $A \overset{rank}{⟶} B$ und $A \overset{dense}{⟶} B$ , dann können wir $B \overset{rank}{⟶} A$ in $O (r + s)$ Schritten und $| A |$ Prozessoren berechnen.

Beweis. Wir haben je einen Prozessor pro Zelle des Arrays $A$ . Der Prozessor von Zelle $i$ schaut den Rang seines Elements in $B$ nach: $j_{1} := rank (A [i], B)$ ; dann den Rang seines rechten Nachbarn: $j_{2} := rank (A [i + 1], B)$ . Nun weiß er: alle Elemente $B [j_{1} + 1], \dots, B [j_{2}]$ sind größer als $A [i]$ aber kleiner als $A [i + 1]$ ; daher setzt er nun

for each $j = j_{1} + 1, \dots, j_{2}$ :
1. $rank (B [j], A) := i$

Nach Annahme gilt $j_{2} - j_{1} \leq r + s$ , und somit führt der Prozessor $i$ höchstens $r + s$ Schritte aus.

Der für on verantwortliche Prozessor muss allen Elementen in $B$ von peace bis radar mitteilen, dass sie in $A$ an den rechten Rand der Zelle von on zeigen sollen. $◻$

Lemma 3.4.9 (Wie man merge schnell berechnet). Wir können $merge (S (v, t), S (w, t))$ mit $| L (u, t) |$ Prozessoren in konstanter Zeit berechnen.

Beweis. Nach Invariante 3.4.6 gilt $S (v, t - 1) \overset{dense}{⟶} S (v, t)$ ; auch gilt $L (u, t) = S (v, t - 1) \cup S (w, t - 1)$ , und somit ist auch $L (u, t) \overset{dense}{⟶} S (v, t)$ (wenn $A \overset{dense}{⟶} B$ dann ist jede Obermenge $A^{'} \supseteq A$ auch dicht in $B$ ). Es gelten also

Mit Hilfe von Lemma 3.4.8 und Lemma 3.4.7 können wir nun

berechnen. Jedes Element $x \in S (v, t)$ kennt nun also $rank (x, S (w, t))$ (aus obigem Bild) und natürlich $rank (x, S (v, t))$ (weil $S (v, t)$ als sortierte Liste vorliegt. Daher erhalten wir per Addition $rank (x, S (v, t) \cup S (w, t)) = rank (x, L (u, t + 1))$ . Genauso für jedes $y \in S (w, t)$ . Wir können also $merge (S (v, t), S (w, t))$ in $O (r + s)$ vielen Schritten berechnen.

◻

Beobachtung 3.4.10 Wir können in $O (r + s)$ Schritten Invariante 3.4.6 aufrecht erhalten, also $L (u, t + 1) \overset{rank}{⟶} S (v, t + 1)$ berechnen.

Beweis. Sei $x \in L (u, t + 1)$ . Es gibt einen separaten Prozessor für $x$ , und wir müssen zeigen, wie dieser $rank (x, L (v, t + 1))$ in konstant vielen Schritten berechnen kann. Da $L (u, t + 1) = S (v, t) \cup S (w, t)$ die Vereinigung zweier Mengen ist, gehen wir separat (aber parallel) für jede der zwei Teilmengen vor:

1. Für jedes $x \in S (v, t)$ : Seien $a$ und $b$ die Kinder von $v$ . Dann ist $L (v, t + 1) = S (a, t) \cup S (b, t)$ , und per Invariante gilt $L (v, t) \overset{rank}{⟶} S (a, t)$ . Da $x \in L (v, t)$ ist, kennen wir bereits den Rang von $x$ in $S (a, t)$ , und analog auch in $S (b, t)$ . Addition ergibt den Rang von $x$ in $L (v, t + 1)$ , und kein weiterer Vergleich ist nötig. Wir haben nun also $S (v, t) \overset{rank}{⟶} S (v, t + 1)$ .

2. Für jedes $x \in S (w, t)$ . Im Beweis von Lemma 3.4.9 haben wir bereits $S (w, t) \overset{rank}{⟶} S (v, t)$ berechnet. Gerade eben haben wir $S (v, t) \overset{rank}{⟶} S (v, t + 1)$ berechnet. Nach Lemma 3.4.4 gilt $S (v, t) \overset{dense}{⟶} S (v, t + 1)$ . Insgesamt also

und nach Lemma 3.4.7 können wir auch $S (w, t) \overset{rank}{⟶} S (v, t + 1)$ berechnen.

Wir haben nun also sowohl $S (w, t) \overset{rank}{⟶} S (v, t + 1)$ als auch $S (v, t) \overset{rank}{⟶} S (v, t + 1)$ und somit $L (u, t + 1) = S (v, t) \cup S (w, t) \overset{rank}{⟶} S (v, t + 1)$ , wie behauptet. $◻$

Verteilung der Prozessoren

Sobald $L (u, t) = L (u)$ erreicht ist, verändert sich $L (u, t)$ nicht mehr, muss also auch nicht neu berechnet werden. Wir benötigen somit auch keine Prozessoren mehr. Wir nennen einen Knoten daher aktiv zum Zeitpunkt $t$ , wenn $L (u, t) \neq L (u)$ gilt.

Übungsaufgabe 3.4.4 Zeigen Sie: zu jedem Zeitpunkt ist die Anzahl der Elemente in aktiven Knoten höchstens $O (n)$ , also

\begin{array}{r} \sum_{u : aktiv zum Zeitpunkt t} | L (u, t) | \in O (n) . \end{array}

Wenn wir Level $i$ des Knotens $u$ und Zeitpunkt $t$ kennen, so können wir schnell die Länge $| L (u, t) |$ berechnen. Diese ist unabhängig vom Input. So können wir auch schnell bestimmen, für welchen Knoten $u$ und für welches Element in der dortigen Liste $L (u, t)$ der Prozessor verantwortlich ist.