Geben Sie den parallelisierbaren Anteil eines Programms und die Anzahl der Prozessoren (Kerne) ein, um zu sehen, wie stark sich das gesamte Programm nach dem Amdahlschen Gesetz beschleunigt. Ein doppelt logarithmisches Diagramm vergleicht diese Grenze bei fester Problemgröße mit der Sicht von Gustafson, bei der das Problem mit der Prozessorzahl wächst.
Ergebnisse
Beschleunigung (Amdahlsches Gesetz)
–
Parallele Effizienz
–
Obergrenze der Beschleunigung 1/(1−p)
–
Skalierte Beschleunigung (Gustafsons Gesetz)
–
Die dünne gestrichelte Linie ist die ideale lineare Beschleunigung (N-fach), die blaue Linie das Amdahlsche Gesetz und die grüne Linie Gustafsons Gesetz. Beide Achsen sind logarithmisch. Overhead durch Kommunikation, Synchronisation und Lastungleichgewicht ist nicht berücksichtigt, reale Beschleunigungen fallen daher meist geringer aus.
Als Diagramm ansehen
Die übrigen Eingaben bleiben auf ihren aktuellen Werten, während die gewählte Eingabe zwischen dem 1/4- und 4-Fachen ihres aktuellen Werts variiert. Der rote Punkt ist der aktuelle Wert.
Die Formel des Amdahlschen Gesetzes
Man setzt die Laufzeit auf einem Prozessor gleich 1 und bezeichnet mit p den parallelisierbaren Anteil. Mit N Prozessoren schrumpft der parallele Teil auf p/N, der serielle Teil (1 − p) bleibt jedoch gleich, sodass die Beschleunigung S = 1/((1 − p) + p/N) beträgt. Wie groß N auch wird, der serielle Teil verschwindet nie, daher ist die Beschleunigung auf 1/(1 − p) begrenzt. Mit den Standardwerten p = 95 % und N = 16 ergibt sich S ≈ 9,14, und die Obergrenze liegt bei 20. Schon 5 % serielle Arbeit entscheiden darüber, wie schnell das Programm überhaupt werden kann.
Effizienz und Diagramm richtig lesen
Die parallele Effizienz E = S/N zeigt, wie viel nützliche Arbeit jeder Prozessor leistet. Mit den Standardwerten beträgt sie 9,14 ÷ 16 ≈ 57,1 %, mehr als 40 % der Rechenkapazität liegen also faktisch brach. Im Diagramm folgt die blaue Linie bei kleinem N der gestrichelten Ideallinie, biegt dann ab und flacht zur Obergrenze hin ab. Bleibt p = 95 % und steigt N auf 64, ergibt sich S ≈ 15,4 bei einer Effizienz von nur etwa 24 %. Der Punkt, ab dem die Effizienz rasch sinkt, ist ein praktischer Anhaltspunkt dafür, wie viele Prozessoren ihre Kosten wert sind.
Worin sich Gustafsons Gesetz unterscheidet
Das Amdahlsche Gesetz geht von einer festen Problemgröße aus, während Prozessoren hinzukommen; man spricht von Strong Scaling. Gustafsons Gesetz lässt dagegen das Problem mit der Prozessorzahl wachsen und löst es in derselben Zeit, was als schwache Skalierung (Weak Scaling) bezeichnet wird, und liefert S = (1 − p) + p·N. Wird zum Beispiel das Gitter einer Simulation verfeinert, wächst nur die parallele Arbeit, sodass die Beschleunigung nahezu proportional zu N steigt. Beachten Sie, dass p hier der Zeitanteil ist, der beim Lauf auf N Prozessoren gemessen wird, und damit anders definiert ist als das p im Amdahlschen Gesetz.
Anwendung in realen Designs
In realen Programmen kommen Thread-Start, Datenkommunikation, Warten an Locks und Barrieren sowie Lastungleichgewicht hinzu, daher bleiben die tatsächlichen Beschleunigungen unter der Vorhersage des Amdahlschen Gesetzes. Den seriellen Teil zu verkleinern ist oft wirksamer, als Kerne hinzuzufügen; üblich ist es daher, zuerst zu profilieren und dann die Hotspots zu parallelisieren. Auf GPUs wirken auch Datentransfers vom und zum Host sowie Kernel-Starts als serielle Anteile. Im Chipdesign ist die Kombination weniger Hochleistungskerne mit vielen kleinen Kernen ein Weg, sowohl den seriellen als auch den parallelen Teil einer Last zu beschleunigen.
Die Zeit nach der Verbesserung ist die Summe aus den übrigen, nicht beschleunigten 50 % (0,5) und den 4-fach beschleunigten 50 % (0,5 ÷ 4 = 0,125), also 0,625. Der Speedup beträgt 1 ÷ 0,625 = 1,6. Egal wie stark der beschleunigte Teil verbessert wird, bleiben die übrigen 50 % bestehen, sodass das Ganze höchstens 2-fach schneller werden kann. Um das Ganze stark zu beschleunigen, müssen Teile gefunden und verbessert werden, die viel Zeit beanspruchen.
AVorrang hat die Beschleunigung der Teile, die viel Zeit beanspruchen (der häufige Fall)
BZuerst werden Teile beschleunigt, die nur selten ausgeführt werden
CEgal welcher Teil beschleunigt wird, der Effekt auf das Ganze ist gleich
Antwort und Erläuterung anzeigen
Antwort: A. Vorrang hat die Beschleunigung der Teile, die viel Zeit beanspruchen (der häufige Fall)
Wird ein Teil, der nur 1 % des Ganzen beansprucht, unendlich beschleunigt, wird das Ganze nur um etwa 1 % schneller. Wird dagegen ein Teil mit 80 % Anteil 2-fach beschleunigt, wird das Ganze etwa 1,7-fach schneller. Grundsätzlich werden daher zuerst mit einem Profiler die zeitintensiven Teile gefunden und von dort aus verbessert. „Make the common case fast“ ist ein auch im Computerentwurf immer wieder genutzter Grundsatz.
AWird bei steigender Prozessorzahl auch die Problemgröße erhöht, wächst der parallelisierbare Anteil, und es ergibt sich ein großer Speedup
BEgal wie stark die Prozessorzahl erhöht wird, ist der Speedup auf höchstens 2 begrenzt
CDer parallelisierbare Teil ist unabhängig von der Problemgröße stets konstant
Antwort und Erläuterung anzeigen
Antwort: A. Wird bei steigender Prozessorzahl auch die Problemgröße erhöht, wächst der parallelisierbare Anteil, und es ergibt sich ein großer Speedup
Das Amdahlsche Gesetz betrachtet steigende Prozessorzahl bei unveränderter Problemgröße, sodass der nicht parallelisierbare Teil die Obergrenze des Speedup bestimmt. Das Gustafsonsche Gesetz geht davon aus, dass mit mehr Prozessoren in gleicher Zeit ein größeres Problem gelöst wird. Wird das Problem größer, etwa durch ein feineres Gitter bei Simulationen, wächst der parallele Teil, der Anteil des sequenziellen Teils sinkt, und es ergibt sich ein Effekt nahezu proportional zur Prozessorzahl.
Die parallele Effizienz ist der Speedup geteilt durch die Kernzahl und gibt an, wie wirksam die Kerne genutzt werden. Wegen 6 ÷ 8 = 75 % wird gegenüber dem Ideal (8-fach) drei Viertel des Effekts erzielt. Die übrigen 25 % gehen durch Warten auf Synchronisation, Lastungleichgewicht, Kommunikation und Konkurrenz um Speicherbandbreite verloren. Da die parallele Effizienz mit steigender Kernzahl tendenziell sinkt, wird die zu nutzende Kernzahl danach gewählt, wie weit die Effizienz gehalten werden kann.
Häufige Fragen
Wie viel schneller kann ein zu 90 % paralleles Programm werden?
Nach dem Amdahlschen Gesetz liegt die Grenze beim 1/(1 − 0,9) = 10-Fachen. Selbst mit 16 Prozessoren beträgt die Beschleunigung nur 1/(0,1 + 0,9/16) = 6,4, eine Effizienz von 40 %. Solange die verbleibenden 10 % serielle Arbeit nicht verringert werden, kann die Beschleunigung niemals 10 überschreiten.
Widersprechen sich das Amdahlsche Gesetz und Gustafsons Gesetz?
Nein. Das Amdahlsche Gesetz beschreibt Strong Scaling mit fester Problemgröße, Gustafsons Gesetz dagegen Weak Scaling, bei dem das Problem mit der Prozessorzahl wächst. Welche Sicht zutrifft, hängt davon ab, ob Sie dasselbe Problem schneller oder ein größeres Problem in derselben Zeit lösen wollen.
Kann die parallele Effizienz 100 % übersteigen?
Ja. Wenn durch zusätzliche Prozessoren der Datenanteil jedes Prozessors so klein wird, dass er in dessen Cache passt, werden Speicherzugriffe schneller, und es kann eine superlineare Beschleunigung auftreten. Das Amdahlsche Gesetz bildet solche Effekte nicht ab.