1 of 30

�Caches IV

Zoom link: cs61c.org/fa25/lecture-zoom

CS61C

UC Berkeley�Teaching Professor �Dan Garcia

cs61c.org

Great Ideas

in�Computer Architecture

(a.k.a. Machine Structures)

Garcia

Caches IV (1)

Garcia

2 of 30

Set-Associative Caches

Caches IV (2)

Garcia

3 of 30

N-Way Set Associative Cache (1/3)

Memory address fields:

Tag: same as before
Offset: same as before
Index: points us to the correct “row” (called a set in this case)

So what’s the difference?

each set contains multiple blocks
once we’ve found correct set, must compare with all tags in that set to find our data
Size of $ is # sets x N blocks/set x block size

Caches IV (3)

Garcia

4 of 30

Associative Cache Example

Here’s a simple 2-way set associative cache.

2 sets, 2 blocks in set

Memory

Memory �Address

Cache Index

Caches IV (4)

Garcia

Let’s look at the simplest cache one can build. A direct mapped cache that only has 4 bytes.

In this direct mapped cache with only 4 bytes, location 0 of the cache can be occupied by data form memory location 0, 4, 8, C, ... and so on.

While location 1 of the cache can be occupied by data from memory location 1, 5, 9, ... etc.

So in general, the cache location where a memory location can map to is uniquely determined by the 2 least significant bits of the address (Cache Index).

For example here, any memory location whose two least significant bits of the address are 0s can go to cache location zero.

With so many memory locations to chose from, which one should we place in the cache?

Of course, the one we have read or write most recently because by the principle of temporal locality, the one we just touch is most likely to be the one we will need again soon.

Of all the possible memory locations that can be placed in cache Location 0, how can we tell which one is in the cache?

+2 = 22 min. (Y:02)

5 of 30

N-Way Set Associative Cache (2/3)

Basic Idea

cache is direct-mapped w/respect to sets
each set is fully associative with N blocks in it

Given memory address:

Find correct set using Index value.
Compare Tag with all Tag values in that set.
If a match occurs, hit!, otherwise a miss.
Finally, use the offset field as usual to find the desired data within the block.

Caches IV (5)

Garcia

6 of 30

N-Way Set Associative Cache (3/3)

What’s so great about this?

even a 2-way set assoc cache avoids a lot of conflict misses
hardware cost isn’t that bad: only need N comparators

In fact, for a cache with M blocks,

it’s Direct-Mapped if it’s 1-way set assoc
it’s Fully Assoc if it’s M-way set assoc
so these two are just special cases of the more general set associative design

Caches IV (6)

Garcia

7 of 30

4-Way Set Associative Cache Circuit

tag

index

“One Hot” Encoding

🗹

Caches IV (7)

Garcia

8 of 30

Block Replacement with Example

Caches IV (8)

Garcia

9 of 30

Block Replacement Policy

Direct-Mapped Cache

index completely specifies position which position a block can go in on a miss

N-Way Set Assoc

index specifies a set, but block can occupy any position within the set on a miss

Fully Associative

block can be written into any position

Question: if we have the choice, where should we write an incoming block?

If there’s a valid bit off, write new block into first invalid.
If all are valid, pick a replacement policy

rule for which block gets “cached out” on a miss.

Caches IV (9)

Garcia

10 of 30

Block Replacement Policy

LRU (Least Recently Used)

Idea: cache out block which has been accessed (read or write) least recently
Pro: temporal locality 🡺 recent past use implies likely future use: in fact, this is a very effective policy
Con: with 2-way set assoc, easy to keep track (one LRU bit); with 4-way or greater, requires complicated hardware and much time to keep track of this

FIFO

Idea: ignores accesses, just tracks initial order

Random

If low temporal locality of workload, works ok

Caches IV (10)

Garcia

11 of 30

Block Replacement Example

Our same 2-way set associative cache with a four byte total capacity and one byte blocks. We perform the following byte accesses:

0, 2, 0, 1, 4, 0, 2, 3, 5, 4

How many hits and how many misses will there be for the LRU replacement policy?

loc 0

loc 1

set 0

set 1

Drawn another way

Caches IV (11)

Garcia

12 of 30

Block Replacement Example: LRU

Addresses 0, 2, 0, 1, 4, 0, ...

lru

loc 0

loc 1

set 0

set 1

lru

set 0

set 1

0: miss, bring into set 0 (loc 0)

2: miss, bring into set 0 (loc 1)

0: hit

1: miss, bring into set 1 (loc 0)

4: miss, bring into set 0 (loc 1, replace 2)

0: hit

set 0

set 1

lru

set 0

set 1

lru

set 0

set 1

lru

set 0

set 1

lru

Caches IV (12)

Garcia

13 of 30

Cache Simulator!

Addresses 0, 2, 0, 1, 4, 0, ...

lru

loc 0

loc 1

set 0

set 1

lru

set 0

set 1

set 0

set 1

lru

set 0

set 1

lru

set 0

set 1

lru

set 0

set 1

lru

🗹

www.ecs.umass.edu/ece/koren/architecture/Cache/frame1.htm

Should be compulsory

Caches IV (13)

Garcia

14 of 30

Average Memory Access Time (AMAT)

Caches IV (14)

Garcia

15 of 30

Big Idea

How to choose between associativity, block size, replacement & write policy?
Design against a performance model

Minimize: Average Memory Access Time

= Hit Time � + Miss Penalty x Miss Rate

influenced by technology & program behavior

Create the illusion of a memory that is large, cheap, and fast - on average
How can we improve miss penalty?

Caches IV (15)

Garcia

16 of 30

Improving Miss Penalty

When caches first became popular, Miss Penalty ~ 10 processor clock cycles
Today 3 GHz Processor (1/3 ns per clock cycle) and 80 ns to go to DRAM (~200 processor clock cycles!)

Proc

$₂

DRAM

MEM

Solution: another cache between memory and the processor cache: Second Level (L2) Cache

Caches IV (16)

Garcia

17 of 30

Great Idea #3: Principle of Locality / Memory Hierarchy

Extremely fast

Extremely expensive�Tiny capacity

Processor chip

Fast

Priced reasonably�Medium capacity

DRAM chip –e.g. �DDR3/4/5�HBM/HBM2/3

Faster

Expensive�Small capacity

Let’s see Cache configuration on Dan’s computer…

hw.cachelinesize: 128 (bytes)

hw.l1icachesize: 131072 (IMEM cache … 128 KiB = 2^17 B)

hw.l1dcachesize: 65536 (DMEM cache … 64 KiB = 2^16 B)

hw.l2cachesize: 4194304 (L2 cache … 4 MiB = 2^22 B)

Caches IV (17)

Garcia

18 of 30

Analyzing Multi-level cache hierarchy

Proc

$₂

DRAM

L1 hit

time

L1 Miss Rate

L1 Miss Penalty

Avg Mem Access Time =

L1 Hit Time + L1 Miss Rate * L1 Miss Penalty

L1 Miss Penalty =

L2 Hit Time + L2 Miss Rate * L2 Miss Penalty

Avg Mem Access Time =

L1 Hit Time + L1 Miss Rate * � (L2 Hit Time + L2 Miss Rate * L2 Miss Penalty)

L2 hit

time

L2 Miss Rate

L2 Miss Penalty

Caches IV (18)

Garcia

19 of 30

Example

Assume

Hit Time = 1 cycle
Miss rate = 5%
Miss penalty = 20 cycles
Calculate AMAT…

Avg mem access time

= 1 + 0.05 x 20

= 1 + 1 cycles

= 2 cycles

Caches IV (19)

Garcia

20 of 30

Ways to reduce miss rate

Larger cache

limited by cost and technology
hit time of first level cache < cycle time (bigger caches are slower)

More places in the cache to put each block of memory – associativity

fully-associative

any block any line

N-way set associated

N places for each block
direct map: N=1

Caches IV (20)

Garcia

21 of 30

Typical Scale

size: tens of KB
hit time: complete in one clock cycle
miss rates: 1-5%

size: hundreds of KB
hit time: few clock cycles
miss rates: 10-20%

L2 miss rate is fraction of L1 misses that also miss in L2

why so high?

Caches IV (21)

Garcia

22 of 30

Example: with L2 cache

Assume

L1 Hit Time = 1 cycle
L1 Miss rate = 5%
L2 Hit Time = 5 cycles
L2 Miss rate = 15% (% L1 misses that miss)
L2 Miss Penalty = 200 cycles

L1 miss penalty = 5 + 0.15 * 200 = 35
Avg mem access time = 1 + 0.05 x 35 � = 2.75 cycles

Caches IV (22)

Garcia

23 of 30

Example: without L2 cache

Assume

L1 Hit Time = 1 cycle
L1 Miss rate = 5%
L1 Miss Penalty = 200 cycles

Avg mem access time = 1 + 0.05 x 200� = 11 cycles

4x faster with L2 cache! (2.75 vs. 11)

🗹

Caches IV (23)

Garcia

24 of 30

Actual CPUs

Caches IV (24)

Garcia

25 of 30

An Actual CPU – Early PowerPC

Cache

32 KiB Instructions & 32 KiB Data L1 caches
External L2 Cache interface with integrated controller and cache tags, supports up to 1 MiB external L2 cache
Dual Memory Management Units (MMU) with Translation Lookaside Buffers (TLB)

Pipelining

Superscalar (3 inst/cycle)
6 execution units (2 integer and 1 double precision IEEE floating point)

Caches IV (25)

Garcia

26 of 30

An Actual CPU – Pentium M

32KiB I$

32KiB D$

Caches IV (26)

Garcia

27 of 30

An Actual CPU – Intel core i7

(for off-chip DRAM)

Caches IV (27)

Garcia

28 of 30

Caches IV (28)

Garcia

29 of 30

How can DM beat 2-way?

Sure, consider the caches from the previous slides (2-way set associative cache with a four-byte total capacity and one-byte blocks) with the following workload: ��0, 2, 0, 4, 2 �

2-way: 0m, 2m, 0h, 4m, 2m;

DM: 0m, 2m, 0h, 4m, 2h

Caches IV (29)

Garcia

30 of 30

And in Conclusion…

We’ve discussed memory caching in detail. Caching in general shows up over and over in computer systems

Filesystem cache, Web page cache, Game databases / tablebases, Software memoization, Others?

Big idea: if something is expensive but we want to do it repeatedly, do it once and cache the result.
Cache design choices:

Size of cache: speed v. capacity
Block size (i.e., cache aspect ratio)
Write Policy (Write through v. write back
Associativity choice of N (direct-mapped v. set v. fully associative)
Block replacement policy
2nd level cache?
3rd level cache?

Use performance model to pick between choices, depending on programs, technology, budget, ...

Caches IV (30)

Garcia