2. Klassische parallele Algorithmen

Kennen Sie diese Art von Mathematik-Aufgaben:

Es ist nicht völlig unrealistisch, dass sie es zu zweit schneller schaffen, vielleicht sogar in ungefähr 16 Stunden. Bei vier Malern könnten wir eventuell mit 8 Stunden rechnen. Wie lange würden 320 Maler brauchen? 32 Stunden geteilt durch 320 ergeben eine Zehntelstunde, also 6 Minuten. Es ist wohl jedem klar, dass das nicht realistisch ist. Dennoch: das Streichen von Wänden ist eine Tätigkeit, die recht gut parallelisierbar ist. Wie sieht es dagegen mit der folgenden Ausgabe aus:

Wahrscheinlich deutlich mehr als eine halbe Stunde. Das Backen einer Torte hat einen inhärent sequentiellen Charakter. Gewisse Schritte müssen eine feste Reihenfolge einhalten (man kann den Teig nicht rühren und gleichzeitig im Ofen backen).

In diesem Kapitel wollen wir untersuchen, welche Berechnungsaufgaben (im Gegensatz zu handwerklichen oder kulinarischen Aufgaben) sich gut parallelisieren lassen. Statt Malern oder Bäckern werden wir es mit Prozessoren zu tun haben, und statt Kuchen und Wohnungswänden mit Arrays, Listen, Graphen und Matrizen. Ganz allgemein:

Das hängt sehr von der Aufgabe ab. Wenn es z.B. darum geht, in einem Array aus $n$ Zahlen das Minimum zu finden, dann könnten sich die beiden Rechner die Aufgabe perfekt aufteilen und sie in $t/2$ Zeiteinheiten lösen. Etwas mehr, weil danach ja die beiden Teilminima kommuniziert und verglichen werden müssen. Wenn dies eine Einheit benötigt, sind wir nach insgesamt $t/2+1$ Einheiten fertig. Bei anderen Problemen können wir vielleicht gar nichts parallelisieren und auch mit vielen Rechnern die Aufgabe nicht schneller als in $t$ Zeiteinheiten lösen. In diesem Kapitel werden wir untersuchen, für welche Probleme wir gute parallele Algorithmen finden können.