De wet van Amdahl

Ik leid hier de wet van Amdahl af. Dat doe ik na het lezen van een interview met Brian Goetz in Java Magazine. Een kader toonde de wet als een formule zonder uitleg. Dit prikkelde mij om de uitleg erbij te vinden.

In de maart editie van Java Magazine zag ik een formule. Deze formule vat de wet van Amdahl samen. Deze wet vertelt hoeveel sneller een programma door parallelisatie wordt als het maar ten delen kan worden geparalleliseerd.

Na enig nadenken begreep ik hoe de formule tot stand komt. Dit gaf mij veel meer inzicht dan de formule. Hieronder vind je mijn gedachtengang.

Afleiding
Een programma heeft een hoeveelheid werk te verrichten. We noemen deze hoeveelheid W. De snelheid van de processor bepaald hoelang het programma over deze hoeveelheid werk doet. De tijd T wordt gegeven door

T = W / v

v is hier de processorsnelheid.

Er wordt aangenomen dat een bepaald deel van het programma niet te paralleliseren is. Dus de totale hoeveelheid werk W bestaat uit een serieel deel en een parallel deel.
Noem die verhouding van het parallele deel ten opzichte van het geheel p. Dus

p = W_parallel / W

zodat W_parallel = pW en W_serieel = (1-p)W.

De tijd T’ die het parallele programma nodig heeft om de hoeveelheid werk te verrichten is op een zelfde manier opgebouwt uit een serieel deel en een parallel deel.

T’ = T_serieel + T_parallel

Aan het serieele werk kan maar een processor tegelijk werken. De tijd is daarom

T_serieel = W_serieel / v = (1-p)W / v

Het parallele deel kan echter over N aantal processoren verdeeld worden. Het werk dat een processor moet uitvoeren wordt zo N keer kleiner. Daardoor wordt

T_parallel = W_parallel / N v = pW / N v

zodat

T’ = T_serieel + T_parallel = (1-p)W / v + pW / N v = ((1-p) + p / N) W / v

De verhouding T en T’ komt zo tot

De wet van Amdahl

De wet van Amdahl

Discussie
Ik begrijp niet zo goed waarom het stuk de formule toonde. De wet van Amdahl speelt maar een zijdelingse rol in het interview. Daar word alleen een gevolg van de wet van Amdahl genoemd.

Ik begrijp dat een auteur een verduidelijking van de wet van Amdahl wil aangeven. Ik vraag mij alleen af of dat op deze manier is bereikt. Een afleiding verduidelijkt meer dan een formule. Of ben ik daar de enige in?