/ Performance & Benchmarking

Amdahls Gesetz (Speedup)

Maximaler Speedup durch Parallelisierung: S = 1 / ((1 − p) + p / n). p = parallelisierbarer Anteil, n = Prozessoren. Der serielle Rest begrenzt den Speedup.

01 · Eingabe

Amdahls Gesetz (Speedup) berechnen

Maximaler Speedup durch Parallelisierung: S = 1 / ((1 − p) + p / n). p = parallelisierbarer Anteil, n = Prozessoren. Der serielle Rest begrenzt den Speedup.

Lösen für

S = 1 / ((1 − p) + p / n)

p Paralleler Anteil

n Prozessoren

Worum geht es?

Amdahls Gesetz beschreibt die theoretische Obergrenze für den Speedup, den Du durch Parallelisierung erreichen kannst — bei fester Problemgröße. Entscheidend ist der serielle Anteil (1 − p), der nicht parallelisiert werden kann.

Selbst mit unendlich vielen Prozessoren ist der Speedup durch 1 / (1 − p) begrenzt. Bei nur 10 % seriellem Anteil liegt die Obergrenze schon bei 10 — egal wie viele Cores Du hinzufügst. Das ist die ernüchternde Botschaft von Amdahl: Parallelisierung lohnt sich vor allem, wenn der serielle Anteil winzig ist.

Die Formel

Formel Amdahls Gesetz

S = 1 / ((1 − p) + p / n)

Umstellung:
    n = p / (1/S − (1 − p))

Grenzwert:
    lim (n → ∞) S = 1 / (1 − p)

Die Variablen

Symbol	Bedeutung	Erklärung
p	Paralleler Anteil	Parallelisierbarer Anteil (0–1).
n	Prozessoren	Anzahl Prozessoren.
S	Speedup	Faktor, um den das Programm schneller wird.

Minimal-Beispiel

p = 0,8 (80 % parallelisierbar), n = 4 Prozessoren.

Rechnung Speedup

S = 1 / (0,2 + 0,8 / 4)
  = 1 / (0,2 + 0,2)
  = 2,5

Praxis-Beispiele

Beispiel 1 — Obergrenze bei vielen Cores

p = 0,95, n = 32.

Rechnung Speedup

S = 1 / (0,05 + 0,95 / 32)
  = 1 / (0,05 + 0,0297)
  ≈ 12,55

Beispiel 2 — Asymptote

Theoretisches Maximum bei p = 0,9.

Rechnung Grenzwert

S_max = 1 / (1 − 0,9)
      = 10

Beispiel 3 — Benötigte Prozessoren

Wie viele Prozessoren sind nötig, um bei p = 0,9 einen Speedup von 6 zu erreichen?

Rechnung Prozessoren

n = 0,9 / (1/6 − 0,1)
  = 0,9 / (0,0667)
  ≈ 13,5  ⇒ 14 Prozessoren