Cache Hierarchy and Locality

Caches hold recently used data close to the core; programs that exhibit temporal and spatial locality run far faster than those that do not.

Levels of cache

Between the fast registers and slow main memory sit several levels of cache: a small, fast L1 per core; a larger, slower L2; and a large L3 often shared across cores. Each level trades size for speed. When a core needs data, the hardware checks caches in order; a hit is fast, a miss forces a fetch from the next level, and a miss all the way to DRAM costs hundreds of cycles.

Two kinds of locality

Caches pay off when programs exhibit locality. Temporal locality means reusing the same data soon after touching it, so it is still cached. Spatial locality means touching data near what was just used, which is cheap because caches load a whole cache line (typically 64 bytes) at once. Sequential array traversal has excellent spatial locality; pointer-chasing through scattered nodes has almost none.

• L1/L2/L3 trade capacity for access speed.
• Temporal locality: reuse data while it is still cached.
• Spatial locality: access neighbors within the same cache line.
• Blocking restructures loops so working sets fit in cache.

Cache blocking

Blocking (tiling) is the main technique for exploiting caches. Instead of sweeping a huge array once, the loop is restructured to work on small tiles that fit in cache, doing all the work on a tile before moving on. Matrix multiply blocked to L1/L2 tile sizes reuses each loaded element many times, converting a memory-bound traversal into one limited by arithmetic. The same idea underlies GPU shared-memory tiling.

False sharing

A multi-thread pitfall is false sharing: two threads write different variables that happen to sit in the same cache line, so the line ping-pongs between cores as each write invalidates the other's copy. Padding shared data to separate cache lines removes it. For a Hyperion stencil, tiling the mesh to cache size and padding per-thread accumulators keeps the memory system efficient without touching the physics.