Question

Given an 8-word, direct mapped cache, and the sequence of address accesses below, enter the number of misses.

CACHE CONFIG

24
13
24
10
8
8

Given an 8-word, 2-way set associative cache, and the sequence of address accesses below, enter the number of misses.

CACHE CONFIG
22
1
9
22
22
22

Given an 8-word, 2-way set associative cache, and the sequence of address accesses below, enter the number of misses.

CACHE CONFIG
23
23
8
20
9
20

Given an 8-word, direct mapped cache, and the sequence of address accesses below, enter the number of misses.

CACHE CONFIG
5
23
1
24
23
11

Given an 8-word, 4-way set associative cache, and the sequence of address accesses below, enter the number of misses.

CACHE CONFIG
4
4
12
23
12
4

Answer 1

Direct Mapped:(8 word)

Sequence = { 24, 13, 24, 10, 8, 8 } , addresses will be placed in the block no. (address % 8).

for 24: it will be placed in 24 % 8 = 0; '24' will be placed in 0th block; ==> 1st miss;

for 13: 13 % 8 = 5; will be in 5th block ==> 2nd miss;

for 24: 24 is already present, so cache hit.

for 10: 10 % 8 = 2; will be in 2nd block ==>3rd miss

for 8: 8 % 2 = 0; 0th block is occupied by 24, so replace it by 8 ==> 4th miss

again 8: 8 is already present, so cache hit.

So Total: 4 miss.

0	24 / 8
1
2	10
3
4
5	13
6
7

2-way set associative(8 word):

Sequence: { 22, 1, 9, 22, 22, 22 }:

Here no of sets: 8/2 = 4 no. of sets.

So addresses will be mapped to any one of these sets. and can be placed any of the two blocks;

for 22: 22 % 4 = 2; place it in 2nd set, 4th block, ==> 1 miss;

for 1: 1 % 4 = 1; in 1st set; in 2nd block; ==> 1 miss;

for 9: 9 % 4 = 1; in 1st set; in 3rd block as it is empty; ==> 1 miss;

for 22: already present in cache; ==>cache hit;

for 22: already present in cache; ==>cache hit;

for 22: already present in cache; ==>cache hit;

So Total = 3 miss;

set 0	0
	1

set 1	2	1
	3	9

set 2	4	22
	5

set 3	6
	7

2-way set associative(8 word):

Sequence: { 23, 23, 8, 20, 9, 20 }:

Here no of sets: 8/2 = 4 no. of sets.

So addresses will be mapped to any one of these sets. and can be placed any of the two blocks;

for 23: 23 % 4 = 3; place it in 3rd set, 6th block, ==> 1 miss;

for 23: already present. ==> cache hit

for 8: 8 % 4 = 0; in 0th set; in 0th block; ==> 1 miss;

for 20: 20 % 4 = 0; in 0th set; in 1st block; ==> 1 miss

for 9: 9 % 4 = 1; in 1st set; in 2nd block; ==> 1 miss

for 20: already present in cache; ==>cache hit;

So Total = 4 miss;

set 0	0	8
	1	20

set 1	2	9
	3

set 2	4
	5

set 3	6	23
	7

Direct Mapped:(8 word):

Sequence = { 5, 23, 1, 24, 23, 11 } , addresses will be placed in the block no. (address % 8).

for 5: it will be placed in 5 % 8 = 5; '5' will be placed in 5th block; ==> 1st miss;

for 23: 23 % 8 = 7; will be in 7th block ==> 2nd miss;

for 1: 1 % 8 = 1; will be in 1st block ==> 3rd miss;

for 24: 24 % 8 = 0; will be in 0th block ==> 4th miss;

for 23: already present. ==>cache hit

for 11: 11 % 8 =3; will be in 3rd block; ==> 5th miss;

So Total: 5 miss.

0	24
1	1
2
3	11
4
5	5
6
7	23

4-way set associative(8 word):

Sequence: { 4, 4, 12, 23, 12, 4}:

Here no of sets: 8/4 = 2 no. of sets.

So addresses will be mapped to any one of these sets. and can be placed in any of the four blocks;

for 4: 4 % 2 = 0; place it in 0th set and 0th block; ==> 1 miss

for 4: already present. ==> cache hit

for 12: 12 % 2 = 0; place it in 0th set and 1st block; ==> 1 miss

for 23: 23 % 2 = 1; in 1st set; in 4th block; ==> 1 miss

for 12: already present. ==> cache hit

for 4: already present in cache; ==>cache hit;

So Total = 3 miss;

set 0	0	4
	1	12
	2
	3

set 1	4	23
	5
	6
	7