11,990 views

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}$

Sir why is the cache block size and page size different
:O Why should they be same?

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

question belongs to  "virtually tagged virtually indexed cache"
@Arjun Sir
if cache address is managed using physical address then block(main memory)size  and  line size must be same or it can also varies?

Detailed video solution

Subscribe to GO Classes for GATE CSE 2022

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$ ).

by

but it means between A[0][0] and A[8][0] there must not be any conflicting index right? but answer is A[4][0]...how is it possible?
I am not sure if I understood your question properly. At index 0 or set 0 we have 4 elements a[0][0] , a[0][1], a[4][0],a[4][1] after first round . What conflict are you taking about ?
see, element A[0][0] will be store at set 0 and  after that all elements will be stored  at set1,2,3..until cache is full and  A[7][1023] will be stored at set number 2047.between these elements  no two elements will have the same index number.then how the element A[4][0] will have the same index as A[0][0].(according to my method)

I hope it is clear now.
edited by

we use row major storage ( means we store in row major order ), see  Arjun's answer again ..

ARR[0][0] is located at virtual address 0x FF000 000. (FF000 is page address and 000 is page offset). So, index bits are 000 0000 0000

Address of ARR[4][0] = 0xFF000 + 4 * 1024 * sizeof (double) [since we use row major storage]

= 0xFF000 000 + 4096*8

= 0xFF000 000 + 0x8000

= 0x FF008 000 ( index bits matches that of ARR [0][0] as both read 000 0000 0000)

ARR[0][0] is located at virtual address 0x FF000 000. (FF000 (17 bits) is cache block tag, next 11 bits are index bits and 4 least bits are offset bits)

for two addresses  have the same cache index, means their 11 address bits after the 4 offset bits from right must be same.

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].

@reena_kandari

what exactly is yours doubt ??
thank you sir now I got it,  I was taking individual block number as index..thank you so much :)
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.
edited
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.
@ 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 ?
Where in the code data is being read?
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 ??
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.

can you pleas explain, how do we get this

So, index bits are 000 0000 0000

for the statement:

ARR[0][0] is located at virtual address 0x FF000 000. (FF000 is page address and 000 is page offset).

Index bits represents Set (in case of K-way Set Associative) and Line (in case of Direct Mapping)?

virtual memory address is nothing but main memory address. because virtual memory is basically dividing the main memory into pages .
edited by
@Reena ji,

I calculated the same as you and was confused to see the wrong conclusion. What I understood going through the comments is this method would be right for direct mapped cache. But since this is 2-way set associative, main memory block 2^11mod2^11=0 is colliding with set 0 instead of block 2^12. Please tell me if I got it correctly? So, we have to see which elements are there in 2^11th block which comes out to be row 4. Please reply if this is the reason for wrong calculation.
Here size of cache block is 16 bytes and each element is of size 8 bytes. So each block can have 2 elements of array. Number of WORD bits are 4, so each element access in a block requires 2 bits. Am I right here?

Watch this video,it will clear all your doubts.

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

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 comment

It is already mentioned in question cache is managed using virtual address.

Why are you solving using physical address.