6. Multicore and the Memory Wall [10 marks]

Relative to each other, CPUs have few threads and enormous caches, while GPUs

have many threads and tiny caches. Generally speaking, we need to think

carefully about any hardware architecture in which many hardware threads

share a cache (usually, but not always, the last-level cache). GPUs are the

extreme example of such an architecture.

Suppose threads are cache friendly in the sense that each portion of a thread

accesses a small subset of memory, and that this subset changes relatively

slowly. But threads are normally interleaved with some frequency, rather than

being allowed to run to completion. The technical term for this slowly

changing subset is the thread's _working set_.

Now suppose that the working set of a thread is roughly the same size as the

shared cache. Further suppose that the hardware schedules threads much more

rapidly than the speed with which their working sets evolve.

As a thought experiment, in which case is a thread more likely to find its data

in cache:

Case i: We schedule many threads rapidly for short intervals, as described

above.

Case ii: We schedule one thread for a relatively long time so that it owns the

cache for an interval roughly equal to one phase of the evolution of its working

set.

Explain.