Given Physical address (Main memory address) is 36 bits
Physical address space (Main memory size) = $2^{36}$ Bytes
The Block Size is given as 128 Bytes = $2^{7}$ Bytes
The Total no of blocks in Main memory = $\frac{ 2^{36}B }{2^{7}B}$ = $2^{29}$ Blocks
Cache size is given to be 64 KB so the no of lines (Blocks) in Cache = $\frac{ 64KB }{2^{7}B}$ = $\frac{ 2^{16}B }{2^{7}B}$
= $2^{9}$ Lines
The minimum tag bit size can be achieved when the cache uses Direct Mapping..
The maximum tag bit size can be achieved when the cache uses Fully Associative Mapping..
From the above example we can clearly visualize that the tag bits size gets reduced when we use
Direct mapping as we map each block of main memory to a particular Cache line using Line bits
whereas in Fully associative...any block can be mapped to any Cache line as there are no Line bits…
Here in this question….
The Tag bits size in Fully associative = Main memory address bits – Block offset
= 36 – 7
= 29 bits
The Tag bits size in Direct Mapping = Main memory address bits – (Line bits + Block offset)
= 36 – (9 + 7)
= 20 bits
The Difference in the size = 29 – 20 = 9 bits
