Module 2 · Unit 4 · Discussion 4
How Far Does Parallelism Scale?
Adding threads to a program is easy; making the program faster is not. Every parallel program has a serial fraction, every shared data structure is a potential bottleneck, and every cache line shared between two cores is a source of coherence traffic. This discussion asks you to measure the scaling of a real multi-threaded workload, compare it to the prediction of Amdahl's Law, and diagnose the gap between the two.
01 Overview
| Course | COMP 3150 / CMIS 3150 — Operating Systems |
|---|---|
| Unit | Unit 4 — Threads |
| Weight | Part of the 5% participation grade (each discussion is worth approximately 0.4% of the final grade) |
| Opens | Monday of Week 4 |
| Initial post due | Thursday of Week 4, 23:59 |
| Peer replies due | Sunday of Week 4, 23:59 |
| Format | One initial post (500–700 words, including a table of measured results) and at least two substantive peer replies (150–250 words each) |
| CLOs assessed | CLO2, CLO6, CLO8 |
02 Learning outcomes addressed
By participating in this discussion you will
- Explain the thread abstraction and identify what is shared between threads of a process and what is private to each (U4.1).
- Compare the threading models — many-to-one, one-to-one, and many-to-many — and explain the trade-offs (U4.2).
- Analyse multicore concurrency and the factors that limit the scaling of a parallel program (U4.3).
- Develop and run a POSIX-threaded program with configurable thread counts, and measure its scaling (U4.4).
- Evaluate thread-management strategies and recommend one for a given workload (U4.5).
This discussion assesses CLO2 (explain process and thread management), CLO6 (apply Linux systems programming and tools), and CLO8 (design and implement OS-related components).
03 Discussion prompt
Amdahl's Law states that if a fraction p of a computation can be parallelised and the remaining fraction (1 − p) is strictly serial, the maximum speedup achievable with n threads is:
S(n) = 1 / ((1 − p) + p / n)In the limit as n → ∞, the speedup approaches 1 / (1 − p). If 20% of the work is serial, no number of cores can produce a speedup above five.
Amdahl's Law is a statement about the algorithm, not the hardware. Real programs also pay for thread creation, context switching, lock contention, memory-bandwidth saturation, cache-coherence traffic, and false sharing. The measured speedup is therefore always below the Amdahl prediction — sometimes far below.
Your task
-
Choose a CPU-bound workload that can be
parallelised. Examples:
- Computing SHA-256 hashes of N independent inputs.
- Multiplying two large matrices.
- Sieve of Eratosthenes to find primes below a large bound.
- Computing a large number of independent Monte-Carlo samples (for example, estimating π).
-
Write a POSIX-threaded program that runs the
workload with n threads, for n
∈ {1, 2, 4, 8} (or as many as your VM has cores;
use
nprocto check). Measure the wall-clock time for each n, usingclock_gettime(CLOCK_MONOTONIC). Repeat each measurement at least five times and report the mean. - Compute the speedup S(n) = T(1) / T(n) and the parallel efficiency E(n) = S(n) / n. Present the results in a table.
- Fit the measured speedup to Amdahl's Law: from the data, estimate the serial fraction (1 − p) of your workload. Does the estimate match your intuition about the algorithm? If not, what else is limiting the scaling?
- Diagnose the gap between the measurement and the Amdahl prediction. Identify at least two concrete sources of overhead in your program (for example, the thread-creation cost, the merge step at the end, the memory bandwidth of the machine, the scheduling of the threads by the kernel, or false sharing between the threads' data structures). Support each diagnosis with evidence from your measurement or from a second experiment.
Your post should be 500–700 words, with the measurement table included. Include the commands you ran, the kernel version, and the CPU count so that the experiment can be reproduced. Do not simply quote the Amdahl prediction — measure the actual speedup and compare.
04 Suggested diagnostics
If your scaling is worse than the Amdahl prediction, the following diagnostics can help you identify the cause.
4.1 Thread-creation overhead
Measure the time to create and join n threads without any work. If the total work is small, the creation overhead dominates. Compare the measured time for a workload that finishes in 1 ms per thread with one that finishes in 1 s per thread.
4.2 Memory bandwidth
Run the same workload single-threaded and
multi-threaded and observe the effective memory
bandwidth with perf stat -e cache-misses,LLC-load-misses,LLC-loads.
If the bandwidth saturates before the cores
saturate, adding threads will not help — the
program is memory-bound, not CPU-bound.
4.3 False sharing
If each thread writes to a variable that shares a
cache line with another thread's variable, the
cache line bounces between cores, and performance
collapses. Test this: write a program where each
thread increments its own counter, and then change
the counters to struct { long v; char
padding[64]; } so that each counter occupies
a full cache line. Measure the difference.
4.4 Lock contention
If your workload requires threads to update a
shared counter or a shared data structure, the
lock serialises the work. Measure the time with
the lock and without (if the workload allows it),
and estimate the fraction of time spent waiting on
the lock with perf stat -e
sched:sched_stat_blocked or a hand-written
instrumentation counter.
4.5 Scheduling
On a machine with fewer cores than threads, the
kernel must multiplex the threads. Observe the
number of context switches (pidstat
-w) and the run-queue length
(vmstat 1, column r). If
the run-queue length is much larger than the number
of cores, the threads are competing for CPU time.
05 Grading rubric
The discussion is marked out of 100 points. The criteria and their weights are given below. The descriptors for each level are adapted to the measurement-based nature of this discussion.
| Criterion | Weight |
|---|---|
| Post quality (experiment, analysis, diagnosis) | 40% |
| Peer response quality | 30% |
| Engagement and timeliness | 20% |
| Netiquette and clarity | 10% |
5.1 Post quality (40 points)
| Level | Descriptor |
|---|---|
| Exemplary (90–100%) | A well-designed experiment with a clear methodology. The results are presented as a table of speedup and efficiency for n ∈ {1, 2, 4, 8}. The measured speedup is compared to the Amdahl prediction, and the serial fraction is estimated. At least two concrete sources of overhead are diagnosed, each with supporting evidence. The post demonstrates a correct understanding of Amdahl's Law and its limitations. |
| Proficient (80–89%) | A well-designed experiment with a clear methodology. The speedup and efficiency are computed correctly. The comparison with Amdahl's Law is present and the serial fraction is estimated. One source of overhead is diagnosed with evidence; the second is mentioned but not fully supported. |
| Developing (70–79%) | An experiment is run, but the methodology is incomplete (fewer than five repetitions, no warm-up, or no documentation of the hardware). The speedup is computed but the efficiency or the Amdahl comparison is missing. The diagnosis is superficial. |
| Beginning (60–69%) | The experiment is not run, or the results are not reported. The post consists of a theoretical discussion of Amdahl's Law without measurement. |
| Not demonstrated (<60%) | The post is missing, off-topic, or a restatement of the prompt without any measurement. |
5.2 Peer response quality (30 points)
The descriptors are the same as for Discussion 3. An exemplary reply might:
- Compare the classmate's measured serial fraction with their own, and explain the difference.
- Suggest a diagnostic the classmate did not run (for example, a test for false sharing or memory bandwidth).
- Identify an assumption in the classmate's Amdahl analysis that does not hold for their workload.
5.3 Engagement and timeliness (20 points)
The descriptors are the same as for Discussion 1.
5.4 Netiquette and clarity (10 points)
The descriptors are the same as for Discussion 1.
06 Resources
- Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 4 (Threads and Concurrency) and Section 5.6 (Multicore Processors).
- Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 26 (Concurrency: An Introduction) and Chapter 27 (Interlude: Thread API).
- Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2 (Threads).
- Butenhof, D. R. Programming with POSIX Threads. Addison-Wesley, 1997.
- Amdahl, G. M. Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities. AFIPS Spring Joint Computer Conference, 1967.
- Gustafson, J. L. Reevaluating Amdahl's Law. Communications of the ACM, 1988.
- Linux man-pages:
man 3 pthread_create,man 3 pthread_join,man 3 pthread_attr_setaffinity_np,man 1 perf-stat,man 1 taskset. - Drepper, U. What Every Programmer Should Know About Memory. Red Hat, 2007.