GATE CS 2008 Questions 71-73 Solution

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Consider a machine with a 2-way set associative data cache of size 64 Kbytes and block size 16 bytes. The cache is managed using 32 bit virtual addresses and the page size is 4 Kbytes. A program to be run on this machine begins as follows:

double ARR [1024] [1024] ;

int i, j ;

/* Initialize array ARR to 0.0 * /

for (i= 0;i< 1024; i++)

  for (j= 0; j< 1024; j++)

    ARR[i] [j ]=0.0;

The size of double is 8 Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no prefetching is done. The only data memory references made by the program are those to array ARR.

71. The total size of the tags in the cache directory is

(A) 32 Kbits (B) 34 Kbits (C) 64 Kbits (D) 68 Kbits

72. Which of the following array elements has the same cache index as ARR [0] [0]?

(A) ARR [0] [4] (B) ARR [4] [0] (C) ARR [0] [5] (D) ARR [5] [0]

73. The cache hit ratio for this initialization loop is

(A) 0% (B) 25% (C) 50% (D) 75%

Solutions:

Assumptions:

1. Memory is word addressible.
2. Since no information is given on the number of bytes constituting a word, we take 1 word = 1 Byte

71.  Answer: (D)


Cache Specification:

• Cache size = 64 KB
• Block size = 16 B
• 2 - way set associative

Number of cache blocks = 64 KB/16 B = 4 K = 2¹² blocks
Number of words in a cache block = 16 B/1 B = 16 = 2⁴ words

Number of sets in cache = 2^12 / 2 = 2¹¹ sets
Size of virtual address = 32 bits

Figure 1: Divisions of the address for cache use.

Blocks offset = 4 bits
Set index = 11 bits
=> Number of TAG bits = 32 - ( 11 + 4 ) = 17 bits

Size of TAGs in the cache directory = #cache blocks x #TAG bits = 2¹² * 17 = 2² * 2¹⁰ * 17 = 68 Kbits

---

72. Answer (B)


Page Size = 4 KB
Number of elements that fit in a page = 4 KB/8 B = 2⁹ elements
Number of elements in any row of the array = 1024 = 2¹⁰ elements
Number of words in an array element = 8 B/1 B = 8 words.

Two main memory addresses will be mapped to the same cache set if they have the same bit pattern for the Set Index bits.

The address where array element ARR[0][0] is stored is 0xFF000 or 0x000FF000 since the address is a 32bit address[8*4]. The bits 4 - 14 in the address correspond to the Set Index from the calculation in Q 71.

0x000FF000 = 00000000000011111111000000000000 - (1)

0x00107000 = 00000000000100000111000000000000 - (2)

Addresses 0x000FF000 - 0x000FF00F have the same Set Index bits. There are sixteen addresses in this range each corresponding to one word. Since each array element takes up 8 words, this address range can store only two elements, ARR[0][0] & ARR[0][1]. So these two elements map to one of the 2 ways [each way is one cache block = 16 B] of some set k in the cache.

The next address for which the Set Index bits are the same is (2)
The number of addresses/words between these (1)&(2) = 2⁽¹¹⁺⁴⁾.
The number of array elements that can be stored in this address range = 2¹⁵/8 = 2¹² = 2² * 2¹⁰
=> 4 rows can be stored in this address range. So the last address, 0x00107000, will store ARR[4][0].
So the first element of every 4^th row will map to the same cache set.

---

73. Answer (C)

Number of elements in the array ARR = 1024 * 1024
Size of an element of type double = 8 B
=> Number of elements that fit in a cache block = 16 B/8 B = 2 doubles or two array elements

The sequence of accesses generated by the for loop is

ARR[0][0], ARR[0][1], ARR[0][2], ... , ARR[0][1024], ARR[1][0], ARR[1][1], ARR[1][2], ... , ARR[1][1024], ... , ARR[1024][0], ARR[1024][1], ARR[1024][2], ... , ARR[1024][1024]

Initially, cache doesn't contain any array elements. The access for ARR[0][0] creates a cache miss which loads a block of data from main memory. Since two array elements can be accommodated in a cache block, ARR[0][1] is also brought into the cache. So the access for ARR[0][1] results in a cache hit. Again ARR[0][2] will be a cache miss which results in ARR[0][3] being a hit and so on.

Once the cache becomes full, existing cache blocks get replaced by the new blocks being brought into the cache, again with the same hit/miss pattern.

The cache access for half of the array elements will result in a miss and the other half will be a hit. So the cache hit ratio for the given initialization loop is 50%.

Written by Code Blocks