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.
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.
Which of the following array elements have the same cache index as ARR[0][0]?
- a)ARR[0][4]
- b)ARR[4][0]
- c)ARR[0][5]
- d)ARR[5][0]
Correct answer is option 'B'. 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.
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 KB
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).
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 KB
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 ...
Understanding the problem:
The problem involves analyzing the cache behavior of a program that initializes a 2D array. We need to determine which array elements have the same cache index as ARR[0][0].
Cache organization:
The cache is 2-way set associative with a total size of 64 Kbytes and a block size of 16 bytes. This means that the cache can hold a total of 4096 cache blocks (64 Kbytes / 16 bytes). Each cache block can store 2 memory blocks (2-way set associative).
Virtual addresses and page size:
The machine uses 32-bit virtual addresses, and the page size is 4 Kbytes. This means that each page consists of 1024 memory blocks (4 Kbytes / 16 bytes).
Array ARR:
The array ARR is of size 1024x1024 and contains double precision floating-point numbers (8 bytes each). The array is stored in row-major order.
Cache indexing:
To determine the cache index of a memory block, we divide the virtual address by the block size and then take the remainder when divided by the number of cache blocks.
Solution:
To find the cache index of ARR[0][0], we need to calculate the virtual address of this element and then find its cache index.
1. Virtual address of ARR[0][0]:
- The starting address of ARR is 0xFF000.
- Each double precision floating-point number occupies 8 bytes.
- To find the virtual address of ARR[0][0], we add 0xFF000 to 0 (0*sizeof(double)*1024) and multiply by the size of a double (8 bytes).
- The virtual address of ARR[0][0] is 0xFF000 + 0*8*1024 = 0xFF000.
2. Cache index of ARR[0][0]:
- Divide the virtual address of ARR[0][0] by the block size (16 bytes).
- 0xFF000 / 16 = 0x9FC0.
- Take the remainder when divided by the number of cache blocks (4096).
- 0x9FC0 % 4096 = 0x9FC0.
3. Cache index of other array elements:
- ARR[0][4]: The virtual address is 0xFF000 + 4*8*1024 = 0xFF800.
- Cache index = 0xFF800 / 16 % 4096 = 0x9FE0.
- ARR[4][0]: The virtual address is 0xFF000 + 4*8*1024*1024 = 0x10FF000.
- Cache index = 0x10FF000 / 16 % 4096 = 0x9FC0.
- ARR[0][5]: The virtual address is 0xFF000 + 5*8*1024 = 0xFFA00.
- Cache index = 0xFFA00 / 16 % 4096 = 0x9FF0.
- ARR[5][0]: The virtual address is 0xFF000 + 5*8*1024*1024 = 0x10FF800.
- Cache index =
The problem involves analyzing the cache behavior of a program that initializes a 2D array. We need to determine which array elements have the same cache index as ARR[0][0].
Cache organization:
The cache is 2-way set associative with a total size of 64 Kbytes and a block size of 16 bytes. This means that the cache can hold a total of 4096 cache blocks (64 Kbytes / 16 bytes). Each cache block can store 2 memory blocks (2-way set associative).
Virtual addresses and page size:
The machine uses 32-bit virtual addresses, and the page size is 4 Kbytes. This means that each page consists of 1024 memory blocks (4 Kbytes / 16 bytes).
Array ARR:
The array ARR is of size 1024x1024 and contains double precision floating-point numbers (8 bytes each). The array is stored in row-major order.
Cache indexing:
To determine the cache index of a memory block, we divide the virtual address by the block size and then take the remainder when divided by the number of cache blocks.
Solution:
To find the cache index of ARR[0][0], we need to calculate the virtual address of this element and then find its cache index.
1. Virtual address of ARR[0][0]:
- The starting address of ARR is 0xFF000.
- Each double precision floating-point number occupies 8 bytes.
- To find the virtual address of ARR[0][0], we add 0xFF000 to 0 (0*sizeof(double)*1024) and multiply by the size of a double (8 bytes).
- The virtual address of ARR[0][0] is 0xFF000 + 0*8*1024 = 0xFF000.
2. Cache index of ARR[0][0]:
- Divide the virtual address of ARR[0][0] by the block size (16 bytes).
- 0xFF000 / 16 = 0x9FC0.
- Take the remainder when divided by the number of cache blocks (4096).
- 0x9FC0 % 4096 = 0x9FC0.
3. Cache index of other array elements:
- ARR[0][4]: The virtual address is 0xFF000 + 4*8*1024 = 0xFF800.
- Cache index = 0xFF800 / 16 % 4096 = 0x9FE0.
- ARR[4][0]: The virtual address is 0xFF000 + 4*8*1024*1024 = 0x10FF000.
- Cache index = 0x10FF000 / 16 % 4096 = 0x9FC0.
- ARR[0][5]: The virtual address is 0xFF000 + 5*8*1024 = 0xFFA00.
- Cache index = 0xFFA00 / 16 % 4096 = 0x9FF0.
- ARR[5][0]: The virtual address is 0xFF000 + 5*8*1024*1024 = 0x10FF800.
- Cache index =
Attention Computer Science Engineering (CSE) Students!
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Top Courses for Computer Science Engineering (CSE)View all
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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. 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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. 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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. 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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. Can you explain this answer?.
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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. 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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. 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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. 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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. 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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. 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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. 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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. 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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. 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 inrow major order. The cache is initially empty and no pre-fetching is done. The only data memory references made by theprogram are those to array ARR.Which of the following array elements have the same cache index as ARR[0][0]?a)ARR[0][4]b)ARR[4][0]c)ARR[0][5]d)ARR[5][0]Correct answer is option 'B'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
Follow Us
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup