Brent’s theorem habe ich wirklich lange anschauen müssen, bis ich es einigermaßen verstanden habe. Ich werde daher für alle anderen, denen es mit Brent’s theorem vielleicht ähnlich geht, versuchen eine anschauliche Erklärung zu liefern.
Wie viele andere Erkenntnisse aus dem Bereich parallel computing ist das Theorem von Brent noch nicht sehr alt – 1974 stellt er es auf.
Die Aussage selber ist sehr kurz:
Ein beliebiger Parallelalgorithmus mit der Berechnungszeit t, der m Operationen ausführt, kann auf p Prozessoren in der Zeit t + (m-t)/p ausgeführt werden.
Immer gut, wenn man wichtige Aussagen knapp formulieren kann – aber was bedeutet Brents theorem nun?
Wichtig für das Verständnis des Satzes ist zum einen das Wissen, dass die Ausführung von einer PRAM Maschine, also einem Parallelrechner durchgeführt wird, und zum anderen die Erklärung der Berechnungszeit t.
Die Berechnungszeit wird dabei allgemein in Zeitschritte eingeteilt. In jedem Zeitschritt werden alle Befehle ausgeführt, die von keinen anderen Befehlen abhängig sind.
t ist dabei dann die längste Befehlsfolge, die von anderen Befehlen abhängig ist. (Alle kürzeren Befehlsfolgen sind ja bereits parallel bearbeitet und beendet worden)
Beispiel:
Wir haben ein Array mit 10 Werten, die aufsummiert werden sollen.
Jetzt könnte man so vorgehen:
position = start; while (position < 10) { ergebnis = ergebnis + array(position); position = position+1;}
Dabei hängt nun jede Berechnung von dem Ergebnis der vorigen Berechnung ab!
t ist damit also 10.
Die Gesamtzahl der Operationen ist auch 10, also ist auch m = 10.
Mit Brent’s Theorem berechnen wir also:
T = 10 + 0/p, es ist also möglich auf einer Parallelmaschine in 10 Zeiteinheiten das Array aufzusummieren. Wäre auch schrecklich wenn es nicht ginge, man kann von der Parallelmaschine ja einfach nur einen Prozessor nutzen, und sequentiell arbeiten.
Brents theorem besagt nicht:
- Es gibt keinen besseren Algorithmus für das Problem
- Es gibt keine bessere Implementierung für den Algorithmus
- Eine entsprechende Implementierung ist leicht zu finden
Aber mit dem Theorem von Brent kann man zeigen, dass eine entsprechende Implementierung existiert!
Jetzt versuchen wir mal die Array-Summe anders zu bilden, da Addieren assoziativ ist, könnte man die Summenbildung parallelisieren.
Wir zerteilen das Array in Summen aus je zwei Elementen:
1+2, 3+4, 5+6, 7+8, 9+10
Das geht – auf der Parallelmaschine – in einem Zeitschritt!
Die Ergebnisse bearbeiten wir nochmals so:
3+7, 11+15, 19
Wieder ein Zeitschritt. Und nochmal:
10 + 26, 19
36 + 19 = 55
Und das in nur 4 Zeitschritten! Durch die Parallelisierung ist das wesentlich schneller.
Etwas formaler: Dieser Algorithmus hat für ein Array mit n Elementen log(n) Schritte, also t= log(n). m – die „Gesamtarbeit“ – ist wieder n.
Die Zeit nach Brent’s Theorem ist somit T = log(n) + (n – log(n) ) /p.
Wichtig in diesem Zusammenhang ist noch die Frage nach der Kosteneffizient oder Kostenoptimalität:
- Egal wie viele Prozessoren wir parallel arbeiten lassen, es geht nicht schneller als O (log n)
- Bei n Prozessoren benötigen wir log(n) Zeit
- Bei log(n) Prozessoren benötigen wir log(n) + log(n) Zeit – das ist aber wieder O (log n)
- Mit einem Prozessor benötigen wir n Zeitschritte
Die Arbeitsleistung wird jetzt so ausgerechnet:
Anzahl der Prozessoren mal der geleisteten Arbeit, also
- Ein Prozessor: 1 * n
- log(n) Prozessoren: log(n) * n
- n Prozessoren: n*n
Kostenoptimal ist ein Algorithmus, wenn er nicht mehr Kosten verursacht als ein äquivalenter sequentieller Algorithmus. Mit n Prozessoren ist man somit nicht mehr Kosteneffizient!
Neue Kommentare