31 views

Suppose in a system we store data using arrays, we have $2$ arrays A and B.  Array A contains $256$ elements of size $4$ bytes each. The first element is stored at physical address $4096$. Another array B contains $512$ elements of size $4$ bytes each,  stored from physical address location $8192$.

Assume that only arrays A and B can be cached in an initially empty, physically addressed, physically tagged, direct mapped cache whose size is $2$ KB with $8$ byte block size. Now we run below loop in the system:

for( p=0; p<256; p++)
{
A[p] = A[p] + B[2*p]
}

If the cache use write back policy, the number of bytes that will be written to memory during execution of the loop is :

1. $256$
2. $1$
3. $0$
4. $2048$

Doubt:

Cache has 256 blocks, Array A has 128 blocks, Array B has 256 blocks. For the given loop, we are accessing every block of A and B exactly once, now as all blocks of A + B cannot be stored in the cache, exactly 128 blocks of B will need replacement, and hence there will be write-back in memory.

The answer is given as 0 but I think it’s wrong,because if the loop statement was

A[p] = A[p] + B[p]

then the answer would be 0, as then 128 blocks of A and 128 blocks of B would be accessed which would fit exactly in our 256 block cache.

| 31 views
0
0
here cache can store atmost 512 elements(256 block.) and answers is indeed $0$.

Consider last address of array B that can be accessed. It is B[510] in this case which will be mapped to block no. 255 of cache.
0
Array A has 128 blocks and you'll access every block once. Array B has 256 blocks with 2 elements per block.
Say Block 0 has elements B[0] and B[1], block 1 has elements B[2] and B[3] and so on. For p = 0 to 255, we are accessing B[2*p] so array B will be accessed like B[0], B[2], B[4]...and this is showing that every block of B needs to be accessed. Where am I going wrong?
0
hmm. I got your point. In second last paragraph of question you say that array $A$ and array $B$ combined need total of $256+128$ blocks.

That's right. But if you simulate the program then you will find following:

Every block gets accessed first to read element of $B$. (Here no page replacement.)

Then it again gets accessed to read element of $A$. (This operation will rewuire page replacement of coresponding block which contains element of $B$ but it is not modified so we will just bring new element in cache without writing this cache copy back to memory. So no write back in this case.)

And finally that block gets accessed to write modified value of element of $A$. Then this block never gets accessed. (This operation doen't require any write back as we never replace this block.)