De wet van Amdahl

 
23 maart 2009

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?


Werken met ?
Kijk dan bij onze mogelijkheden voor starters en/of ervaren IT'ers.


Categorieën: Development

Tags: , , , ,


Reacties (8)

  • Johan Scholten schreef:

    @Thomas:
    Linkje: http://en.wikipedia.org/wiki/Amdahl%27s_law
    De formule is dus niet alleen voor parallellisatie van toepassing.
    En ik denk niet dat die overhead wordt meegenomen. In het optimale geval is die namelijk zo klein mogelijk, dus richting 0. En daar geldt deze wet voor.

    (en ik weet dat ik het over supralineaire versnelling had. Maar als er een geval is waarvoor de formule niet geldt, kan de formule nooit bewezen worden :)

    Geplaatst op 28 maart 2009 om 17:22 Permalink

  • Thomas Zeeman schreef:

    Als je de formule zo ziet, dan lijkt deze inderdaad erg indrukwekkend. Het is echter als veel wiskundige formules, gebruik wat vreemde, liefst Griekse, tekens en de gemiddelde ‘leek’ wordt er enorm door afgeschrikt. Dit lijkt dan ook wel op het imponeren dat hierboven al een paar keer is aangehaald.

    Om nog iets verder op de betekenis van de Wet van Amdahl in te gaan. Die is vooral handig om te bepalen of een bepaalde berekening door parallelliseren ook echt sneller een uitkomst kan opleveren en bij hoeveel processoren je dan het optimum bereikt.
    Bij het opdelen van een probleem in subproblemen, treed namelijk een stukje niet parallelliseerbare overhead op. Iemand moet het werk verdelen en daarna weer aan elkaar plakken. Daarbij zie je dan ook dat hoe meer processoren je er tegenaan gooit, de T_serieel steeds meer zal toenemen en T_parallel steeds minder zal afnemen.
    Hoeveel die T’s toe- of afnemen is dan weer afhankelijk van o.a. het probleem dat je wil paralleliseren, de manier waarop je dat probeert te doen en de processoren die je er bij gebruikt.
    Dat is alleen weer iets dat in deze formule niet meeweegt.
    Waar deze formule je wel bij kan helpen is het vinden van de grens en het optimum van de parallelliseerbaarheid van je probleem, bovenstaande beperkingen in acht nemend.

    @Johan: wat je beschrijft is supra lineaire versnelling bij parallelliseerbare problemen. Een zeldzaam verschijnsel en meestal veroorzaakt door de grootte van de data die bij het opknippen opeens wel in sneller geheugen past dan daarvoor en daardoor opeens ordes van grootte sneller benaderbaar is. Niet iets wat je deze formule kan aanrekenen naar mijn mening.

    Geplaatst op 25 maart 2009 om 19:02 Permalink

  • Daan Wanrooy schreef:

    @Johan

    Je maakt een goed punt dat iedere formule in een bepaalde context gebruikt moet worden. De context, en de nuances die jij aanbrengt, werden uit het kader niet duidelijk.

    Geplaatst op 24 maart 2009 om 10:54 Permalink

  • Johan Scholten schreef:

    Helemaal mee eens, niet al te moeilijke formule.

    En voor zover ik weet klopt hij ook niet helemaal.
    Wat ik me nog herinner, is het parallelle deel sneller te krijgen dan p/N in uitzonderlijke gevallen, aangezien je het geheugengebruik (cache dus) per processor ook kan terugdringen door te parallelliseren, en dit is in sommige gevallen ook een grote factor.
    Als de cache gedeeld is gaat dit natuurlijk niet op.

    Maar een formule erbij lijkt inderdaad extra geloofwaardigheid te geven aan zo’n artikel. Ook al valt het achteraf in dit geval dus wel tegen..

    Geplaatst op 24 maart 2009 om 10:23 Permalink

  • Daan Wanrooy schreef:

    @Ivo @Ralf

    Ik denk dat jullie samen mijn onbegrip goed weergeven. Voor de een zegt de formule niets, voor de ander is hij flauw. In beide gevallen is de achtergrond uitleggen beter.
    Zo wordt voor iedereen duidelijk wat de wet inhoud en kunnen mensen die wat aan formules hebben er een voor vinden.

    @Rick

    Voor mij riekt dit ook een beetje naar “Veel geblaat maar weinig wol”.

    Geplaatst op 24 maart 2009 om 9:39 Permalink

  • @Daan @Ivo @Ralf

    Ik denk dat jullie samen de oplossing hebben:
    Daan: waarom staat die formule daar?
    Ivo: poeh een formule, zal wel ingewikkeld zijn..
    Ralf: valt wel mee, als je er langer naar kijkt.

    Waarschijnlijk wilde de schrijver met een niet heel relevante en eigenlijk vrij simpele formule indruk maken op de lezers..

    Geplaatst op 24 maart 2009 om 9:29 Permalink

  • Ralf Wolter schreef:

    Het is eigenlijk niet zo ingewikkeld. Er staat dat we de oeveelheid werk verdelen tussen parallel en niet parallel. Daarna wordt het parallel gedeelte weer verdeelt over een aantal processoren.

    Grote probleem hierbij lijkt al dat het parallel gedeellte, puur parallel moet zijn zonder overhead of de overhead moet bij het seriele gedeelte horen. Het is eigenlijk een best naive formule valt me op.

    Geplaatst op 24 maart 2009 om 8:16 Permalink

  • Ivo Limmen schreef:

    Ik voel mij zo een ontzettend grote n00b als naar die formules kijk… ik nooit echt wat begrepen van wiskunde.

    Geplaatst op 24 maart 2009 om 7:28 Permalink