C: the speed-up limit of Amdahl's law
Amdahl's law says that the speed-up from using n processors is limited by the part of the program that must run serially. If a fraction p of the work can be parallelized, the speed-up is 1 / ((1 − p) + p / n). As n grows, the speed-up approaches 1 / (1 − p), no matter how many processors are used.
C
#include <stdio.h>
static double speedup(double parallel_fraction, int processors) {
return 1.0 / ((1.0 - parallel_fraction) + parallel_fraction / processors);
}
int main(void) {
double p = 0.9;
int counts[] = {1, 2, 4, 8, 16, 1000000};
for (int i = 0; i < 6; i++) {
printf("%7d processors: %.2fx\n", counts[i], speedup(p, counts[i]));
}
printf("limit: %.2fx\n", 1.0 / (1.0 - p));
return 0;
}