edited by
8,349 views
32 votes
32 votes

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 $\text{ARR}$ is located in memory starting at the beginning of virtual page $\textsf{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 $\text{ARR}$.

The cache hit ratio for this initialization loop is:

  1. $0\%$
  2. $25\%$
  3. $50\%$
  4. $75\%$
edited by

6 Answers

Best answer
34 votes
34 votes
Block size $=16\textsf{B}$ and one element $=8\textsf{B}.$
So, in one block $2$ element will be stored.

For $1024\times 1024$ element num of block required $=\dfrac{1024\times 1024}{2} =2^{19}$ blocks required.

In one block the first element will be a miss and second one is hit(since we are transferring two unit at a time)

$\Rightarrow \text{hit ratio}=\dfrac{\text{Total hit}}{\text{Total reference}}$

               $=\dfrac{2^{19}}{2^{20}}$

               $=\dfrac{1}{2}=0.5$

               $=0.5\times 100=50\%$

Correct Answer: $C$
edited by
12 votes
12 votes

Given cache block size = 16B, 1 element size in array = 8B (size of Double =8B). Therefore 1Block contain 2 elements

     Total elements = 1024 x1024 =2^20
     each time 1 block ( 2 elements) stored in to  cache, so 1st element is compulsory miss and when we access  2nd element           that will be hit because it is already present in cache.

     Therefore each time 1 miss 1 hit occur, For complete 2^20 elements 2^19 misses and 2^19 Hits will occur
      Hit ratio = 2^19/2^20 = 0.5

                    = 0.5 x 100 = 50%

6 votes
6 votes

CM Size$=64KB$

Block Size$=16B$

No. of lines$=2^{12}$

No. of sets$=2^{11}$

Element size$=8B$

No. of elements/Block$=2$

No. of elements in the Row$=1024$

No. of Blocks/Row$=\frac{1024}{2}=512$

$0$ $a[0][0], a[0][1]$ $a[4][0], a[4][1]$
$1$ $a[0][2], a[0][3]$ $a[4][2], a[4][3]$
 

.

.

 
$511$ $a[0][1022], a[0][1023]$  
$512$ $a[1][0], a[1][1]$ $5^{th} row$
 

.

.

.
$1023$ $a[1][1022], a[1][1023]$ .
 

.

.

.
$2047$ $a[3][1022], a[3][1023]$ .

$a[0][0]=Miss$

$a[0][1]=Hit$

$a[0][2]=Miss$

$a[0][3]=Hit$

Miss follows Hit

The cache hit ratio for this initialization loop is:

$=50\%$

0 votes
0 votes
With each cash block we will bring 2 bytes of data, So first we will have Miss then in next reference we will have it, this follow…

So Hit ratio will be (Hit/ Hit+Miss )*100 = 50%
Answer:

Related questions