GATE CSE 2020 | Question: 30

Question

A computer system with a word length of $32$ bits has a $16$ MB byte- addressable main memory and a $64$ KB, $4$-way set associative cache memory with a block size of $256$ bytes. Consider the following four physical addresses represented in hexadecimal notation.

• $A1= \textsf{0x42C8A4}$,
• $A2= \textsf{0x546888}$,
• $A3= \textsf{0x6A289C}$,
• $A4=\textsf{0x5E4880}$

Which one of the following is TRUE?

• A. $A1$ and $A4$ are mapped to different cache sets.
• B. $A2$ and $A3$ are mapped to the same cache set.
• C. $A3$ and $A4$ are mapped to the same cache set.
• D. $A1$ and $A3$ are mapped to the same cache set.

Comments

@the_psycho_scientist Bro messed in test just bcoz of this 32 bit given thank bro to clarify it !

---

Because the question states it is a set-associative cache, all blocks are mapped directly to a specific set number.Your main goal in this type of question is to find that set number for each address.

---

32 bit total

tag=18bit, set=6bit,offset=8bit

A1=42C8A4 = 0100 0010 1100 1000 1010 0100   mapped into 8

A2=546888 = 0101 0100 0110 1000 1000 1000   mapped into 40

A3=6A289C= 0110 1010 0010 1000 1001 1101   mapped into 40

A4=5E4880= 0101 1101 0100 1000 1000 0000   mapped into 8

option B is correct

Answer 1

Block size is 256 Bytes. Number of sets in cache = $2^6$ so Set offset bits=6 and word offset bits=8.

So check for set, check for the rightmost 4 digits of each physical address.(Last two byte denote the word address)

A1=C8A4 = C8 = 11001000

A2=6888 = 68 = 01101000

A3=289C = 28 = 00101000

A4=4880 = 48 = 01001000

Now look for lowest order 6 bits in the highlighted part of Each physical address(corresponds to set number).
8 and 8 match and 6=0110 and 2=0010 two low order bits of 6 and 2 match,So A2 and A3 go to same set.

So answer-B

Comments

is cache Word addressable and its offset size is 6 bits?

---

No. It's byte addressable only. Ignore that "word" part.

---

You can also google how to convert hexadecimal to binary.

anyways, here is a good vid on same: https://youtu.be/D_YC6DSPpQE?si=V4Yl3RFOSbJVbKCv

Answer 2

16 MB byte addressable ===> requires 24 bits to represent.

Block size= 256 B ===> 8 bits to represent.

no.of sets = $\frac{64 K}{4*256} = 64 $ ==> 6 bits to represent.

Tag = 24-8-6 = 10 bits.

 

Memory address = tag | set | block

A1 = 0x42C8A4 = (0100 0010 1100 1000 1010 0100)$_2$ ==> set bits = 00 1000

A2 = 0x546888 = (0101 0100 0110 1000 1010 0100)$_2$ ==> set bits = 10 1000

A3 = 0x6A289C = (0110 1010 0010 1000 1010 0100)$_2$ ==> set bits = 10 1000

A4 = 0x5E4880 = (0101 1110 0100 1000 1010 0100)$_2$ ==> set bits = 00 1000

 

A1 and A4 maps to the same set and A2 and A3 maps to same set.

 

Option B is correct

Comments

Perfect!

---

This is the obvious solution..

---

But also A1 and A4 matching why not we also  consider it ?

---

@Ashutosh mandal

There is no such option provided in the question to select.

Answer 3

Approach should be finding number of bits in the set offset.

Set bits = log(CS/BS/k) = log(64K/256/4) = 6

Now see the addresses, the address that matters to us is C8, 68,28,48

First 6 bits from the LSB side are

001000, 101000, 101000, 001000

clearly A2 and A3 are mapped to same cache sets.

Answer 4

Refer this solution very easy explanation