Problem Set Solutions/Mulitprocessing/Problem05

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):


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 0F00


Offset is 00, set is 0, tag is 0F. The line in set 0 is in I state, so this access is a miss but there is no write-back. The request for this block is broadcast on the bus, and the other caches snoop this broadcast. P1’s cache has this block in the S state, so it asserts the Shared signal on the bus but lets the memory respond. Note that P1 cannot supply the data because it does not know if it is the only one who can do so, unless there is some elaborate scheme for this (to get the point here, the student must either say that the memory responds or describe exactly how P1’s cache figures out it can send the data). Also note that the state of the block in P1’s cache is unchanged (stays in S state). P0’s cache gets the data and sets the state of the cache line in set 0 to S