Nederlands
Menu

Wet van Amdahl versus wet van Gustafson: aannames en schaling

Beide wetten schatten hoeveel sneller een berekening wordt als er meer processors worden ingezet, maar ze gaan uit van andere aannames. De wet van Amdahl houdt de probleemgrootte vast en kijkt hoe hetzelfde werk sneller kan worden afgerond; het niet-paralleliseerbare deel bepaalt dan de bovengrens van de versnelling. De wet van Gustafson houdt de uitvoeringstijd vast en kijkt hoe met meer processors een navenant groter probleem kan worden opgelost; de versnelling groeit dan vrijwel evenredig met het aantal processors. De twee spreken elkaar niet tegen, maar beantwoorden verschillende vragen.

KenmerkWet van AmdahlWet van Gustafson
Wat vast blijftProbleemgrootte (totale hoeveelheid werk)Uitvoeringstijd (hoeveelheid werk per processor)
VraagHoeveel sneller kan hetzelfde probleem worden opgelost?Hoeveel groter probleem kan in dezelfde tijd worden opgelost?
Formule (N is het aantal processors)S = 1 / ((1 − p) + p / N)S = s + (1 − s) × N = N − s × (N − 1)
Hoe de fractie wordt gemetenp is het aandeel in de tijd van het paralleliseerbare deel bij uitvoering op 1 processors is het aandeel in de tijd van het sequentiële deel bij parallelle uitvoering op N processors
Bij toenemende NVlakt af bij 1 / (1 − p)Blijft vrijwel evenredig met N toenemen
RekenvoorbeeldBij p = 0,95 ongeveer 17 keer bij N = 100; zelfs bij oneindige N is 20 keer de bovengrensBij s = 0,05 ongeveer 95 keer bij N = 100
Bijbehorende schalingSterke schalingZwakke schaling
PerspectiefPessimistisch. Een klein sequentieel deel bepaalt de bovengrensOptimistisch. Met een groter probleem loont parallellisatie
Passende voorbeeldenWanneer invoer van vaste grootte snel moet worden verwerkt. Verwerking van één afbeelding, interactieve respons enz.Simulaties met een fijner rooster, of wanneer grotere data of modellen in dezelfde tijd moeten worden verwerkt
Wat beide niet meenemenOverhead van communicatie en synchronisatie, ongelijke belastingsverdeling, onvoldoende geheugenbandbreedteOverhead van communicatie en synchronisatie, ongelijke belastingsverdeling, onvoldoende geheugenbandbreedte

De getalswaarden zijn typische ordegroottes en variëren per procesgeneratie en product.

Wanneer welke variant?

Wet van Amdahl
Wanneer de probleemgrootte vastligt en de responstijd korter moet. Gebruikt om de bovengrens van parallellisatie te schatten en te beoordelen of het sequentiële deel moet worden verkleind.
Wet van Gustafson
Wanneer het probleem kan meegroeien met het aantal processors. Gebruikt om bij grootschalige simulaties en dataverwerking de waarde te schatten van fijner en groter rekenen.
Hoe resultaten te presenteren
Vermeld bij het rapporteren van parallelle prestaties of er met sterke of zwakke schaling is gemeten. Onder andere omstandigheden kan de versnelling van hetzelfde programma sterk verschillen.

Veelgestelde vragen

Spreken de twee wetten elkaar niet tegen?

Nee. De wet van Amdahl houdt de probleemgrootte vast en de wet van Gustafson de uitvoeringstijd, dus ze beantwoorden verschillende vragen. Bovendien wordt het aandeel van het sequentiële deel bij Amdahl gemeten in de tijd bij uitvoering op 1 processor en bij Gustafson in de tijd bij uitvoering op N processors, zodat je niet dezelfde waarde kunt invullen om ze te vergelijken.

Waarom wordt het hoogstens 10 keer sneller als 90% paralleliseerbaar is?

Omdat de resterende 10% niet korter wordt, hoeveel processors er ook bijkomen. Zelfs als de tijd van het parallelle deel naar nul gaat, wordt de totale tijd niet korter dan 10% van de oorspronkelijke tijd, dus vlakt de versnelling af bij 1 / 0,1 = 10 keer.

Waarom is de werkelijke versnelling kleiner dan deze wetten voorspellen?

Omdat geen van beide wetten rekening houdt met communicatie en synchronisatie tussen processors, ongelijke belastingsverdeling of onvoldoende gedeelde geheugenbandbreedte. Hoe meer processors, hoe groter deze effecten en hoe lager de parallelle efficiëntie.

Welke wet past bij mijn programma?

Als de invoergrootte vastligt en je het resultaat sneller wilt hebben, de wet van Amdahl. Als je met meer processors een fijner rooster of grotere data wilt verwerken, de wet van Gustafson. Ook voor hetzelfde programma hangt de passende wet af van hoe het wordt gebruikt.

Test uw begrip

Wat is theoretisch de maximale versnelling wanneer een programma waarvan 90 % van het werk kan worden geparalleliseerd, wordt uitgevoerd met een onbeperkt toenemend aantal processors?

  1. A10 keer
  2. B90 keer
  3. COneindig
Antwoord en toelichting tonen

Antwoord: A. 10 keer

Volgens de wet van Amdahl is, met p als geparalleliseerd deel en N als aantal processors, de versnelling 1/((1 − p) + p/N). Bij p = 0,9 is de bovengrens, ook als N oneindig wordt, 1/0,1 = 10 keer, en bij N = 10 is dat slechts circa 5,3 keer. Omdat zelfs een klein niet-paralleliseerbaar deel de bovengrens bepaalt, is het belangrijk het sequentiële deel te verkleinen. De gedachte om het probleem groter te maken en zo het parallelle deel te laten toenemen is de wet van Gustafson.

Een onderdeel dat 50 % van de totale verwerking beslaat, wordt 4 keer zo snel gemaakt. Wat is de totale versnelling (wet van Amdahl)?

  1. A2 keer
  2. B1,6 keer
  3. C4 keer
Antwoord en toelichting tonen

Antwoord: B. 1,6 keer

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.

Welke les over de aanpak van prestatieverbetering volgt het best uit de wet van Amdahl?

  1. APrioriteit geven aan het versnellen van het deel dat veel tijd kost (het veelvoorkomende geval)
  2. BEerst de zelden uitgevoerde delen versnellen
  3. 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.

  1. Welke uitspraak over de gedachte achter de wet van Gustafson is juist?
  2. Welk verschil tussen “strong scaling” en “weak scaling” bij de evaluatie van parallelle berekeningen is juist?
  3. Hoe wordt de versnelling (speedup) die een prestatieverbetering weergeeft juist bepaald?

Oefenvragen over Prestatiemeting en profiling

Belangrijke termen uitgelegd

Wet van Amdahl
Wet die zegt dat, als slechts een deel van een programma wordt geparalleliseerd, de totale versnelling wordt begrensd door het deel dat niet kan worden geparalleliseerd. Bij bijvoorbeeld 90% parallellisatie is het programma maximaal 10 keer sneller.
Wet van Gustafson
Inzicht dat wanneer het aantal processoren toeneemt en ook het probleem groter wordt gemaakt, het aandeel dat parallel kan worden uitgevoerd toeneemt en een effect wordt behaald dat ongeveer evenredig is met het aantal processoren.
Sterke schaling (strong scaling)
Beoordeling van parallelle prestaties waarbij de probleemgrootte vast blijft en wordt gekeken hoeveel de tijd afneemt bij meer processors.
Weak scaling
Beoordeling van parallelle prestaties waarbij de probleemgrootte per processor constant blijft terwijl het geheel groter wordt, en wordt bekeken of de tijd gelijk blijft.
Parallelle efficiëntie (parallel efficiency)
Waarde die ontstaat door de versnelling dankzij parallellisatie te delen door het aantal processoren. Geeft aan hoe effectief de cores worden gebruikt.

Verwante vergelijkingen