ParAlg, Kapitel 3.1

3.1 Sortiernetzwerke

Wir kommen auf unsere Gadget-Metapher zurück. Zum Sortieren verwenden wir ein Minmax-Gate, dass zwei Inputs und zwei Outputs hat:

Aus diesem Minmax-Gate wollen wir einen Schaltkreis bauen, der Sortieren kann. Das nennt man in diesem Zusammenhang ein Sortiernetzwerk. Wir folgen der Idee von Mergesort: wir zerlegen die Eingabeliste in zwei Teile, die wir rekursiv sortieren; dann rufen wir eine Prozedur merge auf, die die zwei sortierten Teillisten $X$ und $Y$ zu einer großen sortierten Liste $Z = merge (X, Y)$ zusammenfügt. Sequentiell ist die Prozedur merge einfach zu implementieren und tätigt im Worst-Case $| X | + | Y | - 1$ Vergleiche. Parallel ist das schon schwieriger. In diesem Teilkapitel beschreiben wir Batchers Odd-Even Merging Network und das mergesort-artige Sortiernetzwerk, das man daraus erhält.

Ein Netzwerk für Merge

Wir haben als Input zwei Listen gegeben: $X = [x_{1}, x_{2}, \dots, x_{n}]$ und $Y = [y_{1}, y_{2}, \dots, y_{n}]$ . Beide sind bereits sortiert. Wir wollen nun eine sortierte version der Vereinigung, also von $[x_{1}, \dots, x_{n}, y_{1}, \dots, y_{n}]$ berechnen. Sequentiell kennen Sie das als die Subroutine merge von MergeSort, zum Beispiel aus Kapitel 2.3 von TI-1. Um es parallel berechnen zu können, zerlegen wir das Array $X$ in die ungeraden und die geraden Indizes:

\begin{array}{r} X_{o d d} := [x_{1}, x_{3}, x_{5}, \dots, x_{n - 1}] \\ X_{e v e n} := [x_{2}, x_{4}, x_{6}, \dots, x_{n}], \end{array}

wobei wir davon ausgehen, dass $n$ gerade ist. Das dient zum Großteil dazu, die Notation zu vereinfachen. Nach gleichem Schema zerlegen wir $Y$ :

\begin{array}{r} Y_{o d d} := [y_{1}, y_{3}, y_{5}, \dots, y_{n - 1}] \\ Y_{e v e n} := [y_{2}, y_{4}, y_{6}, \dots, y_{n}], \end{array}

Nun führen wir rekursiv einen Merge auf $X_{o d d} \cup Y_{o d d}$ durch, ebenso auf $X_{e v e n} \cup Y_{e v e n}$ .

Wir erhalten also

\begin{aligned} U := [u_{1}, u_{2}, \dots, u_{n}] & = merge (X_{o d d}, Y_{o d d}) \\ V := [v_{1}, v_{2}, \dots, v_{n}] & = merge (X_{e v e n}, Y_{e v e n}) \end{aligned}

Jetzt müssen wir uns noch parallel aus $U$ und $V$ den Merge der Gesamtliste $X \cup Y$ zusammenbasteln - und zwar parallel. Wir können zum Beispiel bereits mit Sicherheit sagen, dass $u_{1}$ das kleinste dieser Liste ist. Danach wird es schon schwieriger.

Definition 3.1.1(Rang). Sei $Z = X \cup Y$ die Menge der Elemente in der Gesamtliste (wir gehen davon aus, dass kein Element doppelt vorkommt, um den Mengenbegriff bequem verwenden zu können). Der Rang eines Elements $s$ in $Z$ ist die Anzahl der Elemente $z$ mit $z \leq s$ , also:

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

So hat das Minimum von $Z$ zum Beispiel Rang $1$ und das Maximum Rang $2 n$ .

Wir fragen uns nun: was ist der Rang von $u_{i}$ , also einem Element, das in $X$ auf einer ungeraden Position stand oder in $Y$ . Das können wir nicht sicher sagen, zum Beispiel kann $u_{2}$ Rang 2 haben, aber auch Rang 3, wenn zum Beispiel $u_{1} < v_{1} < u_{2}$ gilt. Kann es Rang 4 haben? Das nächste Lemma beantwortet diese Frage:

Lemma 3.1.2 $rank (u_{i}) \in {2 i - 2, 2 i - 1}$ .

Beweis. Das Element $u_{i}$ ist in $X_{o d d} \cup Y_{o d d}$ enthalten. Dort gibt es genau $i$ Elemente, die $\leq u_{i}$ sind. Schauen wir uns an, wo $u_{i}$ in $X$ und $Y$ liegt. Seien $2 k - 1$ und $2 l - 1$ die größten ungeraden Indizes mit $x_{2 k - 1} \leq u_{i}$ und $y_{2 l - 1} \leq u_{i}$ . Dann gilt

\begin{array}{r} x_{1} < x_{2} < x_{3} < \dots < x_{2 k - 1} \leq u_{i} \\ y_{1} < y_{2} < y_{3} < \dots < y_{2 l - 1} \leq u_{i} . \end{array}

Die Mengen $X$ und $Y$ enthalten zusammen mindestens $2 k - 1 + 2 l - 1$ Elemente, die $\leq u_{i}$ sind, und somit gilt $rank (u_{i}, Z) \geq 2 k + 2 l - 2$ . Davon gehören $k$ zu $X_{o d d}$ und $l$ zu $Y_{o d d}$ , und somit gilt $k + l = rank (u_{i}, X_{o d d} \cup Y_{o d d}) = rank (u_{i}, U) = i$ . Zusammen schließen wir, dass $rank (u_{i}, Z) \geq 2 i - 2$ .

Folgende Elemente sind echt größer als $u_{i}$ :

\begin{aligned} u_{i} & < x_{2 k + 1} < x_{2 k + 2} < \dots < x_{n} \\ u_{i} & < y_{2 l + 1} < y_{2 l + 2} < \dots < y_{n} \end{aligned}

Das sind insgesamt $n - 2 k + n - 2 l = 2 n - 2 i$ Elemente, die größer sind als $u_{i}$ . Betrachten wir noch $x_{2 k - 1}$ und $y_{2 l - 1}$ . Eines davon ist $u_{i}$ selbst, und somit ist eines von $x_{2 k}, y_{2 k}$ echt größer als $u_{i}$ . Es gibt also mindestens $2 n - 2 i + 1$ Elemente, die echt größer sind als $u_{i}$ , und somit ist $rank (u_{i}) \leq 2 i - 1$ . $◻$

Lemma 3.1.3 $rank (v_{i}) \in {2 i, 2 i + 1}$ .

Übungsaufgabe 3.1.1 Beweisen Sie das obige Lemma.

Für $i = 1$ ergibt das erste Lemma $rank (u_{1}) \in {0, 1}$ und somit $rank (u_{1}) = 1$ , da ein Rang von 0 unmöglich ist. Analog erhalten wir $rank (v_{n}) = n$ . Für $i = 1, \dots, n - 1$ wenden nun die beiden Lemmas auf $u_{i + 1}$ und $v_{i}$ an und sehen, dass

\begin{array}{r} {rank (u_{i + 1}), rank (v_{i})} = {2 i, 2 i + 1} \end{array}

gilt. Wir müssen also nur noch $u_{i + 1}$ und $v_{i}$ vergleichen und können bestimmen, welche Elemente $z_{2 i}$ und $z_{2 i + 1}$ in der endgültigen sortierten Liste $Z = [z_{1}, \dots, z_{2 n}]$ sind. Im Überblick erhalten wir folgende rekursive Konstruktion für merge:

Beobachtung 3.1.4 Das oben beschriebene Merge-Netzwerk hat $Θ (n \log n)$ minmax-Gates und Tiefe $Θ (\log n)$ .

Ein Sortiernetzwerk auf Merge-Netzwerken

Um nun ein Array $[x_{1}, x_{2}, \dots, x_{n}]$ der Länge $n$ zu sortieren, gehen wir wieder rekursiv vor. Wir nehmen an, dass $n$ gerade ist, und teilen das Array in zwei Hälften $L = [x_{1}, \dots, x_{n / 2}]$ und $U = [x_{n / 2}, \dots, x_{n}]$ . Wir sortieren rekursiv und wenden dann merge auf die Ergebnisliste an.

Theorem 3.1.5 Das gerade beschriebene Sortiernetzwerk hat Tiefe $Θ (\log^{2} n)$ und $Θ (n \log^{2} n)$ viele Gates.

Übungsaufgabe 3.1.2 Beweisen Sie das Theorem.