Cache Coherence Flashcards
What are the states and their bits in MSI protocol?
M: Modified. Valid==1, Dirty==1.
S: Shared. Valid==1, Dirty==0.
I: Invalid. Valid==0, Dirty==anything.
What are the state transitions of I in the MSI protocol?
INVALID (I)
- This is the state of a block that is invalid or not in the cache.
- On local read: Put read request on the bus, get the data, then put block in S state. Data could come from memory OR another cache that has block in M state.
- On local write: Suffer a write miss, put write request on the bus (to get the block and invalidate other cores), and move to M.
- Snoop read on bus: Stay in I.
- Snoop write on bus: Stay in I.
What is “local” about “local read” and “local write”?
“Local” refers to the core. Local read as opposed to snooping another core’s read on the bus.
What are the state transitions of M in the MSI protocol?
MODIFIED (M)
- This is the state of a cache line (or block?) that is valid and dirty.
- On local read: Stay in M. Put nothing on the bus.
- On local write: Stay in M. Put nothing on the bus.
- Snoop read on bus: Write back to memory and move to S.
- Snoop write on bus: write back to memory, move to I, and get data to the writing cache!
Is MSI an invalidation- or update-based protocol?
Invalidation
When a cache line is in state M and snoops a read or write on the bus, it needs to transfer its data to the reading/writing cache. What are the two ways it can get data to the reading/writing cache?
1) Cancel the request, write back, move to invalid, and let the writing cache get data from memory.
2) Suppress the memory response and feed data to the requesting cache.
What are the state transitions of S in the MSI protocol?
SHARED (S)
- This is the state of a cache line (or block?) that is valid and clean.
- On local read: Stay in S. Put nothing on the bus.
- On local write: No write miss and no need to put write request on the bus (because we already have the block)! Instead, we put an invalidation on the bus, then move to M.
- Snoop write on bus: Move to I.
- Snoop read on bus: Stay in S. This is what S is for!
What does it mean that the dirty bit is 1 in the M state?
It means that we always need to write back to memory before leaving M.
What are the four actions that lead to state transitions in the MSI protocol?
- Local read: The local core, from the perspective of a cache line, wants to read from said cache line.
- Local write: The local core, from the perspective of a cache line, wants to write to said cache line.
- Snoop read: The local core snoops a read request for the block in said cache line.
- Snoop write: The local core snoops a write request for the block in said cache line.
What is the purpose of the O (Owned) state?
Avoiding memory writes on cache to cache transfers. Imagine two caches alternating reads and writes on the same block. Every time ownsership changes hands, we get a memory write. Not good!
What is the O (Owned) state responsible for?
- Giving data to other caches
- Eventually writing block to memory
How is the MOSI protocol different from the MSI protocol?
1) When M state snoops a read, it transitions to O state, not S. Memory is NOT accessed.
2) O state is like S state except that
- When it snoops a read, it provides the data.
- When O block is replaced, we write back to memory.
What are the access and clean/dirty properties of MOSI protocol?
M: Exclusive read/write access, dirty
S: Shared read access, clean
O: Shared read access, dirty
I: No read/write access, clean/dirty irrelevant
What is the key inefficiency of the MSI protocol?
Unnecessary memory accesses. We might already have a block in M state, and we’d like to send it to another cache, but we have to write back to memory before moving it.
What is the key inefficiency of the MOSI protocol? (this is shared with MSI)
Thread-private data accessed by only a single thread.
When we read then write the same block, the block will go from I state -> read miss -> S state -> send inval -> M state.
Putting the invalidation request on the bus is SLOW. Not as slow as requesting the data or going to memory, but it still requires that we wait for the invalidation process to finish.
