For a direct-mapped cache design with a 64-bit address, the following bits of the address are used to access the cache.

Tag	Index	Offset
63–10	9–5	4–0

1 What is the cache block size (in words)?

2 How many blocks does the cache have?

3 What is the ratio between total bits required for such a cache implementation over the data storage bits?

Beginning from power on, the following byte-addressed cache references are recorded.

	Address
Hex	00	04	10	84	E8	A0	400	1E	8C	C1C	B4	884
Dec	0	4	16	132	232	160	1024	30	140	3100	180	2180

4 Foreachreference,list(1)itstag,index,ando set,(2)whether it is a hit or a miss, and (3) which bytes were replaced (if any).

5 What is the hit ratio?
6 List the final state of the cache,with each valid entry represented as a record of <index, tag, data>.

For example, <0, 3, Mem[0xC00]-Mem[0xC1F]>

Answer:

1) We know that the block size can be determined by looking into the offset bits. In this question we have 4 offset bits (0-4), therefore we have 2⁵ or 32 words in a block (basic binary problem).

2) So the next obvious question would be what does then Index bits tell us. Index bits tell us how many blocks are present in a directly mapped cache. In this question we have bit 5-9 in the Index field. So using those 5 bits we can uniquely identify 2⁵ or 32 blocks in a directly mapped cache.

3) So if we consider very simple scenario with no dirty bit of valid bit for each line of the cache, we need 54 bits for tag field, and 32 words of suppose size w each.

Therefore Total bits/Total data bits = (54+32*w)/(32*w).

4) Let us first convert each binary to their 16 bit binary form. To check if it is a miss or a hit, we need to check its index values, so I have highlighted them. Bits left of bold letters are tag bits.

                00           0000 0000 0000 0000        mandatory miss first time referenced
                04           0000 0000 0000 0100        Hit, since the index and tag is same as 0x00
                10           0000 0000 0001 0000        Hit, since the index and tag is same as 0x04
                84           0000 0000 1000 0100        mandatory miss
                E8           0000 0000 1110 1000        mandatory miss again
                A0           0000 0000 1010 0000        mandatory miss again
                400         0000 0100 0000 0000        Miss, same index, different tag as 0x04
                1E           0000 0000 0001 1110        Miss, same index, different tag as 0x400
                8C           0000 0000 1000 1100        Hit!! Same index as 4^th frame
                C1C        0000 1100 0001 1100        Miss, same index, different tag as 0x1E
                B4           0000 0000 1011 0100        Hit!! Same index as 0xA0
                884         0000 1000 1000 0100        Miss since the frame needs replacement

5) hit ratio is as simple as 4/12 or 0.33

6) To fill this table, I would suggest you to draw a cache on your note book and mark which blocks are being replace and are used.

              <4,2, Mem[0x880]-Mem[0x89F]>
                <0,3, Mem[0xC00]-Mem[0xC1F]>
                <5,0, Mem[0xA0]-Mem[0xBF]>
                <7,0, Mem[0xE0]-Mem[0xFF]>