CMPSC 311 – Caching & Memory Hierarchy

Vocabulary flashcards covering caching fundamentals, memory hierarchy, locality, cache architectures, performance equations, and common caching and writing strategies.

Cache

A small, fast storage layer that temporarily holds a subset of the data in a larger, slower storage device.

Memory Hierarchy

Organization of storage layers where each faster, smaller level serves as a cache for the next slower, larger level.

Locality

The tendency of programs to access the same or nearby data repeatedly, enabling effective caching.

Spatial Locality

Program behavior where accesses tend to cluster near recently accessed addresses.

Temporal Locality

Program behavior where recently accessed data is likely to be accessed again soon.

L1 Cache

Fastest, smallest on-chip processor cache level; typically ≈100× faster than main memory.

L2 Cache

Intermediate cache level, larger and slower than L1 but still faster than main memory.

L3 Cache

Large, slower cache (often shared across cores) that backs L2; still quicker than DRAM.

Cache Line (Block)

Fixed-size unit of data transferred between memory and cache.

Cache Hit

Event when requested data is found in the cache.

Cache Miss

Event when requested data is not in the cache and must be fetched from the next memory level.

Cold (Compulsory) Miss

Miss that occurs because the data has never been loaded into the cache.

Capacity Miss

Miss that occurs when the cache cannot contain the working set of a program.

Conflict Miss

Miss arising when multiple blocks compete for the same cache line(s) in direct-mapped or set-associative caches.

Fully Associative Cache

Placement policy where any memory block can be stored in any cache line.

Direct-Mapped Cache

Placement policy where each memory block maps to exactly one cache line, typically by index mod number-of-lines.

Set-Associative Cache

Placement policy where each block can reside in any line within a small set; e.g., 4-way allows four possible lines.

Placement Policy

Rule that decides where an incoming block can be placed in the cache.

Replacement Policy

Rule that selects which cache block to evict on a miss when the cache (or set) is full.

Least Recently Used (LRU)

Replacement policy that evicts the cache line that has not been accessed for the longest time.

Least Frequently Used (LFU)

Replacement policy that evicts the line with the fewest accesses.

First-In First-Out (FIFO)

Replacement policy that evicts lines in the same order they were brought into the cache.

Hit Ratio

Percentage of memory accesses served by the cache; key measure of cache efficiency.

Miss Penalty

Extra time required to fetch data from the next memory level after a miss.

Average Memory Access Time (AMAT)

hittime + missratio × miss_penalty

Working Set

Set of active memory blocks a program references during a given period.

Cache-Aside (Read-Aside)

Application checks cache; on miss it reads from DB and then writes result into cache.

Read-Through Cache

Cache itself fetches from DB on a miss, returns data to application, and stores it in cache automatically.

Write-Through

Write strategy that updates both cache and backing store simultaneously.

Write-Back

Write strategy that updates only the cache; memory is updated later when the line is evicted.

Write-Around

Write strategy that bypasses the cache and writes directly to main memory.

Miss Rate

1 − hit_ratio; probability that a cache access results in a miss.

Cache Eviction (Victim)

The block removed from cache to make room for a new block.