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.
Japanse benaming: アムダールの法則
“Wet van Amdahl” komt voor in 6 oefenvragen uit 3 onderwerpen, bijv. Prestatiemeting en profiling, CPU en architectuur, Multicore en synchronisatie.
Vakgebied: CPU en architectuur
De wet van Amdahl geeft de versnelling van een programma waarvan een fractie p over N processors kan worden geparalleliseerd als S = 1 / ((1 − p) + p/N). Als N onbeperkt groeit, verdwijnt de term p/N en nadert de versnelling 1 / (1 − p). Bij p = 0,9 ligt dat plafond op 10×, en met tien processors is het resultaat slechts ongeveer 5,3×, zodat de helft van de hardware feitelijk wordt verspild. Het seriële deel, hoe klein het ook lijkt, gaat uiteindelijk de looptijd domineren zodra het parallelle deel fijn genoeg is opgedeeld.
De wet geldt voor elke gedeeltelijke verbetering, niet alleen voor het toevoegen van cores. Als een sectie die 50% van de looptijd kost 4× sneller wordt gemaakt, wordt de nieuwe tijd 0,5 + 0,5/4 = 0,625 van de oorspronkelijke, een totale versnelling van 1,6×, en geen enkele verdere optimalisatie van die sectie kan boven 2× uitkomen. Een deel dat 1% van de tijd kost oneindig snel maken, levert maar ongeveer 1% op. Dit is de kwantitatieve basis van het principe make the common case fast en de reden om een programma te profileren voordat je het optimaliseert.
De wet van Amdahl gaat uit van een vaste probleemgrootte, wat overeenkomt met strong scaling: dezelfde taak wordt over meer processors verdeeld. De wet van Gustafson gaat van het omgekeerde uit: met meer processors lossen mensen in dezelfde tijd een groter probleem op, bijvoorbeeld een fijner simulatierooster. Het parallelle werk groeit mee met het probleem, terwijl het seriële deel ongeveer constant blijft, zodat de seriële fractie krimpt en de versnelling vrijwel evenredig met het aantal processors groeit. Dit is weak scaling. Geen van beide wetten is fout; ze beantwoorden verschillende vragen over hoe een workload wordt gebruikt.
De wet van Amdahl veronderstelt al dat het parallelle deel perfect schaalt, dus gemeten versnellingen liggen meestal nog lager. Threads wachten bij locks en barriers, gedeelde data en false sharing laten cachelines tussen cores heen en weer kaatsen, ongelijk verdeeld werk laat sommige cores stilstaan, en veel threads kunnen de geheugenbandbreedte verzadigen. De overhead van communicatie en synchronisatie kan zelfs met N groeien, zodat extra cores een programma uiteindelijk kunnen vertragen. De schoonste schaling ontstaat als elke thread vooral met eigen data werkt, met weinig communicatie of wachten.
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.
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.
Deel 1 door de nieuwe relatieve looptijd: S = 1 / ((1 − p) + p/s), waarbij p de fractie van de tijd is die wordt beïnvloed en s hoeveel sneller dat deel wordt (s = N voor N processors). Voor p = 0,5 en s = 4 geeft dit 1 / 0,625 = 1,6×.
De grens is 1 / (1 − 0,95) = 20×, ongeacht hoeveel processors worden gebruikt. Zelfs in de buurt van die grens komen vereist zeer grote aantallen processors en een vrijwel perfecte parallelle efficiëntie.
De wet van Amdahl houdt de probleemgrootte vast en laat zien dat het seriële deel de versnelling begrenst. De wet van Gustafson laat het probleem meegroeien met het aantal processors, zodat de seriële fractie krimpt en een vrijwel lineaire geschaalde versnelling mogelijk wordt.
Volgens de wet van Amdahl is, met p als geparalleliseerd deel en N als aantal processors, de versnelling 1/((1 − p) + p/N).
Wat is theoretisch de maximale versnelling wanneer een prog…De belangrijkste oorzaken die het effect van parallellisering belemmeren zijn het niet-paralleliseerbare deel (wet van Amdahl), wachten door locks en barrières, het heen en weer gaan van cacheregels door gedeelde gegevens en false sharing, ongelijke werkverdeling en onvoldoende geheugenbandbreedte.
Welke van de volgende is geen oorzaak dat de prestaties van…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.
Welke uitspraak over de gedachte achter de wet van Gustafso…Zoals de wet van Amdahl aangeeft, is het effectief het deel te verbeteren dat veel tijd kost, dus meten is de eerste stap bij prestatieverbetering.
Wat is het juiste doel van het gebruik van een profiler bij…Profiler Wet van Gustafson Numerieke apertuur (NA) False sharing Cachecoherentie Cachegeheugen DMA (direct memory access) DVFS (dynamic voltage and frequency scaling) GPU Instructiesetarchitectuur (ISA)