Suppose we have a 16 block cache. Each block of the cache is one word wide. When
ID: 3767914 • Letter: S
Question
Suppose we have a 16 block cache. Each block of the cache is one word wide. When a given program is executed, the processor reads data from the following sequence of decimal addresses:
2, 5, 7, 2, 13, 21, 17, 19, 6, 25, 2, 17, 21, 7, 13
Show the contents of the cache at the end of the above reading operations if:
the cache is direct mapped
the cache is 2-way set associative
the cache is 4-way set associative
the cache is fully associative
The content at address 0 can be shown as [0]. Assume LRU (Least Recently Used) replacement algorithm is used for block replacement in the cache, and the cache is initially empty.
Explanation / Answer
Suppose we have a 16 block cache. Each block of the cache is one word wide. When a given program is executed, the processor reads data from the following sequence of decimal addresses:
2, 5, 7, 2, 13, 21, 17, 19, 6, 25, 2, 17, 21, 7, 13
Show the contents of the cache at the end of the above reading operations if:
the cache is direct mapped
Address reference
Binary address
Hit/Miss
Assigned cache block
2
0010
Miss
0010
5
0101
Miss
0101
7
0111
Miss
0111
2
0010
Miss
0010
13
1101
Miss
1101
21
10101
Miss
0101
17
10001
Miss
0001
19
10011
Miss
0011
6
0110
Miss
0110
25
11001
Miss
1001
2
0010
Hit
0010
17
10001
Hit
0001
21
10101
Miss
0101
7
0111
Hit
0111
13
1101
Hit
1101
Final contents of the Cache after refrences :
Index
Contents
0000
0001
M(17)
0010
M(2)
0011
M(19)
0100
0101
M(21)
0110
M(6)
0111
M(7)
1000
1001
M(25)
1010
1011
1100
Suppose we have a 16 block cache. Each block of the cache is one word wide. When a given program is executed, the processor reads data from the following sequence of decimal addresses:
2, 5, 7, 2, 13, 21, 17, 19, 6, 25, 2, 17, 21, 7, 13
Show the contents of the cache at the end of the above reading operations if:
the cache is 2-way set associative
Address reference
Binary address
Hit/Miss
Assigned cache block
2
0010
Miss
010
5
0101
Miss
101
7
0111
Miss
111
2
0010
Miss
010
13
1101
Miss
101
21
10101
Miss
101
17
10001
Miss
001
19
10011
Miss
011
6
0110
Miss
110
25
11001
Miss
001
2
0010
Hit
010
17
10001
Hit
001
21
10101
Miss
101
7
0111
Hit
111
13
1101
Hit
101
Final contents of the Cache after references:
Index
Contents
000
001
M(25)
001
M(17)
010
M(2)
011
M(19)
100
101
M(21)
101
M(13)
101
M(5)
110
M(6)
111
M(7)
Suppose we have a 16 block cache. Each block of the cache is one word wide. When a given program is executed, the processor reads data from the following sequence of decimal addresses:
2, 5, 7, 2, 13, 21, 17, 19, 6, 25, 2, 17, 21, 7, 13
Show the contents of the cache at the end of the above reading operations if:
the cache is fully associative
Address reference
Binary address
Hit/Miss
Assigned cache block
2
0010
Miss
10
5
0101
Miss
01
7
0111
Miss
11
2
0010
Miss
10
13
1101
Miss
01
21
10101
Miss
01
17
10001
Miss
01
19
10011
Miss
11
6
0110
Miss
10
25
11001
Miss
01
2
0010
Hit
10
17
10001
Hit
01
21
10101
Miss
01
7
0111
Hit
11
13
1101
Hit
01
Final contents of the Cache after references:
Index
Contents
00
01
M(21)
01
M(25)
01
M(17)
01
M(13)
01
M(5)
10
M(6)
10
M(2)
11
M(19)
11
M(7)
Address reference
Binary address
Hit/Miss
Assigned cache block
2
0010
Miss
0010
5
0101
Miss
0101
7
0111
Miss
0111
2
0010
Miss
0010
13
1101
Miss
1101
21
10101
Miss
0101
17
10001
Miss
0001
19
10011
Miss
0011
6
0110
Miss
0110
25
11001
Miss
1001
2
0010
Hit
0010
17
10001
Hit
0001
21
10101
Miss
0101
7
0111
Hit
0111
13
1101
Hit
1101