Problem Set Solutions/Mulitprocessing/Problem10

A simple shared-memory cache-coherent machine has four processors, no virtual-to-physical translation and 16-bit (physical) addresses. There is one L1 data cache per processor and there is no L2 cache. Each L1 cache is direct-mapped with four 64-byte blocks (the size of each cache is 256 bytes), and they are kept coherent using the MESI coherence protocol. The initial state of each cache is as follows (tags are shown in hexadecimal notation):

table.jpg

What happens if the following memory access is executed next. In particular, specify whether the access is a cache hit or a miss, is there a write-back, is there a broadcast on the shared bus as a result of this access, what (if anything) happens in each of the other caches as a result of the bus broadcast, where the data comes from (if not already in the cache), and what the new state of the block is in the requestor’s cache and why. For each part of this problem, start with the state of the cache shown above, not with the state left by prior questions.

P0 reads a word from address 0360

Solution:

Offset is 20, set is 1, tag is 03. The line in P0’s cache in set 1 has a different tag, so this is a cache miss [1 point]. Because the existing line in set 1 is in the M state, a write-back is needed before we can bring the requested block there. After the write-back of block 0140, a request for block 0340 is broadcast on the bus. P2’s cache sees this request, and finds the requested block in its own set 1 in the M state. Therefore, P2’s cache has to respond with the data, downgrade its own copy of the line (state changes from M to S), and assert the Shared signal on the bus. P0’s cache gets the data, puts it in the line in set 1 (setting the tag to 03), and sets its state to S