�Caches III

CS61C

UC Berkeley�Teaching Professor �Dan Garcia

cs61c.org

Great Ideas

in�Computer Architecture

(a.k.a. Machine Structures)

Garcia

Caches III (1)

Garcia

Direct Mapped Example

Caches III (2)

Garcia

Accessing data in a direct mapped cache

• Ex.: 16KB of data, direct-mapped, �4 word blocks
• Can you work out height, width, area?
• Read 4 addresses
1. 0x00000014
2. 0x0000001C
3. 0x00000034
4. 0x00008014
• Memory values here:

Address (hex)

Value of Word

Memory

Caches III (3)

Garcia

Caches III (3)

Garcia

Accessing data in a direct mapped cache

• 4 Addresses:
• 0x00000014, 0x0000001C, �0x00000034, 0x00008014
• 4 Addresses divided (for convenience) into Tag, Index, Byte Offset fields

000000000000000000 0000000001 0100

000000000000000000 0000000001 1100

000000000000000000 0000000011 0100

000000000000000010 0000000001 0100� Tag Index Offset

Caches III (4)

Garcia

Example: 16 KB Direct-Mapped Cache, 16B blocks

• Valid bit: determines whether anything is stored in that row (when computer initially powered up, all entries invalid)

...

Index

Caches III (5)

Garcia

1. Read 0x00000014

• 000000000000000000 0000000001 0100

Tag Index Offset

...

Index

Caches III (6)

Garcia

So we read block 1 (0000000001)

• 000000000000000000 0000000001 0100

...

Index

Tag Index Offset

Caches III (7)

Garcia

No valid data

• 000000000000000000 0000000001 0100

...

Index

Tag Index Offset

Caches III (8)

Garcia

So load that data into cache, setting tag, valid

• 000000000000000000 0000000001 0100

...

Index

0

d

c

b

a

Tag Index Offset

Caches III (9)

Garcia

Read from cache at offset, return word b�

• 000000000000000000 0000000001 0100

...

Index

0

d

c

b

a

Tag Index Offset

Caches III (10)

Garcia

2. Read 0x0000001C = 0…00 0..001 1100

• 000000000000000000 0000000001 1100

​

...

Index

0

d

c

b

a

Tag Index Offset

Caches III (11)

Garcia

Index is Valid

• 000000000000000000 0000000001 1100

​

...

Index

0

d

c

b

a

Tag Index Offset

Caches III (12)

Garcia

Index is Valid, Tag Matches

• 000000000000000000 0000000001 1100

​

...

Index

0

d

c

b

a

Tag Index Offset

Caches III (13)

Garcia

Index is Valid, Tag Matches, return d

• 000000000000000000 0000000001 1100

​

...

Index

0

d

c

b

a

Tag Index Offset

Caches III (14)

Garcia

3. Read 0x00000034 = 0…00 0..011 0100

• 000000000000000000 0000000011 0100

​

​

...

Index

0

d

c

b

a

Tag Index Offset

Caches III (15)

Garcia

So read block 3

• 000000000000000000 0000000011 0100

​

​

...

Index

0

d

c

b

a

Tag Index Offset

Caches III (16)

Garcia

No valid data

• 000000000000000000 0000000011 0100

​

​

...

Index

0

d

c

b

a

Tag Index Offset

Caches III (17)

Garcia

Load that cache block, return word f

• 000000000000000000 0000000011 0100

​

​

...

Index

0

d

c

b

a

0

h

g

f

e

Tag Index Offset

Caches III (18)

Garcia

4. Read 0x00008014 = 0…10 0..001 0100

• 000000000000000010 0000000001 0100

​

​

​

...

Index

0

d

c

b

a

0

h

g

f

e

Tag Index Offset

Caches III (19)

Garcia

So read Cache Block 1, Data is Valid

• 000000000000000010 0000000001 0100

​

​

​

...

Index

0

d

c

b

a

0

h

g

f

e

Tag Index Offset

Caches III (20)

Garcia

Cache Block 1 Tag does not match (0 ≠ 2)

• 000000000000000010 0000000001 0100

​

​

​

...

Index

0

d

c

b

a

0

h

g

f

e

Tag Index Offset

Caches III (21)

Garcia

Miss, so replace block 1 with new data & tag

• 000000000000000010 0000000001 0100

​

​

​

...

Index

2

l

k

j

i

0

h

g

f

e

Tag Index Offset

Caches III (22)

Garcia

And return word j

• 000000000000000010 0000000001 0100

​

​

​

...

Index

2

l

k

j

i

0

h

g

f

e

Tag Index Offset

Caches III (23)

Garcia

Do an example yourself. What happens?

• Chose from: Cache: Hit, Miss, Miss w. replace�Values returned: a ,b, c, d, e, ..., k, l
• Read address 0x00000030 ? � 000000000000000000 0000000011 0000

Index

2

l

k

j

i

0

h

g

f

e

Caches III (24)

Garcia

Caches III (25)

Garcia

Do an example yourself. What happens?

• Chose from: Cache: Hit, Miss, Miss w. replace�Values returned: a ,b, c, d, e, ..., k, l

​

​

• Read address 0x0000001c ?� 000000000000000000 0000000001 1100

Index

2

l

k

j

i

0

h

g

f

e

Caches III (26)

Garcia

Caches III (27)

Garcia

Answers

• 0x00000030 a hit

Index = 3, Tag matches, �Offset = 0, value = e

• 0x0000001c a miss

Index = 1, Tag mismatch, so replace from memory, �Offset = 0xc, value = d

• Since reads, values �must = memory values �whether or not cached:
• 0x00000030 = e
• 0x0000001c = d

Address (hex)

Value of Word

Memory

00000010

00000014

00000018

0000001C

a

b

c

d

...

...

00000030

00000034

00000038

0000003C

e

f

g

h

00008010

00008014

00008018

0000801C

i

j

k

l

🗹

Caches III (28)

Garcia

Caches III (28)

Garcia

Writes, Block Sizes, Misses

Caches III (29)

Garcia

Multiword-Block Direct-Mapped Cache

• Four words/block, cache size = 4K words�

What kind of locality are we taking advantage of?

Caches III (30)

Garcia

What to do on a write hit?

• Write-through
• Update both cache and memory
• Write-back
• update word in cache block
• allow memory word to be “stale”
• 🡺 add ‘dirty’ bit to block
• memory & Cache inconsistent
• needs to be updated when block is replaced
• …OS flushes cache before I/O…
• Performance trade-offs?

Caches III (31)

Garcia

Block Size Tradeoff

• Benefits of Larger Block Size
• Spatial Locality: if we access a given word, we’re likely to access other nearby words soon
• Very applicable with Stored-Program Concept
• Works well for sequential array accesses
• Drawbacks of Larger Block Size
• Larger block size means larger miss penalty
• on a miss, takes longer time to load a new block from next level
• If block size is too big relative to cache size, then there are too few blocks
• Result: miss rate goes up

Caches III (32)

Garcia

Extreme Example: One Big Block

​

​

• Cache Size = 4 bytes Block Size = 4 bytes
• Only ONE entry (row) in the cache!
• If item accessed, likely accessed again soon
• But unlikely will be accessed again immediately!
• The next access will likely to be a miss again
• Continually loading data into the cache but�discard data (force out) before use it again
• Nightmare for cache designer: Ping Pong Effect

Caches III (33)

Garcia

Block Size Tradeoff Conclusions

Caches III (34)

Garcia

Types of Cache Misses (1/2)

• “Three Cs” Model of Misses
• 1^st C: Compulsory Misses
• occur when a program is first started
• cache does not contain any of that program’s data yet, so misses are bound to occur
• can’t be avoided easily, so won’t focus on these in this course
• Every block of memory will have one compulsory miss (NOT only every block of the cache)

Caches III (35)

Garcia

Types of Cache Misses (2/2)

• 2^nd C: Conflict Misses
• miss that occurs because two distinct memory addresses map to the same cache location
• two blocks (which happen to map to the same location) can keep overwriting each other
• big problem in direct-mapped caches
• how do we lessen the effect of these?
• Dealing with Conflict Misses
• Solution 1: Make the cache size bigger
• Fails at some point
• Solution 2: Multiple distinct blocks can fit in the same cache Index?

🗹

Caches III (36)

Garcia

Fully Associative Caches

Caches III (37)

Garcia

Fully Associative Cache (1/3)

• Memory address fields:
• Tag: same as before
• Offset: same as before
• Index: non-existant
• What does this mean?
• no “rows”: any block can go anywhere in the cache
• must compare with all tags in entire cache to see if data is there

Caches III (38)

Garcia

Fully Associative Cache (2/3)

• Fully Associative Cache (e.g., 32 B block)
• compare tags in parallel

Caches III (39)

Garcia

Fully Associative Cache (3/3)

• Benefit of Fully Assoc Cache
• No Conflict Misses (since data can go anywhere)
• Drawbacks of Fully Assoc Cache
• Need hardware comparator for every single entry: if we have a 64KB of data in cache with 4B entries, we need 16K comparators: infeasible

Caches III (40)

Garcia

Final Type of Cache Miss

• 3^rd C: Capacity Misses
• miss that occurs because the cache has a limited size
• miss that would not occur if we increase the size of the cache
• sketchy definition, so just get the general idea
• This is the primary type of miss for Fully Associative caches.

Caches III (41)

Garcia

How to categorize misses

• Run an address trace against a set of caches:
• First, consider an infinite-size, fully-associative cache. For every miss that occurs now, consider it a compulsory miss.
• Next, consider a finite-sized cache (of the size you want to examine) with full-associativity. Every miss that is not in #1 is a capacity miss.
• Finally, consider a finite-size cache with finite-associativity. All of the remaining misses that are not #1 or #2 are conflict misses.
• (Thanks to Prof. Kubiatowicz for the algorithm)

Caches III (42)

Garcia

Caches III (43)

Garcia

And in Conclusion…

1. Divide into T I O bits, Go to Index = I, check valid
1. If 0, load block, set valid and tag (COMPULSORY MISS) and use offset to return the right chunk (1,2,4-bytes)
2. If 1, check tag
1. If Match (HIT), use offset to return the right chunk
2. If not (CONFLICT MISS), load block, set valid and tag, use offset to return the right chunk

🗹

Caches III (44)

Garcia