CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Speed-up and efficiency (20 minutes)

A job takes 30 s on one processor and 10 s on four. Give the speed-up and the efficiency.

Done when: 3.0 and 0.75.

Hint

Efficiency = speed-up / 4.

Easy 2: Apply the law (20 minutes)

A program is 80 per cent parallel. Compute the speed-up for 4 processors and the ceiling.

Done when: 1 / (0.2 + 0.8/4) = 2.5, and a ceiling of 5.

Hint

The ceiling is 1 / (1 − p).

Easy 3: Read the machine (20 minutes)

Run nproc, lscpu and getconf LEVEL1_DCACHE_LINESIZE on your machine. Write the number of cores, the threads per core and the line size.

Done when: three values from your own machine.

Hint

Threads per core above 1 means hyper-threading.

Medium

Medium 1: Measure the speed-up (30 minutes)

Run the speed-up program on your machine for 1, 2, 4 and 8 threads. Tabulate the times, the speed-ups and the efficiencies.

Done when: a table where the speed-up stops growing at your number of processors.

Hint

Use a fixed total amount of work and divide it by the thread count.

Medium 2: Check Amdahl (30 minutes)

Run the serial-fraction program with serial fractions 0.1, 0.25 and 0.5. Compute the predicted speed-up for 2 threads for each and compare.

Done when: a table of three predictions (1.82, 1.60, 1.33) next to three measurements, and a note on the gap.

Hint

Predicted speed-up for 2 threads is 1 / (s + (1 − s)/2).

Medium 3: Pin a program (30 minutes)

Run the two-thread spin program with taskset -c 0 and without it, and with taskset -c 0,1. Report the elapsed and user times.

Done when: a table showing the elapsed time about doubling on one processor.

Hint

user time is the same, real changes.

Hard

Hard 1: Reproduce false sharing (60 minutes)

Run the adjacent and padded counter test with atomic increments, then with plain volatile increments. Report the ratios for both and explain the difference.

Done when: a ratio near 5 for atomic and near 1 for plain on a similar machine, or your own figures, with a sentence on why they differ.

Hint

__atomic_fetch_add(&x, 1, __ATOMIC_RELAXED) is the atomic increment.

Hard 2: Find the line size (60 minutes)

Vary the padding between the two counters from 0 to 128 bytes in steps of 8, and time the atomic test for each. Plot the time against the padding and find the point where it drops.

Done when: a table or plot with a sharp drop near 64 bytes, and a conclusion about the line size.

Hint

Use char pad[k] with a changing k, in separate builds or with a macro.

Hard 3: Speed-up of a real task (60 minutes)

Parallelise counting the primes below 20 million with a thread pool of 1, 2 and 4 workers, using ranges of 100,000 numbers as tasks. Compute the speed-up, and compare with Amdahl's law by estimating the serial part.

Done when: a table of three speed-ups, the same count of primes in every run (1,270,607), and one paragraph on why the speed-up is below the ideal.

Hint

The number of primes below 20 million is 1,270,607.