# Computing the hit and miss ratio of a cache organized as either direct mapped or two-way associative

This is an example problem in a computer organization and architecture course that's giving me some trouble. It goes as follows:

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. Now consider a program that accesses memory in the following sequence of addresses:

Once: 63-70

Loop 10 times: 15-32; 80-95

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.

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.

I know that the formula for finding the hit ratio is:

hit ratio = hits / (hits + misses)

and that the LRU replacement scheme should be used for both a and b, since it's the most efficient. I know how to find and compute addresses in a cache, but this has me stumped.

Any help in understanding this is greatly appreciated!

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        ║
╠════════════════╤═════════╣
╟────────────────┼─────────╢
║       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.