Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  Consider a machine with a 2-way set associati... Start Learning for Free
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 pre-fetching is done. The only data memory references made by the program are those to array ARR.
The total size of the tags in the cache directory is
  • a)
    32 Kbits
  • b)
    34 Kbits
  • c)
    64 Kbits
  • d)
    68 Kbits
Correct answer is option 'C'. Can you explain this answer?
Verified Answer
Consider a machine with a 2-way set associative data cache of size 64 ...
Number of sets = cache size/ size of a set = 64 KB / (16 B * 2) (two blocks per set)
= 2 K = 211
So, we need 11 bits for set indexing.
Number of WORD bits required = 4 as a cache block consists of 16 bytes and we need 4 bits to address each of them.
So, number of tag bits = 32 - 11 - 4 = 17
Total size of the tag = 17 * Number of cache blocks
= 17 * 211 * 2 (since each set has 2 blocks)
= 68 Kbits answer = option D) 68 Kbits
We use the top 17 bits for tag and the next 11 bits for indexing and next 4 for offset. So, for two addresses to have the same cache index, their 11 address bits after the 4 offset bits from right must be same.
ARR[0][0] is located at virtual address 0x FF000 000. (FF000 is page address and 000 is page offset). So, index bits are 00000000000
Address of ARR[0][4] = 0xFF000 + 4 * sizeof (double) = 0xFF000 000 + 4*8 = 0xFF000 020 (32 = 20 in hex) (index bits differ)
Address of ARR[4][0] = 0xFF000 + 4 * 1024 * sizeof (double) [since we use row major storage] = 0xFF000 000 + 4096*8
= 0xFF000 000 + 0x8000 = 0xFF008 000 ( index bits matches that of ARR [0][0] as both read 000 0000 0000)
Address of ARR[0][5] = 0xFF000 + 5 * sizeof (double) = 0xFF000 000+ 5*8 = 0xFF000 028 (40 = 28 in hex) (index bits
differ)
Address of ARR[5][0] = 0xFF000 + 5 * 1024 * sizeof (double) [since we use row major storage] = 0xFF000 000 + 5120*8
= 0xFF000 000 + 0xA000 = 0xFF00A 000 (index bits differ)
So, only ARR[4][0] and ARR[0][0] have the same cache index.
The inner loop is iterating from 0 to 1023, so consecutive memory locations are accessed in sequence. Since cache block
size is only 16 bytes and our element being double is of size 8 bytes, during a memory access only the next element gets
filled in the cache. i.e.; every alternative memory access is a cache miss giving a hit ratio of 50%. (If loops i and j are
reversed, all accesses will be misses and hit ratio will become 0).
This question is part of UPSC exam. View all Computer Science Engineering (CSE) courses
Most Upvoted Answer
Consider a machine with a 2-way set associative data cache of size 64 ...
To calculate the size of the tags in the cache directory, we need to consider the cache size, block size, and the number of sets in the cache.

Given information:
Cache size = 64 Kbytes
Block size = 16 bytes
2-way set associative cache

1. Calculate the number of sets:
The cache is 2-way set associative, which means there are two blocks per set. Therefore, the number of sets can be calculated as follows:
Number of sets = Cache size / (Block size * Number of blocks per set)
Number of sets = 64 Kbytes / (16 bytes * 2)
Number of sets = 2 Ksets

2. Calculate the index size:
The index size is determined by the number of sets. Since the number of sets is 2 Ksets, we need log2(2 Ksets) bits to represent the index.
Index size = log2(Number of sets)
Index size = log2(2 Ksets)
Index size = 11 bits

3. Calculate the tag size:
The tag size is determined by the remaining bits after considering the index size and the block offset. In this case, since the virtual addresses are 32 bits and the page size is 4 Kbytes, the block offset size is log2(Block size) = log2(16 bytes) = 4 bits.
Tag size = Total number of bits - Index size - Block offset size
Tag size = 32 bits - 11 bits - 4 bits
Tag size = 17 bits

4. Calculate the total tag size in the cache directory:
Since the cache is 2-way set associative, each set has two tags. Therefore, the total tag size in the cache directory can be calculated as follows:
Total tag size = Number of sets * Number of tags per set * Tag size
Total tag size = 2 Ksets * 2 tags per set * 17 bits
Total tag size = 68 Kbits

Therefore, the total size of the tags in the cache directory is 64 Kbits (option C).
Explore Courses for Computer Science Engineering (CSE) exam

Similar Computer Science Engineering (CSE) Doubts

Top Courses for Computer Science Engineering (CSE)

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 pre-fetching is done. The only data memory references made by the program are those to array ARR.The total size of the tags in the cache directory isa)32 Kbitsb)34 Kbitsc)64 Kbitsd)68 KbitsCorrect answer is option 'C'. Can you explain this answer?
Question Description
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 pre-fetching is done. The only data memory references made by the program are those to array ARR.The total size of the tags in the cache directory isa)32 Kbitsb)34 Kbitsc)64 Kbitsd)68 KbitsCorrect answer is option 'C'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about 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 pre-fetching is done. The only data memory references made by the program are those to array ARR.The total size of the tags in the cache directory isa)32 Kbitsb)34 Kbitsc)64 Kbitsd)68 KbitsCorrect answer is option 'C'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for 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 pre-fetching is done. The only data memory references made by the program are those to array ARR.The total size of the tags in the cache directory isa)32 Kbitsb)34 Kbitsc)64 Kbitsd)68 KbitsCorrect answer is option 'C'. Can you explain this answer?.
Solutions for 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 pre-fetching is done. The only data memory references made by the program are those to array ARR.The total size of the tags in the cache directory isa)32 Kbitsb)34 Kbitsc)64 Kbitsd)68 KbitsCorrect answer is option 'C'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of 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 pre-fetching is done. The only data memory references made by the program are those to array ARR.The total size of the tags in the cache directory isa)32 Kbitsb)34 Kbitsc)64 Kbitsd)68 KbitsCorrect answer is option 'C'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of 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 pre-fetching is done. The only data memory references made by the program are those to array ARR.The total size of the tags in the cache directory isa)32 Kbitsb)34 Kbitsc)64 Kbitsd)68 KbitsCorrect answer is option 'C'. Can you explain this answer?, a detailed solution for 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 pre-fetching is done. The only data memory references made by the program are those to array ARR.The total size of the tags in the cache directory isa)32 Kbitsb)34 Kbitsc)64 Kbitsd)68 KbitsCorrect answer is option 'C'. Can you explain this answer? has been provided alongside types of 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 pre-fetching is done. The only data memory references made by the program are those to array ARR.The total size of the tags in the cache directory isa)32 Kbitsb)34 Kbitsc)64 Kbitsd)68 KbitsCorrect answer is option 'C'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice 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 pre-fetching is done. The only data memory references made by the program are those to array ARR.The total size of the tags in the cache directory isa)32 Kbitsb)34 Kbitsc)64 Kbitsd)68 KbitsCorrect answer is option 'C'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev