Parallele Algorithmen

In diesem Kapitel geht es um den Einsatz nicht nur eines, sondern vieler Prozessoren zur Lösung eines Problems. Es wird dabei von dem Modell einer PRAM (Parallel Random Access Machine) ausgegangen, bei der jeder Prozessor einen lokalen Speicherplatz besitzt, und außerdem noch ein gemeinsamer Speicher existiert. Ein Rechenschritt einer PRAM geht dann wie folgt vor sich:

Einlesen eines Datums vom gemeinsamen Speicher in den lokalen Speicher (Lesephase)
Durchführung der (konstant vielen) Rechenoperationen (Rechenphase)
Schreiben eines Datums vom lokalen Speicher in den gemeinsamen Speicher (Schreibphase)

In Bezug auf die Lese- und Schreibzugriffe kann man eine PRAM in unterschiedliche Klassen einteilen: Eine CR-PRAM (Concurrent Read) erlaubt gleichzeitige Lesezugriffe, eine CW-PRAM (Concurrent Write) erlaubt gleichzeitige Schreibzugriffe. Im Gegensatz dazu spricht man von einer ER- (Exclusive Read) bzw. EW-PRAM (Exclusive Write), wenn keine gleichzeitigen Lese- bzw. Schreibzugriffe erlaubt sind.

Es stellt sich nun die Frage, ob die entsprechend größere Anzahl an Prozessoren in einem angemessenen Verhältnis zum Zeitgewinn steht. Dazu bezeichne im Folgenden $t_{s}(n)$ die sequentielle und $t_{p}(n)$ die parallel Laufzeit, sowie die Anzahl der Prozessoren bei der parallelen Berechnung. Dann definiert man

die Arbeit als $w_{p}(n) := t_{p}(n) * p(n)$ ,
die Effizienz als $\frac{\rule[-1mm]{0mm}{1mm}{Arbeit sequentiell}{\rule{0mm}{4mm}{Arbeit parallel}$ und
den Speedup als $\frac{\rule[-1mm]{0mm}{1mm}{Laufzeit sequentiell}{\rule{0mm}{4mm}{Laufzeit parallel}$ .

Man nennt einen parallelen Algorithmus

optimal, wenn gilt: $t_{p}(n) = O(\log^k \, n) .AND. }w_{p}(n) = O(t_{s}(n))$
effizient, wenn gilt: $t_{p}(n) = O(\log^k \, n) .AND. }w_{p}(n) = O(t_{s}(n) * \log^k \, n)$

In der Vorlesung wurde die parallele Minimum-Berechnung und die parallele Präfixsummen-Berechnung genauer besprochen, worauf hier nicht näher eingegangen wird (bei Interesse möge das Skriptum studiert werden).