CSE Roadmap

Core tier · about 4 hours · 7 parts

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 n processors.
  • Amdahl's law states that if a fraction p of a program's work can be run in parallel on n processors and the remaining fraction 1 − p must 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.