Computing the hit and miss ratio of a cache organized as either direct mapped or two-way associative
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%