GATE CSE 2001 | Question: 9

Question

A CPU has $32-bit$ memory address and a $256 \ KB$ cache memory. The cache is organized as a $4-way$ set associative cache with cache block size of $16$ bytes.

• A. What is the number of sets in the cache?
• B. What is the size (in bits) of the tag field per cache block?
• C. What is the number and size of comparators required for tag matching?
• D. How many address bits are required to find the byte offset within a cache block?
• E. What is the total amount of extra memory (in bytes) required for the tag bits?

Comments

I think it is

---

for part C,  2^14 lines , each line has tag bits which is 16bits(2Bytes) So total amount of extra memory (in bytes) required for the tag bits is 2^14* 2 Byte = 2^15Bytes...

---

offset bit  = 4

no.of bit in set = 12

no. of bit in tag = 16

Extra memory required to store the tag bits =16*2^12*4  = 2^18 bit =  2^15 bytes

 

Answer 1

What is the number of sets in the cache

 $\text{Number of sets}=\dfrac{\text{Cache memory}}{\text{(set associativity $\times$ cache block size)}}$

 $=\dfrac{256KB}{(4\times 16 B)}$

 $=4096$

What is the size (in bits) of the tag field per cache block?

 Memory address size $=32\text{-bit}$

 Number of bits required to identify a particular set  $=12\text{ (Number of sets}= 4096)$

 Number of bits required to identify a paticular location in cache line $=4\text{ (cache block size = 16)}$

 Size of tag field $=32-12-4=16\text{-bit}$

What is the number and size of comparators required for tag matching?

We use $4\text{-way}$ set associate cache. So, we need $4$ comparators each of size $16\text{-bits}$

http://ecee.colorado.edu/~ecen2120/Manual/caches/cache.html

How many address bits are required to find the byte offset within a cache block?

Cache block size is $16\text{-byte.}$ so $4\text{-bits}$ are required to find the byte offset within a cache block.

What is the total amount of extra memory (in bytes) required for the tag bits?

size of tag $=16\text{-bits}$

Number of sets $=4096$

Set associativity $=4$

Extra memory required to store the tag bits $=16\times 4096\times 4\text{-bits}= 2^{18}\text{ bits}=2^{15}\text{ bytes}.$

Comments

understand it in this way , number of comparators required will be same as the number of comparisons to be made . One block can go to anyone of the sets , therefore to check whether the block is already present in the set or not ( basically hit or miss ) we will compare it will every block of the set . 

That is we will make comparisons which is  = the number of blocks in set = associativity of the set 

Thus , number of comparators used = associativity

hence in this case 4 comparator will be used .

---

No. of comparators = 4

size of Comparatos = 16 bits

---

for 2-way set associative:

https://www.gatevidyalay.com/set-associative-mapping-cache-mapping/

Answer 2

A. To find the number of sets we need to determine the number of rows. To do that we need to determine the number of blocks. We are given that this is a 4-way set associative cache, hence each set has four blocks.

It holds:

#Blocks = Capacity / BlockSize = 2¹⁸ / 2⁴ = 2¹⁴. There are 2¹⁴ blocks.

#Sets = #Blocks / #ways = 2¹⁴ / 2² = 2^12. There are 2¹² sets.

Comments

256 KB, not 256 B :)

---

Thanks for pointing out. I've corrected it.

Answer 3

Ans