Memory Hierarchy

Memory Hierarchy— Misses, 3 Cs

and 7 Ways to Reduce Misses

Classifying Misses: 3 Cs

– Compulsory—The first access to a block is not in the

cache, so the block must be brought into the cache.

These are also called cold start misses or first

reference misses.

(Misses in Infinite Cache)

– Capacity—If the cache cannot contain all the blocks

needed during execution of a program, capacity

misses will occur due to blocks being discarded and

later retrieved.

(Misses in optimally-organized Finite Cache)

– Conflict—If the block-placement strategy is set

associative or direct mapped, conflict misses (in

addition to compulsory and capacity misses) will occur

because a block can be discarded and later retrieved if

too many blocks map to its set. These are also called

collision misses or interference misses.

(Misses in N-way Associative, Finite Cache)

---------------------------------------------------

Technique MR MP HT Complexity

Larger Block Size + – n 0

Higher Associativity + n – 1

Victim Caches + n n 2

Pseudo-Associative Caches + n n 2

HW Prefetching of Instr/Data + n n 2

Compiler Controlled Prefetching + n n 3

Compiler Reduce Misses + n n 0

Priority to Read Misses n + n 1

Subblock Placement n + + 1

Early Restart & Critical Word 1 n + n 2

Non-Blocking Caches n + n 3

Second Level Caches n + n 2

Small & Simple Caches – n + 0

Avoiding Address Translation n n + 2

Pipelining Writes n n + 1

Reducing Miss Rate

1. Reduce Misses via Larger Block Size

2. Reduce Conflict Misses via Higher Associativity

3. Reducing Conflict Misses via Victim Cache

4. Reducing Conflict Misses via Pseudo-Associativity

5. Reducing Misses by HW Prefetching Instr, Data

6. Reducing Misses by SW Prefetching Data

7. Reducing Capacity/Conf. Misses by Compiler Optimizations

-----------------------------------------

Miss Rate

********************

1. Reduce Misses via Larger

Block Size

------------------------------

2. Reduce Misses via Higher...