Caches

Table of Contents

A note on capacity misses Slide 3

Example 1: small, direct-mapped cache Slide 4

Example 2: small, fully-associative cache Slide 15

​

A note on conflict vs. capacity misses

How do I know if it’s a capacity miss?

If n blocks fit in our cache, and we are accessing the (n+1)st unique block, then this is a capacity miss! Because in a fully-associative cache with an LRU replacement policy (not necessarily all fully-associative caches, depending on the replacement policy chosen!) this would cause a miss.

See the flowchart on the next page!

Flowchart

Example 1: small, direct-mapped cache

Memory size: 32B

Cache size: 8B

Block size: 4B (1 word)

​

Total address bits?

Index bits?

Offset bits?

Tag bits?

Example 1: small, direct-mapped cache

Memory size: 32B

Cache size: 8B

Block size: 4B (1 word)

​

Total address bits? log₂(# bytes in memory) = log₂(32) = 5 bits

Index bits? log₂(# sets in cache) = log₂(# blocks in direct mapped cache) = log₂(8/4) = log₂(2) = 1 bit

Offset bits? log₂(# bytes in one block) log₂(4) = 2 bits

Tag bits? Total address bits - index bits - offset bits = 5 - 1 - 2 = 2 bits

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses: imagine each access is for a character stored at that address, and characters are one byte

1. 00001
2. 00000
3. 00010
4. 00100
5. 01100
6. 00100
7. 11010
8. 11011
9. 00011

Index

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Index

Data is stored little-endian: at address 0b11100, the word stored is 0xFA235262 in hex.

​

FA is the MSB (most significant byte) and has address 0b1111

​

62 is the LSB (least significant byte) and has address 0b11100.

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Index Offset

00 0 01

​

Compulsory miss

Index

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Index Offset

00 0 00

​

Hit

Index

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Index Offset

00 0 10

​

Hit

Index

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00000
• 00001
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Index Offset

00 1 00

​

Compulsory miss

Index

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00000
• 00001
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Index Offset

01 1 00

​

Compulsory miss

Index

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00000
• 00001
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Index Offset

00 1 00

​

Capacity miss

​

Even though the block with tag 00 and index 0 was pulled into the cache on access 1, we have looked at 3 unique blocks from memory already. Our cache can hold a maximum of 2 unique blocks, so in some fully associative caches, we still would have had a miss here. This leads to a capacity miss.

Index

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00000
• 00001
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Index Offset

11 0 10

​

Compulsory miss

Index

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00000
• 00001
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Index Offset

11 0 11

​

Hit

Index

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00000
• 00001
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Index Offset

00 0 11

​

Capacity miss

​

Even though the block with tag 00 and index 0 was pulled into the cache on access 1, we have looked at 5 unique blocks from memory already. Our cache can hold a maximum of 2 unique blocks, so in some fully associative caches, we still would have had a miss here. This leads to a capacity miss.

​

Index

Hit & Miss Rate

Total memory accesses: 9

Hits: 3

Misses: 6

​

Hit rate = 3/9 = 33.33333… %

Miss rate = 6/9 = 66.6666… %

Example 2: small, fully-associative cache

Memory size: 32B

Cache size: 8B

Block size: 4B (1 word)

Replacement Policy: FIFO (first in, first out)

​

Total address bits?

Index bits?

Offset bits?

Tag bits?

Example 2: small, fully-associative cache

Memory size: 32B

Cache size: 8B

Block size: 4B (1 word)

Replacement policy: FIFO (first in, first out)

​

Total address bits? log₂(# bytes in memory) = log₂(32) = 5 bits

Index bits? log₂(# sets in cache) = log₂(1 in a fully associative cache) = 0 bits

Offset bits? log₂(# bytes in one block) log₂(4) = 2 bits

Tag bits? Total address bits - index bits - offset bits = 5 - 0 - 2 = 3 bits

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Offset

000 01

​

Compulsory miss

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Offset

000 00

​

Hit

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Offset

000 10

​

Hit

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Offset

001 00

​

Compulsory miss

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Offset

011 00

​

Compulsory miss

​

Tag 000 came in before Tag 001, so this is the block in the cache that we replaced (FIFO)

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Offset

001 00

​

Hit

​

In the direct-mapped cache, this was a conflict miss

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Offset

110 10

​

Compulsory miss

​

Tag 001 came in before Tag 011, so this is the block in the cache that we replace (FIFO)

​

​

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Offset

110 11

​

Hit

​

​

​

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

Memory accesses:

• 00001
• 00000
• 00010
• 00100
• 01100
• 00100
• 11010
• 11011
• 00011

Tag Offset

000 11

​

Capacity miss

​

The block with tag 000 was previously pulled into the cache on access 1, but was kicked out due to a lack of space; if the cache were bigger, it would still be there

​

​

​

Hit & Miss Rate

Total memory accesses = 9

Hits: 4

Misses: 5

​

Hit rate = 4/9 = 44.4444… %

Miss rate = 5/9 = 55.5555… %

Extra Slides

Example 3: bigger, 4-way associative cache

Memory size: 4096B

Cache size: 128B

Block size: 16B (4 words)

​

Total address bits?

Index bits?

Offset bits?

Tag bits?

​

Example 3: bigger, 4-way associative cache

Memory size: 4096B

Cache size: 128B

Block size: 16B (4 words)

​

Total address bits? log₂(4096) = 12 bits

Index bits? log₂(128/(16*4)) = log₂(2) = 1 bit

Offset bits? log₂(16) = 4 bits

Tag bits? 12 - 1 - 4 = 7 bits

​

Memory

Address

Memory Contents

Tag

Cache Contents

Cache

...

Memory accesses:

1. 0x007
2. 0x4AA
3. 0x

...