Consider a cache of 4 lines of 16 bytes each. Main memory is divided
into blocks of 16 bytes each. That is, block 0 has bytes with
addresses 0 through 15, and so on.
Number of cache lines = 4
Each cache line = 16 bytes
Main memory block size = 16 bytes
Block 0 holds address 0 to 15,Block 1 holds address 16 to 31,Block 2 holds address 32 to 47, etc as below
╔══════════════════════════╗
║ Main Memory ║
╠════════════════╤═════════╣
║ Memory address │ ║
╟────────────────┼─────────╢
║ 0 │ Block 0 ║
╟────────────────┤ ║
║ 1 │ ║
╟────────────────┤ ║
║ 2 │ ║
╟────────────────┤ ║
║ 3 │ ║
╟────────────────┤ ║
║ 4 │ ║
╟────────────────┤ ║
║ 5 │ ║
╟────────────────┤ ║
║ 6 │ ║
╟────────────────┤ ║
║ 7 │ ║
╟────────────────┤ ║
║ 8 │ ║
╟────────────────┤ ║
║ 9 │ ║
╟────────────────┤ ║
║ 10 │ ║
╟────────────────┤ ║
║ 11 │ ║
╟────────────────┤ ║
║ 12 │ ║
╟────────────────┤ ║
║ 13 │ ║
╟────────────────┤ ║
║ 14 │ ║
╟────────────────┤ ║
║ 15 │ ║
╟────────────────┼─────────╢
║ 16 │ Block 1 ║
╟────────────────┤ ║
║ 17 │ ║
╟────────────────┤ ║
║ 18 │ ║
╟────────────────┤ ║
║ and so on │ ║
╚════════════════╧═════════╝
Now consider a program that accesses memory in the following sequence
of addresses:
Once: 63-70
Loop 10 times: 15-32; 80-95
Here its not correctly specified that-
Case 1 : looped 15-32 ten times and then looped 80-95 ten times
Case 2 : 15-32 and 80-95 are looped one after another ten times
anyway we'll solve both cases.
a. Suppose the cache is organized as direct mapped. Memory blocks 0,
4, and so on are assigned to line 1; blocks 1, 5, and so on to line 2;
and so on. Compute the hit ratio.
Direct mapped Cache :
╔═════════════╤═══════════════════╤═════════════════════════╗
║ Cache lines │ Main memory block │ Addresses in each block ║
╠═════════════╪═══════════════════╪═════════════════════════╣
║ 0 │ Block 0 │ 0-15 ║
╟─────────────┼───────────────────┼─────────────────────────╢
║ 1 │ Block 1 │ 16-31 ║
╟─────────────┼───────────────────┼─────────────────────────╢
║ 2 │ Block 2 │ 32-47 ║
╟─────────────┼───────────────────┼─────────────────────────╢
║ 3 │ Block 3 │ 48-63 ║
╟─────────────┼───────────────────┼─────────────────────────╢
║ 0 │ Block 4 │ 64-79 ║
╟─────────────┼───────────────────┼─────────────────────────╢
║ 1 │ Block 5 │ 80-95 ║
╟─────────────┼───────────────────┼─────────────────────────╢
║ 2 │ Block 6 │ 96-111 ║
╚═════════════╧═══════════════════╧═════════════════════════╝
Accessing memory:
(1) once: 63-70
63 falls in Block 3 - Miss on 63 (Block 3 is bought to cache)
64 falls in Block 4 - Miss on 64 (Block 4 is bought to cache)
╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║ 0 │ Block 4 │ 64-79 ║
╟─────────────┼───────────────────┼─────────╢
║ 1 │ - │ - ║
╟─────────────┼───────────────────┼─────────╢
║ 2 │ - │ - ║
╟─────────────┼───────────────────┼─────────╢
║ 3 │ Block 3 │ 48-63 ║
╚═════════════╧═══════════════════╧═════════╝
therefore, 2 miss and 6 hit.
(2) loop: 15-32,80-95
Case 1:
15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache, replacing Block 4)
16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)
32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache)
╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║ 0 │ Block 0 │ 0-15 ║
╟─────────────┼───────────────────┼─────────╢
║ 1 │ Block 1 │ 16-31 ║
╟─────────────┼───────────────────┼─────────╢
║ 2 │ Block 2 │ 32-47 ║
╟─────────────┼───────────────────┼─────────╢
║ 3 │ Block 3 │ 48-63 ║
╚═════════════╧═══════════════════╧═════════╝
80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1)
╔═════════════╤═══════════════════╤═════════╗
║ Cache lines │ Main memory Block │ Address ║
╠═════════════╪═══════════════════╪═════════╣
║ 0 │ Block 0 │ 0-15 ║
╟─────────────┼───────────────────┼─────────╢
║ 1 │ Block 5 │ 80-95 ║
╟─────────────┼───────────────────┼─────────╢
║ 2 │ Block 2 │ 32-47 ║
╟─────────────┼───────────────────┼─────────╢
║ 3 │ Block 3 │ 48-63 ║
╚═════════════╧═══════════════════╧═════════╝
therefore, 4 miss and 29 hit.
Case 2 : loop: 15-32,80-95
{{ 15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache, replacing Block 4)
16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)
32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache)
80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1) }} x 1 times
{{ 16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache, replacing Block 5)
80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 1) }} x 9 times
therefore, 22 miss and 11 hit.
b. Suppose the cache is organized as two-way set associative, with two
sets of two lines each. Even-numbered blocks are assigned to set 0 and
odd-numbered blocks are assigned to set 1. Compute the hit ratio using
the least recently used replacement scheme.
Two-way set associative mapping:
╔═════════════════════════════╗
║ Cache ║
╠═════════════╤═══════╤═══════╣
║ Cache lines │ Set 1 │ Set 2 ║
╟─────────────┼───────┼───────╢
║ 0 │ - │ - ║
╟─────────────┼───────┼───────╢
║ 1 │ - │ - ║
╚═════════════╧═══════╧═══════╝
Block allocation to cache lines:
╔═════════════╤═══════════════════╗
║ Cache lines │ Main memory Block ║
╠═════════════╪═══════════════════╣
║ 0 │ Block 0,2,4,.. ║
╟─────────────┼───────────────────╢
║ 1 │ Block 1,3,5,.. ║
╚═════════════╧═══════════════════╝
Accessing memory:
(1) once: 63-70
63 falls in Block 3 - Miss on 63 (Block 3 is bought to cache)
64 falls in Block 4 - Miss on 64 (Block 4 is bought to cache)
╔═══════════════════════════════╗
║ Cache ║
╠═════════════╤═════════╤═══════╣
║ Cache lines │ Set 1 │ Set 2 ║
╟─────────────┼─────────┼───────╢
║ 0 │ Block 4 │ - ║
╟─────────────┼─────────┼───────╢
║ 1 │ Block 3 │ - ║
╚═════════════╧═════════╧═══════╝
therefore, 2 miss and 6 hit.
(2) loop: 15-32,80-95
Case 1:
15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache)
16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)
32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache, replacing Block 4)
╔═════════════════════════════════╗
║ Cache ║
╠═════════════╤═════════╤═════════╣
║ Cache lines │ Set 1 │ Set 2 ║
╟─────────────┼─────────┼─────────╢
║ 0 │ Block 2 │ Block 0 ║
╟─────────────┼─────────┼─────────╢
║ 1 │ Block 3 │ Block 1 ║
╚═════════════╧═════════╧═════════╝
80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 3)
╔═════════════════════════════════╗
║ Cache ║
╠═════════════╤═════════╤═════════╣
║ Cache lines │ Set 1 │ Set 2 ║
╟─────────────┼─────────┼─────────╢
║ 0 │ Block 2 │ Block 0 ║
╟─────────────┼─────────┼─────────╢
║ 1 │ Block 5 │ Block 1 ║
╚═════════════╧═════════╧═════════╝
therefore, 4 miss and 29 hit.
Case 2 : loop: 15-32,80-95
15 falls in Block 0 - Miss on 15 (Block 0 is bought to cache)
16 falls in Block 1 - Miss on 16 (Block 1 is bought to cache)
32 falls in Block 2 - Miss on 32 (Block 2 is bought to cache,, replacing Block 2)
80 falls in Block 5 - Miss on 80 (Block 5 is bought to cache, replacing Block 5)
therefore, 4 miss and 29 hit.
Answer:
a.
Case 1: hit ratio = (6+29)/(8+18+15) * 100 = 85.3%
Case 2: hit ratio = (6+11)/(8+18+15) * 100 = 41.1%
b.
Case 1: hit ratio = (6+29)/(8+18+15) * 100 = 85.3%
Case 2: hit ratio = (6+29)/(8+18+15) * 100 = 85.3%
