Cache coherence, false sharing and memory access

Cache coherence in multicore systems

Caching layers can be private to a thread or shared among threads.

A problem that typically arises is how to reflect writes to shared data in the private caches of other threads.

Hardware coherence protocols track the ownership and state of blocks, and they propagate or invalidate updates. Snooping and MESI are two commonly used approaches.

False sharing

Coherence mechanisms operate at the granularity of a cache line, not of a single scalar variable.

If one thread updates variable $𝑥$ and another thread updates variable $𝑦$, and the two variables happen to share the same cache line, the updates are not independent from the hardware’s point of view: each write must acquire exclusive ownership of the whole line, so the line keeps bouncing between the caches and the updates are serialized. This is called false sharing, and it can severely limit the speedup even though the variables themselves are unrelated.

Arithmetic intensity and machine balance

Let us define some terms:

• $\text{Arithmetic intensity}=\frac{\text{arithmetic operations}}{\text{bytes transferred}}$
• ${𝐵}_{\text{peak}}=\text{transfer rate}\times \frac{\text{interface width}}{8}\times \text{channels}$
• $\text{Machine balance}=\frac{{𝑃}_{\text{peak}}}{{𝐵}_{\text{peak}}}$

If $\text{Arithmetic intensity}<\text{machine balance}$, the memory system cannot feed the arithmetic units at peak rate. Otherwise, if $\text{Arithmetic intensity}>\text{machine balance}$, the arithmetic throughput may become the limiting resource.

Effective bandwidth is what the application actually sustains: ${𝐵}_{\text{eff}}=\frac{{𝐵}_{\text{read}}+{𝐵}_{\text{write}}}{𝑡}$, where $𝑡$ is the total time taken for the operations to complete. It is lower than peak for a number of reasons: lack of caching/locality, concurrency (memory requests are not independent), contention (shared resources), access patterns and transaction efficiency (the ratio of bytes fetched to bytes actually used).

Memory access patterns

Different access patterns can be generated from the following formula: sequential, strided (one access every $𝑛$ elements, with $𝑛=1$ reducing to sequential) or even random.

$$\text{address}\left(𝑖\right)=\text{base}+\text{index}\left(𝑖\right)\times \text{sizeof}\left(𝑇\right)$$

As the stride grows, fewer elements from each cache line may be useful. A particular case is matrix element access. For row-major layouts, row access results in sequential addressing, while column access results in strided addressing. This can impact the performance of matrix multiplication.

Random access is common in sparse matrices, graphs and hash-based data structures.

Concurrent access

Parallel access patterns have two dimensions:

• Within one thread over time, it determines the per-thread stride, cache reuse and prefetchability.
• Across threads at the same time, it influences coalescing, shared-cache traffic and contention.

Some common access patterns are (where $𝑃$ is the number of threads, $𝑁$ the number of elements and $𝑘$ the per-thread offset):

• Block distribution: each thread gets a contiguous chunk, good for private cache locality:

  $$\text{index}\left(𝑡,𝑘\right)=𝑡\times \frac{𝑁}{𝑃}+𝑘$$

• Cyclic distribution: each thread has stride $𝑃$ through the array, which is better for shared cache locality but less predictable for the prefetcher:

  $$\text{index}\left(𝑡,𝑘\right)=𝑘\times 𝑃+𝑡$$

For SIMD applications, block access is usually better, since the processor benefits from needing fewer transactions to load data into registers. For applications that need to update variables often, sparse access allows threads to avoid contention and false sharing on cache lines.