2.1 Beispiele: Summen bilden, Minimum berechnen

Kommen wir nochmal auf das Problem zurück, welches ich im letzten Teilkapitel kurz angerissen hatte: in ein Array aus $n$ Zahlen das Minimum zu bilden. Ein sequentieller Algorithmus ist schnell gefunden:

    public int computeMin(int[] array) {
        int n = array.length;
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (result > array[i])
                result = array[i];
        }
        return result;
    }                        

Für ein Array aus $n$ Elementen benötigt dieser Algorithmus $n$ "Schritte". Die Scare Quotes habe ich eingefügt, weil wir uns nicht wirklich verständigt haben, was ein Schritt ist. Wenn wir jeden Prozessorschritt zählen, also z.B. Inkrementieren des Zählers i, Vergleich i < n, Laden des Array-Elementes, Vergleich mit result, sowie Initialisieren von n und result, das return-Statement, sowie Verwaltung von Stack-Pointer und Program-Counter, dann kommen wir vielleicht auf $4n+5$ Schritte oder $6n+3$ oder was auch immer. In jedem Fall auf $\mathrm{\Theta }(n)$ Schritte. Da die $O/\mathrm{\Theta }/\mathrm{\Omega }$-Notation im Folgenden aber etwas störend ist, sage ich jetzt einfach, dass mein Algorithmus computeMin oben $n$ Makroschritte ausführt, wobei jeder Makroschritt dann aus $O(1)$ vielen Mikroschritten besteht.

Minimum finden mit vier Prozessoren

Im folgenden schauen wir uns an, wie man mit vier Prozessoren das Minimum schneller bestimmen kann. Ich formalisiere noch nicht, wie diese Prozessoren arbeiten und wie sie kommunizieren. Das alles kann warten.

Unser paralleler Algorithmus benötigt auf diesem Array von 16 Elementen insgesamt 19 Schritte aber nur 6 Zeitschritte, da viele Schritte parallel ablaufen. Verallgemeinern wir:

Beliebig viele Prozessoren

Machen wir einen radikalen Gedankensprung und stellen uns vor, wir hätten beliebig viele Prozessoren. Seien wir mal ganz verschwenderisch und lassen jeden Prozessor nur einen Schritt ausführen. Wie sähe dann die Berechnung des Minimums aus?

In meiner graphischen Darstellung ist jeder Kreis ein separater Prozessor, der genau einen Schritt ausübt und danach inaktiv wird.

Wir haben also bereits zwei Komplexitätsmaße, die uns interessieren: Erstens die Anzahl der Arbeitsschritte; dies bezeichnen wir im Folgenden einfach als Arbeit. Zweitens die Anzahl der Zeitschritte; diese bezeichnen wir als parallele Zeit oder einfach als Zeit.

Wirklich beliebig viele Prozessoren?

Ich habe im vorherigen Beispiel $2n-1$ Prozessoren verwendet, um das Minimum zu berechnen. Dies verstößt gegen einen Grundsatz, den ich im Kurs Theoretische Informatik II gepredigt habe: die "Bauweise" unserer Rechenmaschine muss unabhängig sein von der Größe des Inputs. Wir wollen einen Algorithmus, der für alle möglichen Eingaben funktioniert. Eine Maschine, deren Prozessorenanzahl mit der Datenmenge wachsen darf, so wie ich sie oben entworfen habe, ist nicht realistisch. Ich reagiere auf diese Kritik auf dreierlei Art.

1. Es ist nicht unrealistisch. Heutzutage werden in Rechenzentren dynamisch neue Rechner dazugekauft. Die Anzahl der Prozessoren (oder in diesem Fall besser: die Anzahl der Rechner) wächst also in der Tat mit der Datenmenge. Diese moderne Sichtweise und das davon inspirierte Modell für paralleles Rechnen werden wir in Kapitel 4 kennenlernen.
2. Auch wenn die Anzahl der Prozessoren auf einem Rechner realistisch gesehen nicht mit der Datenmenge wachsen kann (sondern zum Zeitpunkt der Herstellung feststehen muss), so ist es als Modellierungsmodell vielleicht doch sinnvoll. Und in der Tat haben wir in Kapitel 1 von Theoretische Informatik II so ein Modell kennengelernt: die Booleschen Schaltkreise. Sicherlich wird Ihnen nicht entgangen sein, dass der Binärbaum im obigen Beispiel sehr einem Schaltkreis ähnelt, nur dass die Gates keine Booleschen Werte bearbeiten, sondern ganze Zahlen. In der Tat werfen wir in Kapitel 2.2 einen Rückblick auf Boolesche Schaltkreise.
3. Beliebig viele Prozessoren anzunehmen ist zwar unrealistisch, spielt aber keine Rolle, weil man die Zahl der Prozessoren problemlos reduzieren kann. Das muss ich näher erläutern. Wenn ich Ihnen einen sequentiellen Algorithmus gebe (also mit einem Prozessor), dann ist es nicht klar, ob und wie man ihn modifizieren kann, so dass er mit $p$ Prozessoren circa $p$ mal so schnell läuft. Wenn ich Ihnen allerdings einen parallelen Algorithmus erkläre, der $p$ Prozessoren verwendet und $t$ Zeitschritte macht, dann kann ich ihn mit $p/k$ Prozessoren in circa $t\cdot k$ Zeitschritten implementieren: jeder "neue" Prozessor $P$ macht einfach sequentiell die Arbeit von $k$ "alten" Prozessoren (wie genau das geht, sehen wir in den nächsten Teilkapiteln). Dies ist als Brent's Principle bekannt. Da wir also immer (fast) kostenlos die Anzahl der Prozessoren reduzieren können, sind wir beim Entwurf eines Algorithmus also so verschwenderisch wie möglich.