edited by
18,500 views
61 votes
61 votes

Consider a machine with a $2$-way set associative data cache of size $64\text{Kbytes}$ and block size $16\text{bytes}$. The cache is managed using $32\;\text{bit}$ virtual addresses and the page size is $4\text{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\text{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 total size of the tags in the cache directory is:

  1. $32\text{Kbits}$
  2. $34\text{Kbits}$
  3. $64\text{Kbits}$
  4. $68\text{Kbits}$
edited by

4 Answers

Best answer
76 votes
76 votes

Number of sets $=\dfrac{\text{cache size}}{\text{size of a set}}$

$=\dfrac{64\ KB}{(16\ B\times 2)}$ (two blocks per set)

$=2\ K=2^{11}$

So, we need $11\text{-bits}$ for set indexing.

Number of WORD bits required $=4$ as a cache block consists of $16\text{ bytes}$ and we need $4\text{-bits}$ to address each of them. 

So, number of tag bits $=32-11-4=17$

Total size of the tag$= 17\times \text{Number of cache blocks}$

$= 17\times 2^{11}\times 2$ (since each set has $2$ blocks)

$=68\text{ Kbits}$

Answer is option D) 68 Kbits

We use the top $17\text{-bits}$ for tag and the next $11\text{-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 $\text{0x FF000 000. (FF000 is page address and 000 is page offset).}$
So, index bits are $00000000000$

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

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

Address of $ARR[5][0] =\text{0xFF000} + 5\times 1024\times \text{ sizeof (double)}$ [since we use row major storage]
$=\text{0xFF000 000}+5120\times 8=\text{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\text{ bytes}$ and our element being double is of size $8\text{ 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$ ). 

edited by
3 votes
3 votes

Number of lines of cache = $\frac{64\times 2^{10}\ Bytes }{16\ Bytes} = 4096$

It is 2 way set associative so the number of sets =4096/2 = 2048

Each block size is 16B 

Tag Bit bits needed to represent No. of sets block offset
32-11-4 = 17 11 4

no. of tag bits = 17

tag directory size = no. of lines * tag bit size = 17 * 4096 = 69632 B i.e., nearly equal to (D) 68KB

1 votes
1 votes
As per me, we have 1024*1024 elements i.e. a total of 2^20 elements in physical memory. Each such element is of 8 bytes. Each element has its own address which means there are 2^20 addressable units in physical memory.

Now, block size is 16 bytes and element size is 8 bytes. Thus there are 2 elements per block and hence number of blocks is 2^20/2=2^19

2^19 blocks and 2^11 sets means each set can map to 2^19/2^11 different block and thus tag number bits are 8

Number of cache lines = 2^12 = 4K
Number of tag bits = 8 bits

Thus, tag size = 4 K * 8 = 32 Kbits
Answer:

Related questions