C · Course navigation

C: the speed-up limit of Amdahl's law

Compute the best possible speed-up for a program in which only part of the work can run in parallel.

On this page

Before you start

C loops, double arithmetic, and printf.

Compute the best possible speed-up for a program in which only part of the work can run in parallel.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

For p = 0.9, even with a million processors the program cannot run more than 10 times faster, because the serial 10 percent takes the same time on every machine. This is why reducing serial work, coordination, and communication matters more than adding processors. Gustafson's law gives a more optimistic view when the problem size grows with the machine.

Code example

#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;
}

Output

      1 processors: 1.00x
      2 processors: 1.82x
      4 processors: 3.08x
      8 processors: 4.71x
     16 processors: 6.40x
1000000 processors: 10.00x
limit: 10.00x

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1#include <stdio.h>

3static double speedup(double parallel_fraction, int processors) {

4 return 1.0 / ((1.0 - parallel_fraction) + parallel_fraction / processors);

5}

7int main(void) {

8 double p = 0.9;

9 int counts[] = {1, 2, 4, 8, 16, 1000000};

10 for (int i = 0; i < 6; i++) {

11 printf("%7d processors: %.2fx\n", counts[i], speedup(p, counts[i]));

12 }

13 printf("limit: %.2fx\n", 1.0 / (1.0 - p));

14 return 0;

15}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The serial part (0.1) is fixed; the parallel part (0.9) shrinks as processors are added.	`—`	—
Ninety percent of the work can be done in parallel.	`serial fraction = 0.1`	—
Doubling the processors gives less and less extra speed-up.	`2 → 1.82x, 4 → 3.08x, 8 → 4.71x, 16 → 6.40x`	1 processors: 1.00x 2 processors: 1.82x 4 processors: 3.08x 8 processors: 4.71x 16 processors: 6.40x 1000000 processors: 10.00x
The ceiling is 1 / 0.1 = 10, however many processors there are.	`2 → 1.82x, 4 → 3.08x, 8 → 4.71x, 16 → 6.40x`	1 processors: 1.00x 2 processors: 1.82x 4 processors: 3.08x 8 processors: 4.71x 16 processors: 6.40x 1000000 processors: 10.00x limit: 10.00x

Behind the scenes

How C processes this code

The C compiler produces a native program. Variables occupy memory, and execution enters main.

Cost and common mistakes

O(1) per evaluation.

The law assumes a fixed problem size and no overhead. Real programs also pay for synchronization and communication, so they do worse.
Using integer division, as in parallel_fraction / processors with ints, would round down and give wrong results. The example uses doubles.

Try it yourself

What is the limit of the speed-up if 95% of the program is parallelizable?

Reveal answer and reasoning

1 / 0.05 = 20 times, however many processors are used.