Cache Memory: Direct, Associative, Set-Associative & AMAT

Caches exploit Temporal Locality (recently referenced memory locations are likely to be accessed again soon) and Spatial Locality (memory locations contiguous to recently accessed items are likely to be accessed soon).

Physical Address Partitioning Formulations:

1. Block (Byte) Offset bits (w):

w = \log_2(Block Size in bytes). Identifies the specific byte within a cache line.

2. Direct-Mapped Cache:

Each main memory block maps to exactly ONE cache line index: Line = (Block Address) \bmod (Total Cache Lines).

Address Split: [ Tag Bits \mid Line Index Bits (\log_2 N_{lines}) \mid Block Offset Bits (w) ].

3. Fully Associative Cache:

A memory block can be placed in ANY cache line. No index bits required. Requires parallel comparator hardware for all lines.

Address Split: [ Tag Bits \mid Block Offset Bits (w) ].

4. k-way Set-Associative Cache:

Cache lines are grouped into sets of k lines each. Block maps to: Set = (Block Address) \bmod (Total Sets).

Address Split: [ Tag Bits \mid Set Index Bits (\log_2 N_{sets}) \mid Block Offset Bits (w) ].

Total Sets = \frac{Total Cache Capacity}{Block Size × k} = \frac{N_{lines}}{k}.

AMAT models the effective latency seen by the CPU across the memory hierarchy:

1. Single-Level Cache:

AMAT = T_{hit} + (M_{rate} × T_{penalty}).

2. Two-Level Cache Hierarchy (L1 and L2):

AMAT = T_{L1} + M_{L1} × (T_{L2} + M_{L2,local} × T_{MM}).

Local vs Global Miss Rate Distinction:

- Local Miss Rate of L2 (M_{L2,local}): \frac{Misses in L2}{Accesses to L2 (Misses from L1)}.

- Global Miss Rate of L2 (M_{L2,global}): \frac{Misses in L2}{Total CPU References} = M_{L1} × M_{L2,local}.