CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 3 of 7 · 2 min read

Speed-up

Speed-up is the time the program takes with one thread divided by the time with n threads. A speed-up of 2 means twice as fast. Efficiency is the speed-up divided by n: an efficiency of 1 (or 100 per cent) means every added processor was fully used.

In plain words: The test splits a fixed amount of computing (400 million loop steps) among 1, 2, 4 and 8 threads, and times it on the two-processor machine:

1 thread : 1.16 s, speed-up 1.00
2 threads: 0.58 s, speed-up 1.99
4 threads: 0.60 s, speed-up 1.92
8 threads: 0.58 s, speed-up 1.99

Read the table in steps. Two threads cut the time to half, 1.16 divided by 0.58 is 2.0, so the efficiency was almost 100 per cent. Four threads did not help further. There are only two processors, so four threads still run two at a time, taking turns, and the total work is the same. Eight threads gave the same. The speed-up cannot exceed the number of processors, 2 here.

Three lessons follow:

  1. For work that only computes, more threads than processors never help (page 5 gave the same advice for pool sizes).
  2. The efficiency stays high only when the work splits evenly and the threads do not wait for each other.
  3. A program with a part that cannot be split loses efficiency, the next section.

Speed-up and efficiency

Speed-up is the run time of a program on one processor divided by its run time on n processors. Efficiency is the speed-up divided by n, the fraction of the added processors' capacity that was actually used.

Example: a program that takes 12 s on one processor and 4 s on four has a speed-up of 3 and an efficiency of 0.75.

Check yourself: 1. What was the efficiency of the two-thread run? 2. Why did eight threads not beat two on a two-processor machine? 3. Compute the speed-up and the efficiency for 20 s on one processor and 6 s on four.