Voer de fractie van een programma in die parallel kan draaien en het aantal processors (cores) om te zien hoeveel sneller het hele programma wordt volgens de wet van Amdahl. Een log-loggrafiek vergelijkt deze grens bij vaste probleemgrootte met de benadering van Gustafson, waarin het probleem meegroeit met het aantal processors.
Resultaten
Speedup (wet van Amdahl)
–
Parallelle efficiëntie
–
Maximale speedup 1/(1−p)
–
Scaled speedup (wet van Gustafson)
–
De dunne stippellijn is de ideale lineaire speedup (N keer), de blauwe lijn de wet van Amdahl en de groene lijn de wet van Gustafson. Beide assen zijn logaritmisch. Overhead door communicatie, synchronisatie en ongelijke belastingsverdeling is niet meegenomen, dus echte speedups liggen meestal lager.
Bekijk als grafiek
De andere invoerwaarden blijven gelijk, terwijl de gekozen invoer varieert van 1/4 tot 4 keer de huidige waarde. De rode stip is de huidige waarde.
De formule van de wet van Amdahl
Neem de uitvoeringstijd op één processor als 1 en laat p de fractie zijn die geparallelliseerd kan worden. Met N processors krimpt het parallelle deel tot p/N, maar het seriële deel (1 − p) blijft gelijk, dus de speedup is S = 1/((1 − p) + p/N). Hoe groot N ook wordt, het seriële deel verdwijnt nooit, dus de speedup is begrensd op 1/(1 − p). Met de standaardwaarden p = 95% en N = 16 is S ≈ 9,14 en ligt de grens op 20. Slechts 5% serieel werk bepaalt hoe snel het programma ooit kan worden.
Efficiëntie en grafiek aflezen
De parallelle efficiëntie, E = S/N, laat zien hoeveel nuttig werk elke processor doet. Met de standaardwaarden is die 9,14 ÷ 16 ≈ 57,1%, dus meer dan 40% van de rekencapaciteit staat feitelijk stil. In de grafiek volgt de blauwe lijn bij kleine N de ideale stippellijn, buigt daarna af en vlakt af richting de grens. Met p = 95% en N verhoogd naar 64 is S ≈ 15,4 en de efficiëntie slechts ongeveer 24%. Het punt waarop de efficiëntie snel begint te dalen, is een praktische richtlijn voor hoeveel processors hun kosten waard zijn.
Hoe de wet van Gustafson verschilt
De wet van Amdahl gaat uit van een vaste probleemgrootte terwijl er processors bijkomen; dat heet strong scaling (sterke schaling). De wet van Gustafson laat het probleem juist meegroeien met het aantal processors en lost het in dezelfde tijd op; dat heet weak scaling, met S = (1 − p) + p·N. Wanneer bijvoorbeeld het rooster van een simulatie wordt verfijnd, groeit alleen het parallelle werk, zodat de speedup vrijwel evenredig met N stijgt. Let op: p is hier de fractie van de tijd gemeten bij de uitvoering op N processors, wat niet dezelfde definitie is als de p in de wet van Amdahl.
Toepassing in echte ontwerpen
Echte programma's krijgen te maken met het opstarten van threads, datacommunicatie, wachten op locks en barriers, en ongelijke belastingsverdeling, zodat de werkelijke speedup onder de voorspelling van Amdahl blijft. Het seriële deel verkleinen is vaak effectiever dan cores toevoegen, dus de gebruikelijke aanpak is eerst profileren en dan de hotspots parallelliseren. Op GPU's werken ook datatransfers van en naar de host en kernel-launches als seriële delen. In chipontwerp is het combineren van een paar krachtige cores met veel kleine cores een manier om zowel het seriële als het parallelle deel van een workload te versnellen.
De tijd na de verbetering is de som van de resterende 50 % (0,5) die niet sneller wordt gemaakt en de 50 % die 4 keer zo snel is geworden (0,5 ÷ 4 = 0,125), dus 0,625. De versnelling is 1 ÷ 0,625 = 1,6 keer. Hoe sterk het versnelde deel ook wordt versneld, de resterende 50 % blijft bestaan, zodat de totale versnelling hoogstens 2 keer kan bedragen. Om het geheel sterk te versnellen moet het deel dat veel tijd kost worden gevonden en verbeterd.
APrioriteit geven aan het versnellen van het deel dat veel tijd kost (het veelvoorkomende geval)
BEerst de zelden uitgevoerde delen versnellen
CHet effect op het geheel is hetzelfde, welk deel ook wordt versneld
Antwoord en toelichting tonen
Antwoord: A. Prioriteit geven aan het versnellen van het deel dat veel tijd kost (het veelvoorkomende geval)
Als een deel dat slechts 1 % van het geheel beslaat oneindig snel wordt gemaakt, wordt het geheel slechts ongeveer 1 % sneller. Wordt daarentegen een deel dat 80 % beslaat 2 keer zo snel gemaakt, dan wordt het geheel ongeveer 1,7 keer zo snel. Daarom is het gebruikelijk om eerst met een profiler de delen te vinden die veel tijd kosten en daar te beginnen met verbeteren. “Maak het veelvoorkomende geval snel” is een principe dat steeds opnieuw wordt toegepast bij computerontwerp.
AAls bij een toenemend aantal processors ook de omvang van het probleem wordt vergroot, neemt het aandeel van het parallelle deel toe en wordt een grote versnelling bereikt
BHoeveel processors er ook worden toegevoegd, de versnelling blijft altijd beperkt tot maximaal 2 keer
CHet parallelle deel is altijd constant, ongeacht de omvang van het probleem
Antwoord en toelichting tonen
Antwoord: A. Als bij een toenemend aantal processors ook de omvang van het probleem wordt vergroot, neemt het aandeel van het parallelle deel toe en wordt een grote versnelling bereikt
De wet van Amdahl gaat uit van een toenemend aantal processors bij gelijkblijvende probleemomvang, waarbij het niet-parallelle deel de bovengrens van de versnelling bepaalt. De wet van Gustafson gaat ervan uit dat bij meer processors in dezelfde tijd een groter probleem wordt opgelost. Wanneer het probleem groter wordt gemaakt, bijvoorbeeld door een fijner rooster in een simulatie, neemt het parallelle deel toe en wordt het aandeel van het sequentiële deel kleiner, zodat een effect wordt verkregen dat vrijwel evenredig is met het aantal processors.
De parallelle efficiëntie is de versnelling gedeeld door het aantal cores en geeft aan hoe effectief de cores worden gebruikt. 6 ÷ 8 = 75 %, dus ten opzichte van het ideaal (8 keer) wordt drie kwart van het effect bereikt. De resterende 25 % gaat verloren door wachten op synchronisatie, ongelijke werkverdeling, communicatie en strijd om geheugenbandbreedte. Naarmate er meer cores zijn, daalt de efficiëntie gemakkelijk, dus het te gebruiken aantal cores wordt bepaald door te kijken tot waar de efficiëntie op peil blijft.
Veelgestelde vragen
Hoeveel sneller kan een programma worden dat voor 90% parallel is?
Volgens de wet van Amdahl ligt de grens op 1/(1 − 0,9) = 10 keer. Zelfs met 16 processors is de speedup slechts 1/(0,1 + 0,9/16) = 6,4, een efficiëntie van 40%. Zolang de resterende 10% serieel werk niet kleiner wordt, kan de speedup nooit boven 10 uitkomen.
Spreken de wet van Amdahl en de wet van Gustafson elkaar tegen?
Nee. De wet van Amdahl gaat over strong scaling met een vaste probleemgrootte, de wet van Gustafson over weak scaling, waarbij het probleem meegroeit met het aantal processors. Welke benadering geldt, hangt ervan af of je hetzelfde probleem sneller wilt oplossen of een groter probleem in dezelfde tijd.
Kan de parallelle efficiëntie boven 100% uitkomen?
Ja. Wanneer extra processors het deel van de data per processor zo klein maken dat het in de cache past, worden geheugentoegangen sneller en kan superlineaire speedup optreden. De wet van Amdahl modelleert zulke effecten niet.