in CO and Architecture edited by
2,581 views
0 votes
0 votes

Array A contains $256$ elements of $4$ bytes each. Its first element is stored at physical address $4,096.$ Array B contains $512$ elements of $4$ bytes each. Its first element is stored at physical address $8,192.$ Assume that only arrays A and B can be cached in an initially empty, physically addressed, physically tagged, direct-mapped, $2K$-byte cache with an $8$-byte block size. The following loop is then executed.
     

for (i = 0; i < 256; i++)
          A[i] = A[i] + B[2 ∗ i];


During the execution of the loop, how many bytes will be written to memory if the cache has a write-through policy?

$a) 0$

$b) 256$

$c) 1,024$

$d) 2,048$

in CO and Architecture edited by
2.6k views

1 comment

0
0

4 Answers

1 vote
1 vote
The answer is D) 2048 ,  as the cache block is eight bytes long , so whenever an element of A is updated you have to write the entire block which contains the element to memory , as 256 elements are updated there will be that many cache block writes to memory so in all 8*256 = 2048 bytes are written.

4 Comments

why 8*256 i think it should be 4*256 because ecah element is 4byte.
0
0
The cache block can only be written entirely. when cache is updated there is no mechanism to know that half of the cache block is updated hence entire block is written to memory.
0
0
right.
0
0

It will be $4*256$ only. Only $4$ bytes will be written in write-through policy into the MM.

For more clarity check the below question and solution –

https://gateoverflow.in/10668/64-word-cache-and-main-memory-is-divided-into-16-words-block

0
0
1 vote
1 vote
Since the cache line size is 8 bytes, the smallest unit of data transfer into cache from L2 cache or memory is 8 bytes. So if we have a miss for A[0], both A[0] and A[1] get fetched into cache.
2. The cache is addressed by the lower bits of the address. However the address is byte address, and since a cache line can hold 8 bytes, the lower three bits of the address are used to address bytes inside a cache line. Since the cache is 2K bytes large, it has 2K/8 = 256 cache lines, which are addressed by 8 bits. Hence:
bits 0-2 form the “offset”, which is used to address inside a cache line
bits 3 through 10 of the address from the cache line address.
Bits 11-32 form the TAG. (assume a 32 bit architecture)
Now, Consider the sequence: (2 iterations of the loop)
load A[0] → causes A[0] and A[1] at cache line 0
load B[0] → *also addresses cache line 0* - so overwrites A[0] & A[1] above
store A[0] → Nothing happens to cache (no write allocate)  8 bytes are written (8 is the unit of transfer)
load A[1] → Accesses the SAME cache line as A[0] So we load A[0] and A[1] again into line 0
load B[2] → addresses cache line 1 – load B[2] and B[3] into cache line 1
store A[1] → Again nothing happens as above.
So the pattern might be obvious:
At every iteration of the loop, B[2*i] accesses a new cache line, and A overwrites the cache lines every two iterations. Since the loop is 256 iterations, B will just reach cache line 255 when the loop will finish.

Since A has been erasing B half as fast, we would have A in the top half of the cache and B in the bottom half.
Thus the cache contains:
A[0] –A[255] (In the top half) and B[256] – B[511] in the bottom half.

Also, since the cache is write through, the entries in the cache will always be the freshly written entries. Since this is write through, we have to write 256 words = 1024 bytes (all of A) back to the next level (L2 cache or memory)
Assuming that the minimum transfer from a cache to a lower level is a cache line, this translated to 2048 bytes
0 votes
0 votes
I think 256 is the answer. The reason is:

Maximum, there will 1024 bytes written to memory as array A is of 1024 bytes.

Now, A[0] i.e address 4096 and B[2*0] i.e B[0] i.e address 8192 map to the 0th block and hence, this will be a conflict miss and A[0] will not be written. For next 2/3 elements, data is getting written to the main memory. So, the answer is not 0.

So, what remains in between is 256.

Correct me if wrong.

2 Comments

for updating if block is not in the cache then first it will write allocate

then updatation will take place.
0
0
@Pankaj. Look at the answer given by Vikram. He is right. No matter what happens, every time a block is updated. So, 8*256 = 2048 bytes.
0
0
0 votes
0 votes
In write-through policy,

We need to update Memory buffer and Cache simultaneously.

And it is not possible two element in a block at the same time, in a direct-mapped cache.

So, when we are updating an element of array A , the cache blocks are updated simulteneously.

So, ans will be $256 *8=2048B$

Related questions