Discussion 8: Caches
March 21, 2019

Attendance:

tinyurl.com/cacheorcheck

Question 1:

32 byte direct-mapped cache

Question 1:

32 byte direct-mapped cache

8 byte block size

Question 1:

32 byte direct-mapped cache

8 byte block size

ONE BLOCK

Question 1:

32 byte direct-mapped cache

8 byte block size

ONE BLOCK = 3 bits/offset

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11100000

ONE BLOCK = 3 bits/offset

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11100001

ONE BLOCK = 3 bits/offset

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11100010

ONE BLOCK = 3 bits/offset

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11100011

ONE BLOCK = 3 bits/offset

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11100100

ONE BLOCK = 3 bits/offset

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11100101

ONE BLOCK = 3 bits/offset

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11100110

ONE BLOCK = 3 bits/offset

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11100111

ONE BLOCK = 3 bits/offset

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11100111

FOUR BLOCKS

2 bits/index

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11100111

FOUR BLOCKS

2 bits/index

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11100111

FOUR BLOCKS

2 bits/index

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11101111

FOUR BLOCKS

2 bits/index

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11110111

FOUR BLOCKS

2 bits/index

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11111111

FOUR BLOCKS

2 bits/index

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11111111

NOTE THAT CACHE IS SMALLER THAN MEMORY!

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11111111

NOTE THAT CACHE IS SMALLER THAN MEMORY!

32B (size of cache) < 256B (size of mem)

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11111111

NOTE THAT CACHE IS SMALLER THAN MEMORY!

32B (size of cache) < 256B (size of mem)

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b11011111

NOTE THAT CACHE IS SMALLER THAN MEMORY!

32B (size of cache) < 256B (size of mem)

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b10111111

NOTE THAT CACHE IS SMALLER THAN MEMORY!

32B (size of cache) < 256B (size of mem)

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b10011111

NOTE THAT CACHE IS SMALLER THAN MEMORY!

32B (size of cache) < 256B (size of mem)

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b01111111

NOTE THAT CACHE IS SMALLER THAN MEMORY!

32B (size of cache) < 256B (size of mem)

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b01011111

NOTE THAT CACHE IS SMALLER THAN MEMORY!

32B (size of cache) < 256B (size of mem)

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b00111111

NOTE THAT CACHE IS SMALLER THAN MEMORY!

32B (size of cache) < 256B (size of mem)

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b00011111

NOTE THAT CACHE IS SMALLER THAN MEMORY!

32B (size of cache) < 256B (size of mem)

00

01

10

11

Question 1:

32 byte direct-mapped cache

8 byte block size

Memory Address: 0b00011111

NOTE THAT CACHE IS SMALLER THAN MEMORY!

32B (size of cache) < 256B (size of mem)

Remaining bits are used to “tag” the item in cache (hence called tag bits)

00

01

10

11

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

0x00000005

0x00000068

0x000000C8

0x00000068

0x000000DD

0x00000045

0x00000004

0x000000C8

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

0x00000005

...00000

00

101

0x00000068

...00011

01

000

0x000000C8

...00110

01

000

0x00000068

...00011

01

000

0x000000DD

...00110

11

101

0x00000045

...00010

00

101

0x00000004

...00000

00

100

0x000000C8

...00110

01

000

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

0x00000005

...00000

00

101

0x00000068

...00011

01

000

0x000000C8

...00110

01

000

0x00000068

...00011

01

000

0x000000DD

...00110

11

101

0x00000045

...00010

00

101

0x00000004

...00000

00

100

0x000000C8

...00110

01

000

Index

Tag

00

01

10

11

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

0x00000068

...00011

01

000

0x000000C8

...00110

01

000

0x00000068

...00011

01

000

0x000000DD

...00110

11

101

0x00000045

...00010

00

101

0x00000004

...00000

00

100

0x000000C8

...00110

01

000

Index

Tag

00

....00000

01

10

11

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

0x000000C8

...00110

01

000

0x00000068

...00011

01

000

0x000000DD

...00110

11

101

0x00000045

...00010

00

101

0x00000004

...00000

00

100

0x000000C8

...00110

01

000

Index

Tag

00

....00000

01

10

11

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

0x00000068

...00011

01

000

0x000000DD

...00110

11

101

0x00000045

...00010

00

101

0x00000004

...00000

00

100

0x000000C8

...00110

01

000

Index

Tag

00

...00000

01

...00011

10

11

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

0x000000DD

...00110

11

101

0x00000045

...00010

00

101

0x00000004

...00000

00

100

0x000000C8

...00110

01

000

Index

Tag

00

...00000

01

...00110

10

11

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

0x00000045

...00010

00

101

0x00000004

...00000

00

100

0x000000C8

...00110

01

000

Index

Tag

00

...00000

01

...00011

10

11

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

0x00000004

...00000

00

100

0x000000C8

...00110

01

000

Index

Tag

00

...00000

01

...00011

10

11

...00110

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

0x000000C8

...00110

01

000

Index

Tag

00

...00010

01

...00011

10

11

...00110

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

Miss w/ Repl.

0x000000C8

...00110

01

000

Index

Tag

00

...00000

01

...00011

10

11

...00110

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

Miss w/ Repl.

0x000000C8

...00110

01

000

Miss w/ Repl.

Index

Tag

00

...00000

01

...00110

10

11

...00110

3 Types of Misses

3 Types of Misses

Compulsory Miss: A miss that must occur when you first bring in a block. Can be reduced by making blocks bigger (so you bring in more other items).

3 Types of Misses

Compulsory Miss: A miss that must occur when you first bring in a block. Can be reduced by making blocks bigger (so you bring in more other items).

Conflict Miss: Occurs when the item was previously in the block, but got kicked out earlier because there wasn’t enough space in the index (and there would’ve been in a FA cache). Can be reduced by increasing cache associativity.

3 Types of Misses

Compulsory Miss: A miss that must occur when you first bring in a block. Can be reduced by making blocks bigger (so you bring in more other items).

Conflict Miss: Occurs when the item was previously in the block, but got kicked out earlier because there wasn’t enough space in the index (and there would’ve been in a FA cache). Can be reduced by increasing cache associativity.

Capacity Miss: Occurs when item was previously in cache, but got kicked out because cache is full. Can be reduced by buying a computer with a bigger cache.

Classify each of the following misses as compulsory, conflict, or capacity:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

Miss w/ Repl.

0x000000C8

...00110

01

000

Miss w/ Repl.

Classify each of the following misses as compulsory, conflict, or capacity:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

Miss w/ Repl.

0x000000C8

...00110

01

000

Miss w/ Repl.

Compulsory

Index

Tag

00

....00000

01

10

11

Classify each of the following misses as compulsory, conflict, or capacity:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

Miss w/ Repl.

0x000000C8

...00110

01

000

Miss w/ Repl.

Compulsory

Index

Tag

00

...00000

01

...00011

10

11

Classify each of the following misses as compulsory, conflict, or capacity:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

Miss w/ Repl.

0x000000C8

...00110

01

000

Miss w/ Repl.

Compulsory

Index

Tag

00

...00000

01

...00110

10

11

Classify each of the following misses as compulsory, conflict, or capacity:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

Miss w/ Repl.

0x000000C8

...00110

01

000

Miss w/ Repl.

Conflict

Index

Tag

00

...00000

01

...00011

10

11

Classify each of the following misses as compulsory, conflict, or capacity:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

Miss w/ Repl.

0x000000C8

...00110

01

000

Miss w/ Repl.

Compulsory

Index

Tag

00

...00000

01

...00011

10

11

...00110

Classify each of the following misses as compulsory, conflict, or capacity:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

Miss w/ Repl.

0x000000C8

...00110

01

000

Miss w/ Repl.

Compulsory

Index

Tag

00

...00010

01

...00011

10

11

...00110

Classify each of the following misses as compulsory, conflict, or capacity:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

Miss w/ Repl.

0x000000C8

...00110

01

000

Miss w/ Repl.

Conflict

Capacity
(see slide 56)

Index

Tag

00

...00000

01

...00011

10

11

...00110

Classify each of the following misses as compulsory, conflict, or capacity:

Memory

Tag

Index

Offset

Access Type?

0x00000004

...00000

00

100

Miss

0x00000005

...00000

00

101

Hit

0x00000068

...00011

01

000

Miss

0x000000C8

...00110

01

000

Miss w/ Repl.

0x00000068

...00011

01

000

Miss w/ Repl.

0x000000DD

...00110

11

101

Miss

0x00000045

...00010

00

101

Miss w/ Repl.

0x00000004

...00000

00

100

Miss w/ Repl.

0x000000C8

...00110

01

000

Miss w/ Repl.

Conflict

Capacity
(see slide 56)

Index

Tag

00

...00000

01

...00110

10

11

...00110

Reasons why the last two are CAPACITY, not CONFLICT misses

When labelling cache misses, “capacity” takes precedence over “conflict” misses. The criteria for a “capacity” miss is that, should the cache have been a fully associative cache, the miss would have happened anyways.


In the previous two examples, had we had a fully associative cache, we would have had the blocks corresponding to memory addresses 0x68, 0xC8, 0xDD, and 0x45 loaded in in that order. Thus, 0x04 would have been kicked out anyways, even in a FA cache.

When we then load in 0x04, we need to kick out 0xC8 because that was the least recently used block (0x68 was added in first, but was called after 0xC8). Thus, when we would have loaded in 0xC8 in a FA cache, we still would have had a miss. Apologies for the confusion!

A[0]

A[128]

A[255]

Cache block

A[256]

A[384]

A[511]

Cache block

A[0]

A[128]

A[255]

Cache block

A[256]

A[384]

A[511]

Cache block

A[0]

A[128]

A[256]

A[384]

A[512]

A[640]

...

Miss

Hit

Miss

Hit

Miss

Hit

...

A[0]

A[128]

A[255]

Cache block

A[256]

A[384]

A[511]

Cache block

A[0]

A[128]

A[256]

A[384]

A[512]

A[640]

...

Miss

Hit

Miss

Hit

Miss

Hit

...

50%

A[0]

A[128]

A[255]

Cache block

A[256]

A[384]

A[511]

Cache block

A[0]

A[128]

A[255]

Cache block

A[256]

A[384]

A[511]

Cache block

A[0]

A[128]

A[256]

A[384]

A[512]

A[640]

...

Miss

Hit

Miss

Hit

Miss

Hit

...

A[0]

A[128]

A[255]

Cache block

A[256]

A[384]

A[511]

Cache block

A[0]

A[128]

A[256]

A[384]

A[512]

A[640]

...

Miss

Hit

Miss

Hit

Miss

Hit

...

50%

Question 4:

32 byte 2-way set associative cache

8 byte block size

2 SETS of 2 BLOCKS

1 bit/index

0

0

1

1

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0b0000 0100

0b0000 0101

0b0110 1000

0b1100 1000

0b0110 1000

0b1101 1101

0b0100 0100

0b0000 0100

0b1100 1000

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0b0000 0100

0000

0

100

0b0000 0101

0000

0

101

0b0110 1000

0110

1

000

0b1100 1000

1100

1

000

0b0110 1000

0110

1

000

0b1101 1101

1101

1

101

0b0100 0100

0100

0

100

0b0000 0100

0000

0

100

0b1100 1000

1100

1

000

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0b0000 0100

0000

0

100

0b0000 0101

0000

0

101

0b0110 1000

0110

1

000

0b1100 1000

1100

1

000

0b0110 1000

0110

1

000

0b1101 1101

1101

1

101

0b0100 0100

0100

0

100

0b0000 0100

0000

0

100

0b1100 1000

1100

1

000

Ind.

Tag 1

Tag 2

0

1

Classify each of the following accesses as either a hit, miss, or miss w/ replacement:

Memory

Tag

Index

Offset

Access Type?

0b0000 0100

0000

0

100

Miss

0b0000 0101