5.9k views

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$ $bi$t 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:

1. $32$ $Kbits$
2. $34$ $Kbits$
3. $64$ $Kbits$
4. $68$ $Kbits$
• 🚩 Edit necessary | | 💬 “Difficult”
edited | 5.9k views
0
Sir why is the cache block size and page size different
+5
:O Why should they be same?
0

so this is a virtually indexed virtually tagged cache @Arjun sir

0
question belongs to  "virtually tagged virtually indexed cache"

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
0

yes sir, I re-read arjun sir' answer and it is correct.If we calculate address of each element and then check for those 11 bits then answer is A[4][0] but sir my main doubt is the procedure I commented above why it fails although I feels all things are correct but conclusion is not true

#set=211=2048

#elements/cache block=16/8=2

#elements/set=4

#array elements which can be in cache simultaneously without conflicting the cache index  :

total set * #elements per set

2048*4=8192=8 rows

so after 8 rows cache will be full and second wrap up will start, so A[8][0] will conflict to cache index with  A[0][0].

0
@reena_kandari

what exactly is yours doubt ??
+1
+1
thank you sir now I got it,  I was taking individual block number as index..thank you so much :)
0
Why are we using virtual memory size here? Tag number bits etc. depend on number of blocks in main memory which in turn depends on physical memory size and size of blocks in memory.  How can we subtract word bits etc. from virtual memory bits. As far as I know, virtual memory size has nothing to do with number of blocks in physical memory and thus won't have anything to do with tag bits in cache memory. Kindly correct me where I am wrong.
0
Why are we using virtual memory size here? Tag number bits etc. depend on number of blocks in main memory which in turn depends on physical memory size and size of blocks in memory.  How can we subtract word bits etc. from virtual memory bits. As far as I know, virtual memory size has nothing to do with number of blocks in physical memory and thus won't have anything to do with tag bits in cache memory. Kindly correct me where I am wrong.

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
Where am I calculating it wrong? I find this approach better than assuming virtual memory size = physical memory size.

If you look at next question belonging to same problem, you can see that main memory address is given as 0xFF000 which is 20 bits. Hence physical memory is addressable with 20 bits not 32 bits.
0
@ Arjun

should we consider read acess too for each elements or only write acess . if read acess is also there then the ans should be different ?
0
Where in the code data is being read?
0
for(i = 0; i < 1024; i++)
for(j = 0; j < 1024; j++)
ARR[i][j] = 0.0; // line 1

Is line 1 is a  read access or write access or both?
Write access is there but I'm having doubt of read access bcz first we are fetching memory location a[i][j]. So should we consider it as a read acess sir ??
0
In question,it is given that cache is managed using 32 bit virtual address.So why you are taking physical address of 32 bit to evaluate tag bit size.

Tag bit = Physical address(MM) bits - set no. - Block offset.

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

1
2