Assume we have a 4-way set-associative cache with the block size of one word. The following diagram shows all its current tags (with the tilde being used to fix leading 0's), with the red tag in each row being the newest entry for the corresponding set. We assume the FIFO replacement policy, with the newest entry starts from the leftmost position and rotates to the right.

A. Please mark on each of the memory addresses in the following memory reference sequence whether it is a hit (marked X) or a miss (marked O):

10010,01010,01110,11011,10010,11010,01010,11110,11010,11011,

(Some were bolded to make it easier to differentiate them)

Please re-draw the table to show all the tags in the cache immediately after the last memory reference in the sequence given above is completed.

B. Under the same assumptions, suppose the program issues two iterations of the given memory sequence and no other memory references. What is the hit ratio (i.e. the hit rate) of the program at this cache?

Index Tag1 Data Tag2 Data Tag4 Data Tag3 Data ~100 -00 -000 ~110 ~101 -100 -01 ~110 ~000 ~101 ~10 111 ~011 ~100 ~110 11 111 ~110 ~000 ~001