Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Just a basic question to ask

Does the write through cache copies the whole block or just the byte which is updated?

I went through the following question

Array A contains 256 elements of 4 bytes each. Its first element is stored at physical address 4096. Array B contains 512 elements of 4 bytes each. Its first element is stored at physical address 8192. 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 the executed

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

How many bytes will be written to memory if the cache has a write-through policy?

I calculated it as follows:

The cache can store the whole array with 2 elements per block (block size = 8bytes, element size = 4bytes). For every write, the whole block will be copied. For $0^{th}$ element, the block containing $0^{th}$ and $1^{st}$ element would be written. The same would be done for $1^{st}$ element as well.

So, for every iteration the 2 elements would be written. This makes the number of bytes as $256*2* (4bytes / element) = 2048bytes$.

But in the solution, they have just calculated the number of loop iterations ($256$) multiplied by the element size ($4byte$) which makes the answer $1024bytes$. If this is true, then the cache would update only the updated byte (not the whole block).

Which is correct?

share|improve this question
1  
This likely depends on the cache implementation, less so on a scientific principle. Therefore, I think the question is offtopic here. –  Raphael Jan 28 '13 at 10:19
    
I think data transfer always occur in blocks. Isn't it? –  Shashwat Jan 28 '13 at 10:25

3 Answers 3

up vote 1 down vote accepted

The caching strategies could be very "domain specific" like efficient data caching for numerical data structure, graph data structures and algorithms, bio-informatics data structure, etc.. This is a nice Ph.D thesis about it: "Cache-efficient Algorithms and Data Structures: Theory and Experimental Evaluation"

For your specific program I think it will cache whole block of memory not only the specific data in array. It uses a general cache strategy. See Cache algorithms on Wikipedia.

share|improve this answer

I would say that write-through cache always knows which addressable units need to be written, so there is absolutely no reason why it should write the rest of the block. Therefore it does not.

I am intentionally saying "addressable units", because (though I am not sure) it would generally be aligned units of the same width as the bus, i.e. usually 4-byte. But that has no effect here when the elements are 4-byte.

In contrast write-back cache is likely to only keep per-block modified status. However a write-back cache would be delaying the writes and since the consecutive passes through the loop end up overwriting whole blocks, it would still write just 1024 bytes.

share|improve this answer
    
You are advocating complicated logic to (a) find out exactly what part of the cache line has changed, (b) address individual bytes in memory, and (c) transfer parts of cache lines to/from memory. The whole point of transferring whole cache lines is to get rid of all this extra complexity. Cache should be fast, complex logic is just out of the question. –  vonbrand May 6 at 12:41
    
@vonbrand: For write through cache it is not complicated, because the command is just passed through as is. And for write back cache I didn't say anything like that. –  Jan Hudec May 6 at 14:08
    
@vonbrand: Of course most caches are write back in practice. But the question did say "write through", so I described write through caches first. –  Jan Hudec May 6 at 14:21

A cache works by transferring a block at a time from/to RAM, so it copies a full block.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.