Why Cache Consistency Can Halve Your Program’s Runtime – A Deep Dive

Cache Consistency Levels

Cache consistency has several layers:

Synchronization between a CPU's icache and dcache.

Synchronization among caches of multiple CPUs.

Synchronization between CPU caches and devices (or heterogeneous processors) such as DMA.

ICache and DCache Synchronization

When self‑modifying code (e.g., JIT‑compiled code) writes new instructions to memory, the store updates the dcache, but the icache may still contain the old instructions. The software must clean the dcache and invalidate the icache, which incurs noticeable overhead.

Some processors, such as ARM64 N1, provide hardware support for icache synchronization (see the Arm Neoverse N1 documentation).

Multi‑CPU Cache Synchronization

In a simplified processor model, CPUs A and B share an L3 cache, while CPUs C and D share another L3. When one CPU writes to a memory location, other CPUs must see the updated value. This is achieved through cache‑coherency protocols.

MESI Protocol

The MESI (Modified, Exclusive, Shared, Invalid) protocol defines four states for a cache line:

M (Modified) : The line is dirty and differs from memory; it must be written back before another CPU can read it.

E (Exclusive) : The line is clean and present only in this cache.

S (Shared) : The line is clean and may exist in multiple caches.

I (Invalid) : The line is not valid.

The state machine ensures that when a CPU modifies a line, other CPUs receive invalidation messages, guaranteeing coherence.

Performance Measurement

A two‑thread program that writes and reads the same cache line shows significant overhead due to cache synchronization. Running the program on two cores took 3.614 s (real) and 7.021 s of user time. Changing the second thread to read a different cache line reduced the runtime to 1.820 s, almost halving the execution time.

$ time ./a.out
real  0m3.614s
user  0m7.021s
sys   0m0.004s

$ time ./b.out
real  0m1.820s
user  0m3.606s
sys   0m0.008s

Prefetching

Prefetching reduces cache‑miss latency. On ARM, the pld instruction can be used:

static inline void prefetch(const void *ptr) {
    __asm__ __volatile__("pld %a0" :: "p" (ptr));
}

Benchmarks show a ~14 % speed‑up when prefetching is enabled in a binary search implementation.

False Sharing

When two threads write to different variables that reside on the same cache line, the cache‑coherency protocol forces the line to bounce between cores, causing performance loss. Padding or separating the variables into different cache lines eliminates false sharing.

struct s { int a; char padding[cacheline_size - sizeof(int)]; int b; };

Cache Mapping Strategies

Three common mapping schemes:

Direct‑mapped : Each memory block maps to exactly one cache line.

Fully associative : Any memory block can occupy any cache line.

Set‑associative : A compromise; the cache is divided into sets, each set is fully associative.

Cache Replacement Policy

Most modern caches use the Least‑Recently‑Used (LRU) policy to evict the line that has not been accessed for the longest time.

Practical Programming Tips

Use row‑major traversal for 2‑D arrays to exploit spatial locality, and avoid false sharing by padding structures. Align data to cache‑line boundaries when possible, and employ prefetch instructions for hot data paths.

const int row = 1024;
const int col = 1024;
int matrix[row][col];
int sum_row = 0;
for (int r = 0; r < row; ++r) {
    for (int c = 0; c < col; ++c) {
        sum_row += matrix[r][c];
    }
}
int sum_col = 0;
for (int c = 0; c < col; ++c) {
    for (int r = 0; r < row; ++r) {
        sum_col += matrix[r][c];
    }
}

Understanding and applying these cache‑aware techniques can dramatically improve program performance.