Amdahlsches Gesetz: Speedup und Effizienz

Amdahls Gesetz, formuliert vom Computerarchitekten Gene Amdahl im Jahr 1967, beschreibt den theoretischen Speedup, der durch die Parallelisierung einer Berechnung auf mehrere Prozessoren erreichbar ist. Es ist eines der wichtigsten und am häufigsten zitierten Prinzipien im Parallelrechnen, weil es eine harte Obergrenze für die Leistungsgewinne setzt, die zusätzliche Prozessoren liefern können — ganz gleich, wie viele Sie hinzufügen. Das Gesetz beginnt mit einer einfachen Beobachtung: Jedes reale Programm besteht aus zwei Teilen. Ein Teil ist inhärent seriell — er muss sequentiell ausgeführt werden, weil jeder Schritt vom Ergebnis des vorherigen abhängt. Der andere Teil ist parallelisierbar — er kann in unabhängige Aufgaben zerlegt und gleichzeitig auf mehreren Prozessoren ausgeführt werden. Amdahls Gesetz formalisiert das Verhältnis zwischen diesen beiden Teilen. Die Formel lautet: S(n) = 1 / (p + (1 − p) / n), wobei S der Speedup ist, p der Anteil des Programms ist, der seriell laufen muss (zwischen 0 und 1), n die Anzahl der Prozessoren und (1 − p) der parallelisierbare Anteil. Wenn n gegen unendlich wächst, nähert sich der Term (1 − p) / n dem Wert 0, und der Speedup nähert sich 1/p — dem maximalen theoretischen Speedup. Dieses Maximum wird vollständig vom seriellen Anteil bestimmt und kann unabhängig von der Prozessorzahl nicht überschritten werden. Die Konsequenzen sind erheblich. Wenn 10 % eines Programms seriell laufen müssen (p = 0.1), beträgt der maximale Speedup 1/0.1 = 10×, egal wie viele Prozessoren Sie einsetzen. Bei 20 % seriell sind es 5×. Bei 50 % seriell sind es nur 2×. Das Hinzufügen weiterer Prozessoren bringt ab einem gewissen Punkt nur noch abnehmende Erträge, weil der serielle Teil zum Engpass wird — manchmal auch als „Amdahl-Decke“ bezeichnet. Ein konkretes Beispiel: Ein Programm benötigt auf einem einzelnen Kern 3.600 Sekunden, wobei 80 % der Arbeit parallelisierbar sind (p = 0.2). Mit 8 Prozessoren ist der Speedup S(8) = 1 / (0.2 + 0.8/8) = 1 / (0.2 + 0.1) = 1 / 0.3 = 3.33×. Die parallele Laufzeit beträgt 3600 / 3.33 = 1080 Sekunden. Mit 16 Prozessoren ist S(16) = 1 / (0.2 + 0.8/16) = 1 / (0.2 + 0.05) = 4×, und die Zeit sinkt auf 900 Sekunden. Die Verdopplung von 8 auf 16 Prozessoren verbessert die Leistung nur um 20 %, weil die seriellen 20 % dominieren. Parallele Effizienz ist der Speedup geteilt durch die Anzahl der Prozessoren, ausgedrückt in Prozent: E = S(n)/n × 100 %. Sie misst, wie gut jeder zusätzliche Prozessor genutzt wird. Eine perfekte Effizienz (100 %) würde bedeuten, dass jeder Prozessor vollständig ausgelastet ist — ein theoretisches Ideal. In der Praxis sinkt die Effizienz mit mehr Prozessoren, weil der serielle Anteil Prozessorzeit verschwendet. Fällt die Effizienz unter 50 %, kostet das Hinzufügen weiterer Prozessoren in Hardware mehr, als es an Zeit spart. Amdahls Gesetz nimmt an, dass der serielle Anteil p unabhängig von der Problemgröße konstant bleibt. Gustafsons Gesetz (1988) bietet eine ergänzende Perspektive: Bei größeren Problemgrößen wird ein größerer Anteil der Arbeit parallelisierbar, und die Effizienz bleibt bei steigender Prozessorzahl höher. Zusammen ergeben die beiden Gesetze ein vollständiges Bild des parallelen Skalierens — Amdahls Gesetz ist pessimistisch, beschreibt aber das Szenario mit fester Problemgröße sehr genau, während Gustafsons Gesetz optimistischer ist und gilt, wenn die Problemgröße mit der Prozessorzahl wächst. Praktische Anwendungen von Amdahls Gesetz sind CPU- und GPU-Architekturdesign, Cloud-Ressourcenplanung, Algorithmusanalyse für High-Performance-Computing und die Schätzung des Nutzens zusätzlicher Prozessoren in bestehenden Systemen. Den seriellen Anteil einer Berechnung zu identifizieren und zu reduzieren — durch bessere Algorithmen, weniger Synchronisationsaufwand oder neu gestaltete Datenstrukturen — ist der effektivste Weg, Amdahls Decke anzuheben.