IAE Academy

GATE 2020 CS Q.30: solution and answer

GATE 2020 · CSQ.30 · 2 marks · MCQ

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.

Which one of the following is TRUE?

  1. (A)

    A1 and A4 are mapped to different cache sets.

  2. (B)

    A2 and A3 are mapped to the same cache set.

  3. (C)

    A3 and A4 are mapped to the same cache set.

  4. (D)

    A1 and A3 are mapped to the same cache set.

See the question in the paper
GATE 2020 CS question 30Tap to open full size

Answer and solution

ANSWER

A2 and A3 map to the same cache set (both set 40); A1 and A4 also map to the same set (set 8, not different). So option B is TRUE.

Official answer: BSource: Official answer key, GATE 2020 CS (IIT Delhi)

  1. Physical address size: main memory = 16 MB = 2^24 B, so addresses are 24 bits wide.

  2. Block offset: block size = 256 B = 2^8 B, so the low 8 bits (bits[7:0]) are the block offset.

  3. Number of sets: cache = 64 KB = 65536 B, so number of blocks = 65536/256 = 256. With 4-way associativity, number of sets = 256/4 = 64 = 2^6, so 6 bits (bits[13:8]) form the set index. The remaining 10 bits (bits[23:14]) are the tag.

  4. Compute the set index for each address as (address >> 8) & 0x3F, equivalent to reading bits[13:8] directly from the binary expansion:

  5. A1 = 0x42C8A4 → binary 0100 0010 1100 1000 1010 0100 → bits[13:8] = 001000 = set 8.

  6. A2 = 0x546888 → binary 0101 0100 0110 1000 1000 1000 → bits[13:8] = 101000 = set 40.

  7. A3 = 0x6A289C → binary 0110 1010 0010 1000 1001 1100 → bits[13:8] = 101000 = set 40.

  8. A4 = 0x5E4880 → binary 0101 1110 0100 1000 1000 0000 → bits[13:8] = 001000 = set 8.

  9. Compare sets: A1 & A4 → both set 8 (same set, so option A, which claims they differ, is false). A2 & A3 → both set 40 (same set) → option B is TRUE. A3 (40) & A4 (8) differ → option C false. A1 (8) & A3 (40) differ → option D false.

  10. Hence the TRUE statement is option B.

KEY IDEA

Split the 24-bit physical address (since main memory ) into Tag | Set Index | Block Offset. Block offset width = . Number of cache sets = (cache size / block size) / associativity, so set-index width = . Two addresses collide in the cache iff their set-index bits are equal, regardless of their tag bits.

WATCH OUT FOR

Miscounting the number of index bits by using (giving 8 bits) instead of dividing by the associativity first to get the number of SETS ( blocks, sets index bits), which shifts every set number and can flip which addresses collide.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 22 Memory & cache questions, with notes

More Memory & cache questions