GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html
Download GATE 2012 CSE Question Paper.
Written by Code Blocks
Sunday, February 12, 2012
GATE 2012 - CS/IT - Answer Key & Solutions
Please refer GATE 2012 CS/IT Official Answer Key for the official answer key published by IIT Madras.
GATE 2012 Answer Key & Solutions for Computer Science and Information Technology.
Download the GATE 2012 CS question paper here.
Key by ACE Engineering Academy
Key by Gate Forum
Key by Engineers Institute of India
GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html
GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html
Information courtesy: IITB Gate 2013 Website.
Wednesday, February 8, 2012
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:
- Memory is word addressible.
- 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 Specification:
- Cache size = 64 KB
- Block size = 16 B
- 2 - way set associative
Number of cache blocks = 64 KB/16 B = 4 K = 212 blocks
Number of words in a cache block = 16 B/1 B = 16 = 24 words
Number of words in a cache block = 16 B/1 B = 16 = 24 words
Number of sets in cache = 2^12 / 2 = 211 sets
Size of virtual address = 32 bits
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 = 212 * 17 = 22 * 210 * 17 = 68 Kbits
72. Answer (B)
Page Size = 4 KB
Number of elements that fit in a page = 4 KB/8 B = 29 elements
Number of elements in any row of the array = 1024 = 210 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.
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(11+4).
The number of array elements that can be stored in this address range = 215/8 = 212 = 22 * 210
=> 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 4th 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
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 = 212 * 17 = 22 * 210 * 17 = 68 Kbits
72. Answer (B)
Page Size = 4 KB
Number of elements that fit in a page = 4 KB/8 B = 29 elements
Number of elements in any row of the array = 1024 = 210 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)
The next address for which the Set Index bits are the same is (2)
The number of addresses/words between these (1)&(2) = 2(11+4).
The number of array elements that can be stored in this address range = 215/8 = 212 = 22 * 210
=> 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 4th 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%.
Subscribe to:
Posts (Atom)