ParAlg, Kapitel 2.3

2.3 Präfixsummen parallel berechnen

Im letzten Teilkapitel haben wir gelernt, wie man das scheinbar inhärent sequentielle Problem der Binäraddition effizient parallelisiert. Als Rechnermodell haben wir dabei die uns bereits bekannten Booelschen Schaltkreise gewählt. Wir werden nun ein ähnliches Problem untersuchen: wir haben ein Array $[a_{1}, \dots, a_{n}]$ von $n$ natürlichen Zahlen berechnet und wollen die $n$ Präfixsummen

\begin{array}{r} s_{i} := a_{1} + \dots + a_{i} \end{array}

Dieses Problem nennt man Präfixsummen parallel berechnen oder kurz parallele Präfixsummen, auf Englisch parallel prefix sum. Der Lösungsansatz ist ganz ähnlich wie für den Binäraddierer. Allerdings wird bei den parallelen Präfixen das zugrunde liegende Problem besser deutlich, und noch dazu dient es als Baustein für viele weitere parallele Algorithmen.

Als Berechnungsmodell nehmen wir wieder Schaltkreise, nun aber nicht Boolesche, sondern arithmetische. Jedes Gate kann nur eine Operation durchführen: Addition zweier natürlicher Zahlen. Auf den Kanten des Schaltkreises fließen auch keine Booleschen Werte sondern natürliche Zahlen (natürlich). Beim Entwurf unseres Schaltkreises gehen wir rekursiv vor:

Sie $S (n)$ die Größe des obigen Schaltkreise (also Anzahl der Gates) bei einem Array der Größe $n$ . Wenn $n$ gerade ist, gilt

\begin{aligned} S (n) & = S (n / 2) + n - 1 \end{aligned}

Das zusätzliche $n -$ kommt daher, dass jedes Gate einem Output entspricht, wobei $s_{1}$ kein Gate benötigt. Der Einfachheit halber schätzen wir $S (n) \leq S (n / 2) + n$ ab und somit

\begin{array}{r} S (n) = n + n / 2 + n / 4 + \dots + 1 = 2 n - 1 \end{array}

wenn $n$ eine Zweierpotenz ist. Anzahl der Zeitschritte ist $2 \log n$ .

Schaltkreis-Sichtweise und Prozessoren-Sichtweise

So wie vor zwei Kapiteln begründet, betrachte ich jedes Gate als einen Prozessor, der zu einem bestimmten Zeitpunkt die Bühne betrifft, genau einen Schritt ausführt (oder besser gesagt: $O (1)$ Schritte) und sich dann aus dem Geschehen zieht. Begründet habe ich das unter Anderem mit der Behauptung, wir könnten die Anzahl der Prozessoren problemlos verkleinern (was natürlich einen Zuwachs in der Zeit nach sich zieht).

Übungsaufgabe 2.3.1 Arbeiten Sie die Details aus! Nehmen Sie an, Sie hätten $p = n / \log (n)$ Prozessoren zur Verfügung. Können Sie die Rechenschritte so auf die Prozessoren verteilen, dass Sie immer noch in $O (\log n)$ Zeitschritten fertig werden?

Hinweis. Jetzt kommt die Schaltkreis-Intuition an ihre Grenzen und wir müssen festlegen, wie unsere Prozessoren arbeiten. Nehmen Sie an, die Prozessoren würden auf einen gemeinsamen Arbeitsspeicher zugreifen (in dessen ersten $n$ Zellen das Eingabe-Array liegt). In einem Makro-Schritt könnte ein Prozessor also so etwas tun wie

Lade Speicherzellen $i$ und $j$
Berechne die Summe der Inhalte
Speichere das Ergebnis in Zelle $k$

Abstrahierung

Die rekursive Konstruktion oben ist viel einfacher als unser Gerechne mit den Binärintervallen und Präfixintervallen im letzten Teilkapitel. Ich will daher argumentieren, dass man ein grundlegendes Prinzip herausarbeiten kann, mit dem man parallele Präfixsummen und binäre Addition gleichzeitig erschlagen kann. Hierfür müssen wir abstrahieren.

Sei $X$ eine Menge und $(a_{1}, \dots, a_{n}) \in X^{n}$ ein Array. Des weiteren sei $\circ$ eine Operation $\circ : X \times X \to X$ , wobei wir allerdings statt $\circ (a, b)$ die Infixschreibweise $a \circ b$ bevorzugen. Wir nehmen an, dass $\circ$ assoziativ ist, dass also

\begin{array}{r} \forall a, b, c \in X : a \circ (b \circ c) = (a \circ b) \circ c \end{array}

gilt. In diesem Falle dürfen wir ohne Verwechslungsgefahr $a \circ b \circ c$ schreiben. Wir wollen nun alle Präfixprodukte

\begin{array}{r} s_{i} := a_{1} \circ \dots \circ a_{i} \end{array}

berechnen. Dies effizient parallel zu berechnen nennt man paralleles Berechnen von Präfixen, kurz parallele Präfixe, Englisch parallel prefix. Wir nehmen an, dass ein Prozessor das Produkt $a \circ b$ in einem Schritt berechnen kann und stellen uns das wieder als $\circ$ -Gate vor. Die effiziente Konstruktion ist identisch mit der obigen, nur dass wird $+$ durch $\circ$ ersetzen. Die Operation $+$ ist natürlich assoziativ. Überzeugen Sie sich, dass es für den Erfolg der Parallelpräfixkonstruktion nicht entscheidet ist, ob $\circ$ auch kommutativ ist. Auch ob es eine Gruppenoperation ist, ob es also neutrale oder inverse Elemente gibt, ist nicht wichtig.

Können wir die Binäraddition mit Carry-Lookahead in dieses Framework pressen? Hierfür beobachten wir, dass $g p_{I}$ drei Werte annehmen kann: $(1, 1), (0, 1), (0, 0)$ , die den drei "Aktionen" Übertrag erzeugen, Nicht erzeugen, aber weiterreichen und Übertrag verschlucken entsprechen. Die Menge $X$ unserer Werte ist also $X = {(1, 1), (0, 1), (0, 0)}$ und $\circ$ ist durch das $g p$ -Gate realisiert. Wir können für $\circ$ auch die "Multiplikationstabelle" schreiben. Für $I = [a, b]$ , $J = [a, i]$ und $K = [i + 1, b]$ kann nämlich $g p_{I}$ durch folgende Tabelle gegeben:

Übungsaufgabe 2.3.2 Zeigen Sie, dass $\circ$ assoziativ ist. Konkret also, dass die beiden Schaltkreise

die gleiche Boolesche Funktion berechnen.

Sie führen nun die obige Konstruktion für parallele Präfixsummen durch, ersetzen nun aber $+$ durch $g p$ -Gates. Dann können Sie sich alle Überlegungen zu Binärintervallen und Präfixintervallen sparen.

Übungsaufgabe 2.3.3 Sie haben ein Array aus $n$ Elementen. Wenn in eine Reihe hintereinander mehrmals das gleiche Element steht, sprechen wir von einem Block. Das Array [a,a,a,c,c,d,a,e,e,e] besteht also aus insgesamt fünf Blöcken der Längen 3, 2, 1, 1 und 3.

Sie wollen für jeden Index $i$ berechnen, wie lange der zugehörige Block ist und der wievielte. Für das obige Array zum Beispiel wollen Sie die Ausgabe-Arrays

            Lengths    = [3,3,3,2,2,1,1,3,3,3] 
            BlockIndex = [1,1,1,2,2,3,4,5,5,5]

berechnen. Zeigen Sie, wie das mit $O (n)$ Arbeit und $O (\log n)$ Zeit geht.

Übungsaufgabe 2.3.4 (Bestes Subinterval). Sie haben ein Array aus ganzen Zahlen gegeben, z.B.

            A = [-8, 5, -4, 7, -9, 3, 0, 7, -5, 8, -1, 2, -5, 2, 9, -3]

Ein Subarray ist ein Array der Form A[i...j]. Der Wert eines Subarrays ist die Summe seiner Elemente. Sie wollen das Subarray mit dem höchsten Wert finden:

\begin{array}{r} A = [- 8, \overset{8}{\overset{⏞}{5, - 4, 7}}, - 9, \underset{20}{\underset{⏟}{\overset{14}{\overset{⏞}{3, 0, 7, - 5, 8, - 1, 2}}, - 5, 2, 9}}, - 3] \end{array}

in diesem Falle also wohl [3, 0, 7, -5, 8, -1, 2, -5, 2, 9] mit dem Wert 20.

Entwerfen Sie einen sequentiellen Algorithmus, der den Wert des optimalen Subarrays in $O (n)$ Schritten berechnet.

Lösung

Irgendjemand hat uns gesagt, dass das mit Dynamic Programming geht. Wir müssen also Teilprobleme definieren. Sei

b e s t U n t i l H e r e (t)

der Wert des optimalen Teilarrays von

A [i \dots j]

mit

j \geq t

, also die Lösung für das Interval

A [0 \dots t]

. Wir wollen nun zeigen, dass wir

b e s t U n t i l H e r e (t)

einfach berechnen können, wenn wir bereits

b e s t U n t i l H e r e (t - 1)

kennen. Sei nun

I \subseteq [0, t]

das beste Teilinterval von

A [0 \dots t]

. Wir unterscheiden zwei Fälle: (1) falls

t \notin I

ist, dann ist

I

bereits ein Teilinterval von

[0, t - 1]

und somit gilt

b e s t U n t i l H e r e (t) = b e s t U n t i l H e r e (t - 1)

; (2) falls

t \in I

ist, also

I = [i, t]

, dann ist, hmmm, vielleicht

b e s t U n t i l H e r e (t) = b e s t U n t i l H e r e (t - 1) + A [t]

? Da können wir uns nur sicher sein, wenn das beste Teilinterval von

A [0, t - 1]

auch wirklich mit

t - 1

aufhört. Was nicht immer der Fall ist.

Die Lösung ist, zwei Werte zu speichern: in $B e s t U n t i l H e r e (t)$ das beste Teilinterval von $A [0, t]$ (und dazu dessen Wert {\rm bestUntilHere}; wir beginnen mit einem Großbuchstaben, um das Interval zu bezeichnen und mit einem Kleinbuchstaben für dessen Wert) und $B e s t E n d i n g H e r e (t)$ , das beste Teilinterval von $A [0, t]$ , das $t$ auch enthält (und dessen Wert $b e s t E n d i n g H e r e)$ . Sei nun $I = B e s t E n d i n g H e r e (t - 1)$ . Dann ist $B e s t E n d i n g H e r e (t)$ entweder $I \cup {t}$ oder einfach nur ${t}$ . Sei $J = B e s t U n t i l H e r e (t - 1)$ . Dann ist $B e s t U n t i l H e r e (t)$ entweder $J$ (wenn es $t$ nicht enthält) oder $I \cup {t}$ . Daher gelten die rekursiven Formeln

\begin{aligned} b e s t E n d i n g H e r e (t) & = max (b e s t E n d i n g H e r e (t - 1) + A [t], A [t]) \\ b e s t U n t i l H e r e (t - 1) & = max (b e s t U n t i l H e r e (t), b e s t E n d i n g H e r e (t)) . \end{aligned}

Jetzt müssen Sie sich nur noch überlegen, wie Sie diese beiden Werte für $t = 0$ initialisieren müssen. Dann können Sie mittels Dynamic Programming den Wert $B e s t U n t i l H e r e (n)$ berechnen.

Übungsaufgabe 2.3.5 Zeigen Sie, wie man das Problem aus der letzten Übungsaufgabe effizient parallel berechnen kann! Erfinden Sie nicht das Rad neu sondern formulieren Sie das als Parallelpräfixproblem mit einer passenden Verknüpfung $\circ$ . Überlegen Sie sich: welche Werte müssen Sie für ein Interval $[i, j]$ (analog zu Carry Propagate und Carry Generate) speichern?

Übungsaufgabe 2.3.6 (Reguläre Sprachen und parallele Berechnung). Erinnern Sie sich an reguläre Sprachen, die wir in Theoretische Informatik II, Kapitel 4 kennengelernt haben. Dort haben wir auch gesehen, dass jede reguläre Sprache durch einen endlichen Automaten entschieden werden kann. Hier ein Beispiel für einen endlichen Automaten:

Geben Sie einne effizienten parallelen Algorithmus für das Wortproblem in regulären Sprachen! Also einen Algorithmus, der, gegeben ein Eingabewort $w \in Σ^{*}$ , entscheidet, ob $w \in L$ ist, wobei $L$ eben die reguläre Sprache ist, um die es geht.

Hinweis: überlegen Sie sich wieder, welche Werte Sie in Analogie zu Carry Propagate und Carry Generate für ein Interval

I = [i, j]

berechnen müssen und finden Sie die passende Operation

\circ