Part 6 of 7 · 3 min read
Affinity
Choosing where a thread runs
In plain words: The scheduler decides which processor runs a thread, and it moves threads between processors to balance the load (Level 3). Sometimes a program wants to decide. Processor affinity is the set of processors on which a thread is allowed to run. Pinning a thread to one processor keeps its data in that core's caches, and it also makes timing experiments repeatable, as in the context-switch test of Level 1, page 5.
From the shell, taskset -c 0 ./prog runs a program on processor 0 only. In C, sched_setaffinity sets the allowed processors, and pthread_setaffinity_np does so for one thread. The earlier two-thread test shows the effect:
$ time ./m1 elapsed 0.86 s user 1.705 s
$ time taskset -c 0 ./m1 elapsed 1.71 s user 1.699 s
The two runs did the same work, 1.7 seconds of processor time. Restricted to one processor, the elapsed time doubled (page 3).
Common mistake
Believing that more threads always give more speed. The limits are the number of processors, the serial part of the program (Amdahl), the memory system (cache lines, false sharing) and the cost of locks (page 4).
Interview angle
Answer in your head first, then open it.
What is Amdahl's law?
The speed-up from parallelism is limited by the serial fraction: speed-up = 1 / ((1 − p) + p/n), at most 1 / (1 − p).
Why might a multithreaded program run slower than a single-threaded one?
Locks, false sharing, too many threads for the processors, or work too small to repay the thread start-up.
What is false sharing?
Different threads writing different variables on the same cache line, so the line bounces between cores.
What is processor affinity?
The set of processors a thread may run on.
How many threads for CPU-bound work?
About the number of processors.
Check yourself: 1. Which command runs a program on processor 0 only? 2. Why does pinning help with timing experiments? 3. Name three reasons a threaded program may fail to speed up.
Words you will meet
| Word | Meaning |
|---|---|
| Core | One complete processing unit on a chip |
| Logical processor | What the operating system schedules threads on |
| Cache line | The unit of data in a cache, 64 bytes here |
| Speed-up | Time on one processor divided by time on n |
| Efficiency | Speed-up divided by n |
| Cache coherence | The hardware rule that keeps copies of a line consistent |
| False sharing | Different variables on one cache line causing slow-downs |
| Processor affinity | The processors a thread may run on |
Quick notes
- A core is an independent processing unit of a chip that executes instructions, so a multicore chip can run several threads at the same moment.
- Speed-up is the run time of a program on one processor divided by its run time on
nprocessors. - Amdahl's law states that if a fraction
pof a program's work can be run in parallel onnprocessors and the remaining fraction1 − pmust run serially. - False sharing is a loss of performance that occurs when threads on different cores write different variables that lie on the same cache line, so the coherence protocol keeps moving.