CPU caches fundamentals

Foundational Principles

Temporal Locality: Re-referencing the same memory location within a short time frame -> solved by caching.
Spatial Locality: Referencing memory locations near one another -> solved by using cache blocks / cache lines.

Write Policies

Write-Through Cache: Writes data directly to both the cache and main memory simultaneously.
Write-Back Cache: Writes data only to the cache; relies on a Dirty bit (D) to defer writing to main memory until eviction.
Write-Allocate: Loads the block into the cache on a write miss.
Write-No-Allocate: Writes directly to main memory on a write miss without loading the block into the cache.

Cache Mapping & Search Methods

Fully Associative: A memory block can go into any cache line. Address breakdown: [Tag | Block Offset]
Direct Mapped (1-way Set Associative): Each memory block maps to exactly one specific cache line.
Set Associative (2-way, 4-way, etc.): A memory block maps to a specific set, but can sit in any line inside that set. Address breakdown: [Tag | Set Index | Block Offset]

Address Bit Calculations

Block Offset = log2(Block Size)
Set Index = log2(Number of Sets in Cache)
Tag = Remaining Most Significant Bits of Address

Replacement / Eviction Algorithms

LRU (Least Recently Used): Evicts the block that has not been accessed for the longest time.
Optimal: Evicts the block that will not be used for the longest period in the future.
FIFO (First-In, First-Out): Evicts the oldest loaded block.
Random: Randomly selects a block to evict.

Cache Hierarchy & Structure

Levels: L1, L2, L3 caches.
Cache Line Layout: Each entry contains control metadata alongside the data payload:
- V (Valid Bit): Indicates if the cache line contains valid data.
- D (Dirty Bit): Used in Write-Back caches to track modified data.
- Tag: Most significant bits used to identify the address.
- Data: The actual cached memory block.
Example Parameters: 2-way set associative, Cache line = 2 bytes, Write-back policy.

Cache coherency in multicore systems

https://www.youtube.com/watch?v=83jOKVb_HTM

DMA caches IIT Madras videos:

DMA fundamentals

DMA on AXI

Cache coherency in DMA systems

AXI DMA programming and usage

Cache hierarchy and DMA

Example DMA stream transfer from peripheral:

MM2S --> memory mapped to AXI stream

S2MM --> Stream to memory mapped

Cache coherency in DMA:

🧠 Biological Cache Reload: MIT 6.004 L25 — Cache Coherence

1. 🎯 Core Problem & Mission

    [ Core 0 (L1 Cache) ] \

    [ Core 1 (L1 Cache) ]  ===> [ Shared Main Memory ]

    [ Core 2 (L1 Cache) ] /

The Problem: Multiple cores have private caches but share one main memory.
- Stale Data Scenario: Core 0 loads A (value=2). Core 1 stores 3 into A. Core 0 re-reads A from its L1 cache and gets stale 2 instead of 3.
The Mission: Make private L1 caches completely invisible to the programmer so parallel code behaves as if there is a single, perfectly consistent shared memory.

2. ⚖️ Two Absolute Rules of Coherence

To guarantee correctness across parallel cores, any protocol must enforce:

Write Propagation: A write by Core X must eventually become visible to all other cores.
Write Serialization: All writes to the same address must be seen by all cores in the exact same global order.

3. 📜 Protocol Evolution FSMs (State Machines)

A. Valid / Invalid (VI) Protocol (Write-Through)

States: V (Valid), I (Invalid)
Mechanism: Writes broadcast a Bus Write to update Main Memory and invalidate other L1 copies.
Why it fails in practice: Every write triggers a bus transaction and main memory write. Extreme bandwidth bottleneck!

B. MSI Protocol (Write-Back)

States:
- I (Invalid): Line not present or stale.
- S (Shared): Read-only permission. Multiple cores can hold S copies simultaneously.
- M (Modified): Read/Write permission. Only ONE core can hold M. Line is dirty (differs from Main Memory).
Key Transitions:
- I → (Processor Read) → S (issues BusRd)
- I or S → (Processor Write) → M (issues BusRdX / Bus Read Exclusive — forces all other cores to invalidate their copy)
- M → (Snoops BusRdX from another core) → I (must write dirty data back to memory first)
Big Win over VI: Writes in M state happen locally in L1 without any bus traffic.

C. MESI Protocol (Optimized for Private Data)

States: Adds E (Exclusive) state to MSI (M, E, S, I).
What E means: Read-only access, but only ONE core holds it, and it is clean (matches main memory).
Why E exists:
- When a core reads private data (no other core has it), it enters E instead of S.
- If it later decides to write to that data, it moves E → M silently with ZERO bus overhead (no need to issue BusRdX because it already knows no other cache has a copy!).
- Saves 1 bus transaction for every private read-modify-write sequence.

4. 🏗️ Hardware Architecture Implementations

Feature	Snoopy-Based Protocols	Directory-Based Protocols
Medium	Shared Bus	Interconnect Network (Point-to-Point)
How it works	Every cache controller "snoops" (listens to) all broadcast traffic on the shared bus.	A centralized/distributed Directory tracks which cores hold copies of each memory block.
Target Scale	Small core counts (2–8 cores).	Large multi-core / distributed systems (16+ cores).
Limitation	Broadcast bus does not scale (bus saturation).	Directory lookup latency + storage overhead.

5. ⚠️ The Performance Trap: False Sharing

    Cache Line (64 Bytes): [ Word i (Used by Core 0) | Word k (Used by Core 1) ]
  

What it is: Two independent threads on different cores update different variables that happen to live inside the same cache line block.
The Consequence:
- Core 0 writes to Word i → Core 0 requests M state → Core 1's cache line gets invalidated.
- Core 1 writes to Word k → Core 1 requests M state → Core 0's cache line gets invalidated.
- Ping-Pong Effect: The line constantly bounces between L1 caches via bus invalidations even though there is zero logical data sharing!
Software Fix: Pad data structures (e.g., align variables to 64-byte boundaries) so independent concurrent variables sit on separate cache lines.

⚡ 30-Second Flash Card Summary

Coherence Goal: One memory view across all cores.
Rules: Write Propagation + Write Serialization.
VI Protocol: Write-through → Too slow (bus spam).
MSI Protocol: Write-back → Uses BusRdX to gain exclusive write state (M).
MESI Protocol: Adds E state → Eliminates extra BusRdX for private read-modify-write loops.
Snoopy vs Directory: Snoopy broadcasts on a bus (small scale); Directory sends point-to-point updates (large scale).
False Sharing: Different variables on the same 64B cache line cause cache ping-ponging. Solution: Padding / Alignmen

Pages

Caches