ParAlg, Kapitel 6.1

6.1 Broadcast, Summen, Präfixsummen

Problem 6.1.1 (MPC-Summe). Die Eingabe besteht aus einer Menge (bzw. Multimenge) von $N$ natürlichen $x_{1}, \dots, x_{N}$ . Wir wollen die Summe $x := x_{1} + \dots + x_{N}$ berechnen; genauer gesagt wollen wir, dass am Ende der Berechnung jede Maschine genau einen Item hält: die Zahl $x$ .

Theorem 6.1.2 Wenn jede Maschine $S = N^{ϵ}$ Speicher hat, dann können wir MPC-Summe in $O (1 / ϵ)$ Runden berechnen.

Beweis. Wir bauen einen $S$ -ären gewurzelten Baum mit $P$ Blättern. Jedes Blatt entspricht einer Maschine und somit der Menge der Items (hier: Zahlen), die diese am Anfang hält. Für $S = 4$ sieht dies so aus:

In jeder Runde bildet Maschine $i$ nun die Summe der Items, die sie hält, und schickt sie an den Eltern-Knoten weiter. Der Baum hat Höhe $h = \log_{S} (P) \leq \log_{S} (N) = λ = \frac{1}{ϵ}$ . Nach $h + 1 = \frac{1}{ϵ} + 1$ Runden hat der Wurzelknoten die Gesamtsumme berechnet. $◻$

Übungsaufgabe 6.1.1 (Lästige Details). Im obigen Baum tun wir so, als hätten wir "unten" $N / S$ viele Maschinen, die "voll" sind, also jeweils $S$ Items halten, und weiter oben dann $< N / S$ viele innere Knoten, die anfangs alle leer sind. Unsere Annahme war allerdings, dass die Items beliebig auf Maschinen verteilt sind.

Können wir mit einem Initialisierungsschritt erreichen, dass keine Maschine "voll" ist, sondern höchstens $\frac{3}{4} \cdot S$ Items enthält?
Können wir in einem weiteren Initialisierungsschritt erreichen, dass eine gewisse Anzahl von Maschinen, sagen wir die $P / 4$ Maschinen mit höchstem Index, "leer" sind, also keine Items tragen?

Im folgenden wird es einfacher sein, anzunehmen, dass anfangs jede Maschine höchstens $S / 2$ Items (oder generell höchstens $c \cdot S$ Items) hält.

Übungsaufgabe 6.1.2 Erweitern Sie den Baum-Algorithmus aus dem Beweis von Theorem 6.1.2 so, dass er alle Präfixsummen berechnet. Hier müssen wir die Eingabe spezifizieren: ein Item ist ein Paar $(i, x_{i})$ ; die Zahl $i$ heißt der Index des Items und $x_{i}$ heißt der Wert des Items. Wir gehen davon aus, dass alle Items unterschiedliche Indizes halten. Ergebnis der Präfixsummenberechnung soll eine Menge von Items $(i, y_{i})$ sein, mit

\begin{array}{r} y_{i} := x_{1} + x_{2} + \dots + x_{i} . \end{array}

Überzeugen Sie sich, dass Ihr Algorithmus nicht nur für $+$ , sondern für beliebige assoziative Operatoren $\circ$ funktioniert.

Ganz allgemein: wenn wir davon sprechen, dass die Eingabe ein Array ist, dass meinen wir eine Menge aus indizierten Items, also $(i, x_{i})$ wie oben beschrieben.

Übungsaufgabe 6.1.3 Gegeben ein Array der Länge $N$ mit Werten True und False, bestimme für jeden Index $1 \leq i \leq N$ den Index des nächsten True-Eintrages zur Linken, also $max {j | j \leq i und x_{j} = True}$ . Ihr Algorithmus sollte $O (λ)$ Runden haben.

Mithilfe von Übungsaufgabe 6.1.3 können wir nun in einem Array, in welchem manche Einträge "markiert" sind das somit in Teilarrays zerlegt ist, für jeden Index die ihn umgebenden Markierungen finden und somit bestimmen, zu welchem Intervall er gehört und wo dieses anfängt und endet.