edited by
15,488 views
60 votes
60 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}$.

Which of the following array elements have the same cache index as $\text{ARR[0][0]}$?

  1. $\text{ARR[0][4]}$
  2. $\text{ARR[4][0]}$
  3. $\text{ARR[0][5]}$
  4. $\text{ARR[5][0]}$
edited by

6 Answers

Best answer
62 votes
62 votes
Number of sets $=$ cache size/ size of a set
$= 64 \ \textsf{KB} / (16 \  \textsf{B} \times 2)$ (two blocks per set)
$= 2 \ \textsf{K} = 2^{11}$
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 \times$ Number of cache blocks
 $=17 \times 2^{11} \times 2$ (since each set has $2$ blocks)

$= 68 \ \textsf{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.

$\text{ARR[0][0]}$ is located at virtual address $\textsf{0x  FF000  000. (FF000}$ is page address and $000$ is page offset). So, index bits are $00000000000$

Address of $\text{ARR[0][4]} = \textsf{0xFF000} + 4 \times$ sizeof (double) $= \textsf{0xFF000 000} + 4\times 8 = \textsf{0xFF000  020}  (32 = 20$ in hex) (index bits differ)

Address of $\text{ARR[4][0] } = \textsf{0xFF000 } + 4 \times 1024 \times$ sizeof (double) [since we use row major storage] $= \textsf{0xFF000  000} + 4096\times 8 = \textsf{0xFF000  000 + 0x8000 = 0xFF008  000}$ ( index bits matches that of $\text{ARR [0][0]}$ as both read $000 \ 0000 \ 0000$)

Address of $\text{ARR[0][5]} = \textsf{0xFF000} + 5 \times$ sizeof (double) $= \textsf{0xFF000  000}+ 5\times 8 = \textsf{0xFF000  028} (40 = 28$ in hex) (index bits differ)

Address of $\text{ARR[5][0]} = \textsf{0xFF000} + 5 \times 1024 \times$ sizeof (double) [since we use row major storage] $ = \textsf{0xFF000  000} + 5120\times 8 = \textsf{0xFF000  000 + 0xA000 = 0xFF00A  000}$ (index bits differ)

So, only $\text{ARR[4][0]}$ and $\text{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).$

Correct Answer: $B$
edited by
59 votes
59 votes

[ Need @arjun sir to verify this solution ]
Every element = 8B
Total Size Required By the Array = 1024 *1024 * 8 = 2 23 B
Every Block = 16 B
Number of blocks for Array =$\frac{2 ^{23}}{2^{4} }$ = 2 19
Elements in one block = $\frac{16}{8}$= 2
Number of blocks in cache =$\frac{2 ^{16}}{2^{4} }$ = 2 12
Number of Sets = $\frac{2 ^{12}}{2^{1} }$= 211

$\Rightarrow$ 2 elements in one block




MM block 0 $\varepsilon$  0 mod 211 = set 0
MM block 1 $\varepsilon$  1 mod 211 = set 1
..
..
MM block 2048 $\varepsilon$  2048 mod 211 = set 0  //  sharing same set 

Each Row of array has 1024 elements $\Rightarrow$  512 blocks required

Row 0 :  0-511 blocks
Row1 :  512-1023
..
..
..
Row 'x' : 2048-2559

We need to find 'x'

x= $\frac{2048}{512}$= 4
$\Rightarrow$ A[4][0] shares same set that of A[0][0]

edited by
9 votes
9 votes

virtual address 32 bit

block size 16 B

Each block contain 2 elements

Data cache size 64 KB

Number of blocks=212

but each block contain 2 elements.

So, no. of blocks will be 211

So, for the machine total size  of the blocks $2^{11}\times 2^{4}=2^{15}$

Now , each element size $2^{3}$ B

So, no. of elements could be present in total block=$2^{12}$

So, 1st time array contain 0 to 1024 elements.

     2nd time array can  contain 1 to 1024 elements

     3rd time array can contain 2 to 1024 elements

     4th time array can  contain 3 to 1024 elements

So, now all blocks are full.

No, next time block access it will replace 1st element by Arr[4][0]

edited by
1 votes
1 votes

Where i am going wrong as i am getting the answer as APR[8][0]?

Answer:

Related questions