\( \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{\succ}{\textnormal{succ}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\Z}{\mathbb{Z}} \)

Um möglichst nahe an unserer Schaltkreis-Metapher zu bleiben, stellen wir uns eine beliebig große Menge an Prozessoren vor, die jeweils den selben Code ausführen. Sie greifen dabei auf einen gemeinsamen Speicher zu. Dieser Code hat folgende Form:

P($i$: index of processor, $t$: time step):
  1. Perform a constant number of elementary operations, such as:
    1. Use simple operations on $i$ and $t$ to compute some address $a$.
    2. Load cell $\texttt{a}$ of the shared memory into the processor's local register.
    3. Compute some data $d$ and another address $\texttt{b}$ by simple calculations.
    4. Store $d$ in cell $\texttt{b}$.

Gates verschiedener Typen (AND, OR, XOR) können Sie leicht simulieren: der Prozessor kann ein dem Index $i$ erkennen, welchen Gate-Typ er simulieren soll und wo im Speicher er seine Inputs finden kann. Und wenn das nicht einfach aus dem Index $i$ erkennbar ist, dann ist Ihre Schaltkreis-Konstruktion vielleicht auch nicht wirklich algorithmisch; solche nicht-uniformen Schaltkreise gibt es und sie sind wichtig, kommen aber in dieser Vorlesung nicht vor. Falls Sie sich erinnern: Valiants probablitistische Konstruktion eines monotonen Schaltkreises logarithmischer Tiefe für Majority, die wir in Kapitel 1.5 von Theoretische Informatik II besprochen haben, ist ein solcher nicht-uniformer Schaltkreis. Wir wissen bis heute (2024) nicht, wie man effizient berechnet, wie Gate $i$ aussieht und von welchen anderen Gates es seine Inputs liest.

Ein Aufruf von $P(i,t)$ führt mehrere (konstant viele) Anweisungen aus, stellt aber einen Zeitschritt dar. Der gesamte parallele Algorithmus wird dann von einem Scheduler geleitet:

Scheduler$(n: \textnormal{size of input})$:
  1. Berechne die Anzahl $T$ der benötigten Zeitschritte
  2. $\texttt{for}\ t=1,\dots,T$:
    1. Sei $S_t$ die Menge der Prozessoren (genauer: ihrer Indizes), die in Schritt $t$ gebraucht werden.
    2. Rufe $P(i,t)$ für jedes $i \in S_t$ parallel auf.

Des weiteren vertrauen wir darauf, dass die Berechnung von $T$ in Schritt 1 und die von $S_t$ in Schritt 2.1 von Scheduler sehr effizient vonstatten geht.

Definition (Arbeit und Zeit). Die Anzahl der Arbeitsschritte oder einfach die Arbeit eines Algorithmus ist

\begin{align*} w := \sum_{t = 1}^T |S_t| \ , \end{align*}

also die Gesamtzahl der Prozessorenaufrufe. Die Anzahl der Zeitschritte oder einfach die Zeit eines parallelen Algorithmus ist $T$, die Anzahl der Schleifendurchläufe von Scheduler.

Wir heben folgende Punkte hervor:

  • Der Scheduler greift nie direkt auf den Speicher zu. Er kennt nur die Größe $n$ des Inputs.
  • Wir gehen davon aus, dass die Schleife (Schritte 2, 2.1 und 2.2 von Scheduler) synchronisiert ist: der Durchlauf für $t+1$ beginnt erst, wenn alle Prozessoren den von $t$ beendet haben. Innerhalb eines Durchlaufs (also innerhalb eines Zeitschrittes, in welchem die Prozessoren konstant viele Anweisungen durchführen), gehen wir nicht von Synchronisation aus.
  • Letzterer Punkt zeigt die Gefahr von Schreib-Lese-Konflikten auf. Daher definieren wir:

Definition (Concurrent Read, Exclusive Write PRAM, kurz CREW PRAM). Ein paralleler Algorithmus für eine CREW PRAM muss folgende Bedingung erfüllen: wenn ein Prozessor in einem Schritt $t$ auf Adresse $\texttt{a}$ schreibt, dann darf kein anderer Prozessor in Schritt $t$ auf Adresse $\texttt{a}$ zugreifen, weder lesend noch schreibend.

Übungsaufgabe Hier sehen Sie noch einmal den Code von pointerJump

def pointerJumping($i$: index of processor):
  1. $s := \succ[i]$
  2. $\val[i] := \val[i] + \val[s]$
  3. $\succ[i] := \succ[s]$
Dieser Code verletzt das CREW-Kriterium: in Schritt 3 wird $\succ[i]$ geschrieben, zeitgleich aber eventuell von einem anderen Prozessor $j$ gelesen. Schreiben Sie den Code so um, dass er CREW-kompatibel ist.

Der Scheduler für Pointer Jumping ist einfach: es werden einfach in jedem Zeitschritt alle Prozessoren $1,\dots,n$ aufgerufen, also $S_t = \{1, \dots, n\}$.

Beobachtung Der parallele Algorithmus Pointer Jumping läuft in $O(\log(n))$ Zeit und $O(n \log n)$ Arbeit.

Übungsaufgabe Schreiben Sie den Code von $\texttt{pointerJump}$ so um, dass wir am Ende wieder eine verkettete Liste haben, die die Suffixsumme enthält. Der derzeitige Code zerstört die Pointerstruktur der Liste.

Übungsaufgabe Schreiben Sie den Schaltkreis für Präfixsummen in einem Array (also die Konstruktion aus Kapitel 2.3) als Code für eine CREW PRAM, also mit Code für $P(i,t)$ und einen Scheduler.

Tip. Numerieren Sie Ihre Gates durch und nehmen Sie sich für jedes Gate einen neuen Prozessor.

Brent's Principle

Obiges Modell nimmt eine unbegrenzte Anzahl von Prozessoren an. Insbesondere eine, die mit der Größe der Inputinstanz wächst. Was aber, wenn uns nur eine begrenzte Anzahl $p$ von Prozessoren zur Verfügung steht? Hier greift Brent's Principle, was besagt, dass man einen parallelen Algorithmus immer teilweise sequentialisieren kann.

Brent's Principle. Sei $A$ ein paralleler Algorithmus mit Zeit $T$ und Arbeit $w$. Sei weiterhin eine Zahl $p \in \N$ gegeben. Dann gibt es einen parallelen Algorithmus $A'$ mit $p$ Prozessoren, Arbeit $w$ und Zeit $\frac{w}{p} + T$.

Begründung. Für jeden Zeitschritt $t$ von Algorithmus $A$ teilen wir die $|S_t|$ Arbeitsschritte gleichmäßig auf die $p$ Prozessoren auf. Jeder Prozessor muss dann bis zu $\ceil{\frac{|S_t|}{p}}$ Schritte von $A$ ausführen. Insgesamt braucht der neue Algorithmus $A'$ dann

\begin{align*} \sum_{t=1}^{T} \ceil{\frac{|S_t|}{p}} & \leq \sum_{t=1}^{T} \left(\frac{|S_t|}{p} + 1\right) \\ & = T + \sum_{t=1}^{T} \frac{|S_t|}{p} = T + \frac{w}{p} \end{align*}

Zeitschritte. Formal können wir Algorithmus $A'$ beschreiben, in dem wir den Code vom Scheduler und der individuellen Prozessoren angeben.

Scheduler-von-A'$(n: \textnormal{size of input})$:
  1. Berechne die Anzahl $T$ der benötigten Zeitschritte von Algorithmus $A$
  2. $\texttt{for}\ t=1,\dots,T$:
    1. Sei $S_t$ die Menge der Prozessoren (genauer: ihrer Indizes), die der Algorithmus $A$ in Schritt $t$ braucht.
    2. $S := \ceil{\frac{|S_t|}{p}}$ # so viele Schritte muss also ein $A'$-Prozessor ausführen, damit wir einen $A$-Schritt simulieren können
    3. Zerlege $S_t = S_t^{(1)} \cup S_t^{(2)} \cup \dots \cup S_t^{(p)}$, so dass $|S_t^{(l)}| \leq S$ für jedes $1 \leq l \leq p$ gilt. // Die Menge $S_t^{(l)}$ ist die Menge der Schritte, die ein $A'$-Prozessor $l$ nun sequentiell aber in beliebiger Reihenfolge erledigen soll
    4. $\texttt{for}\ s=1,\dots,S$:
      1. Rufe $P'(l,t,s)$ für jedes $l \in \{1, \dots, p\}$ parallel auf.
P'($l$: index of processor, $t$: time step of outer loop, $s$: time step of inner loop):
  1. $i := $ das $s$-te Element in $S_t^{(l)}$
  2. Rufe $P(i,t)$ auf

Wieder geht der Code mit einigem an Vertrauen einher: dass wir in Schritt 2 von P' den Index $i$ des Algorithmus-A-Prozessors schnell berechnen können. Im konkreten Anwendungsfall sollte das meistens kein Problem sein, und man kann sich in der Tat auch Zeile 2.3 in scheduler-von-A' sparen, weil das eben in Zeile 2 von P' direkt und parallel berechnet werden kann. Aber immerhin ist dieser Schritt vage genug, dass ich von Brent's Principle und nicht von Brent's Theorem spreche. \(\square\)