ParAlg, Kapitel 6

6. Massiv parallele Algorithmen

Unser Rechnermodell besteht aus $P$ Maschinen, von denen jede einen lokalen Speicher hat, der $S$ Items halten kann. Ein Item besteht üblicherweise aus einem oder einer konstanten Zahl von Maschinenwörtern. Der Input besteht aus $N$ Items, die auf beliebige Weise auf die Maschinen verteilt sind, aber so, dass jede Maschine nicht mehr als $S$ Items hält. Es gilt also $N \leq P \cdot S$ . Wir gehen meistens davon aus, dass $P \cdot S \geq c N$ sind für eine konstante $c$ , zum Beispiel $c = 2$ , einfach, um etwas Spielraum zu haben und Items auch mal doppelt speichern zu können.

Definition 6.1(Runde in einem MPC-Algorithmus). In jeder Runde führt jede Maschine eine lokale Berechnung ihrer Menge von Items durch; deren Ergebnis ist wiederum eine Menge von Items, die sie dann an eine oder mehrere Maschinen schicken wird. Dabei muss jedoch gelten, dass keine Maschine mehr als $S$ Items verschickt oder mehr als $S$ Items empfängt. Formal:

In Runde $r$ hält Maschine $i$ eine Menge $X_{i, r}$ an Items. Es gilt $| X_{i, r} | \leq S$ .
Sie führt nun eine lokale Berechnung durch und erhält dadurch eine neue Menge: $Y_{i, r} := f (X_{i, r})$ ; ein Element in $Y_{i, r}$ ist von der Form $(j, y)$ , wobei $j$ der Index der Maschine ist, an den dies geschickt werden soll. Sei also $Y_{i, r, j} := {y | (j, y) \in Y_{i, r}}$ die Menge der Items, die Maschine $i$ am Ende von Runde $r$ an Maschine $j$ schicken will.
Maschine $i$ schickt $Y_{i, r, j}$ an Maschine $j$ .
Maschine $j$ empfängt die Items von mehreren Maschinen und setzt $\begin{array}{r} X_{j, r + 1} := ⋃_{i} Y_{i, r, j} . \end{array}$ Wobei wir sicherstellen müssen, dass $\sum_{i} | Y_{i, r, j} | \leq S$ gilt.

Die Funktion $f$ darf vom Index $i$ der Maschine und der Runde $r$ abhängen; ganz pedantisch würden wir also $f (i, r, X_{i, r})$ schreiben.

Dies ist eine Runde eines MPC-Protokolls. Insbesondere tun wir so, als könnte die lokale Berechnung $f$ in $O (1)$ Zeit ausgeführt werden. Das ist natürlich nicht immer realistisch, trägt aber der empirischen Tatsache Rechnung, dass die Gesamtkomplexität von den I/O-Operationen, also der Kommunikation über das Netzwerk, und nicht von den eigentlichen Rechenoperationen dominiert wird. In den MPC-Algorithmen, die wir vorstellen werden, sind die lokalen Rechenoperationen $f$ in der Tat immer sehr einfache Operationen (die immer in polynomieller und meist auch linearer Zeit oder $O (n \log n)$ ausgeführt werden können).

Typische Parameter für $S$ und $P$

Interessant wird das MPC-Modell, wenn $S$ so groß ist, dass jede Maschine einen signifikanten Teil der Berechnung lokal erledigen kann, aber noch nicht so groß, dass sie alles erledigen könnte. Zum Beispiel wenn $S = N^{ϵ}$ gilt für $0 < ϵ < 1$ , wobei $ϵ$ aber eher nahe bei $0$ ist als bei $1$ . Ein wichtiger Parameter in diesem Setting ist

\begin{array}{r} λ := \frac{\log N}{\log S} = \frac{1}{ϵ} . \end{array}

Laufzeit

Im Zusammenhang von MPC-Algorithmen interessieren wir uns vorerst hauptsächlich für die Anzahl der Runden. Unser Ziel ist es, Algorithmen von konstanter Rundenkomplexität zu entwerfen - die Anzahl der Runden soll also nicht von der Inputgröße $N$ abhängen. Sie kann und wird jedoch von dem Parameter $ϵ$ abhängen. Eine typische gute Laufzeit wird $O (λ) = O (\frac{1}{ϵ})$ sein.

Literatur

Mohsen Ghaffari: Parallel Algorithms, Kapitel 6 im Skript zur Vorlesung APC (Algorithms, Probability, and Computing) an der ETH Zürich
Mohsen Ghaffari: Massively Parallel Algorithms, das Skript zur gleichnamigen Vorlesung an der ETH Zürich

6. Massiv parallele Algorithmen

Typische Parameter für S und P

Laufzeit

Literatur

Typische Parameter für $S$ und $P$