Gustafson–Barsis lag

Gustafson–Barsis lag avbildar sammanhang mellan problemstorlek och antal CPU:er, dvs. speedup. Den har upptäckts av E. Barsis och publicerats av John Gustafson. Frågan är: Hur mycket större problem kan beräknas i samma tid när mer CPU:er tillsätts?

Även i ett parallellt program finns det uppgifter som inte kan delas upp och som varje programinstans måste utföra själva, som till exempel minnesallokering eller initialisering av nätverkförbindelser. Följaktligen delas program upp i en parallelliserbar ($P'$) och en seriell ($S$) andel (då är $S+P'=1$). Speedup $Sp$ för tillsättning av $N$ CPU:er beräknas enligt:

${\begin{matrix}Sp(N)&=&{\frac {S+P\cdot N}{S+P'}}\\\ &=&S+P\cdot N\\\ &=&(1-P)+P\cdot N\end{matrix}}$

Det beror på jämförelse av antal av instruktioner som en enkel processor måste utföras för att lösa problemet ($S+P\cdot N$) med den antal varje av $N$ processorer måste utföras ($S+P$).

Kritik

Det är inte alltid möjligt att ökar endast den parallella andelen. För sådana fall finns Amdahls lagen som frågar efter tidvinster. Hur mycket snabbare kommer man att beräkna ett problem av fast storlek om man tillsätter mer CPU:er?