I'm not sure I understand how these extra lines work. Can someone please explain? How does a 0 value indicate everyone has responded? Presumably some of the processors will respond with a 1 value if the data is shared, dirty, etc.?
rbcarlso
I could be totally off base here, but as I recall the way the bus connects the caches in the system is typically in a ring fashion, so maybe if you initiate something on the bus, when it gets back to you you know everyone else has touched it?
I'm really not sure about this, so if someone could confirm or correct this it'd be appreciated.
afa4
@sgbowen: At the start, all the processors assert the snoop-valid line. Every processor then reports its snoop result (i.e., asserts shared or dirty line if it has the line in shared or dirty state respectively) and then de-asserts the snoop-valid line. When all the processors are done the snoop-valid line should have the value 0.
ekr
@sgbowen I believe the Snoop-valid line is just a bit to indicate if every processor on the bus has had a chance to respond to the Bus request. That is, if the second response line is 0, indicating the data is clean, but the last line is a 1, this means that not all of the processors have been able to respond to the snoop (due to cache access restrictions), so the bit indicating that the data is clean may not actually be correct.
Presumably the default value is a 1 for each processor, and as each processor responds, it sets its corresponding Snoop-valid bit to a 0.
HLAHat
These are all OR lines, so the only way to change the state of the Snoop-Valid line is to have all processors de-assert that line. If the line is high, then that means at least one processor has not responded, and has not de-asserted the line. afa4 and ekr are both correct here.
TypicalChazz
So let me try to make sense of this. Assuming that the snoop-valid line is 0 (all processors have responded):
Shared = 0, Dirty = 0: Get the line from memory, no one has it.
Shared = 0, Dirty = 1: Invalid state (It's saying no one else has the line, but the line is still dirty, which doesn't make sense)
Shared = 1, Dirty = 0: Someone else has the line in a shared state, we can get it from that cache.
Shared = 1, Dirty = 1: Someone else has the line in a dirty state (holds exclusive access), get it from that cache.
Is my understanding correct? I'm under the assumption that each processor puts a 1 on the shared line if it holds that line in a valid state (be it a exclusive or shared state).
amaliujia
@TypicalChazz Can shared line and Dirty line be 1 at the same time? From my point of view, shared line be 1 is cache in shared state while Dirty line be 1 is cache with modified state. In MESI, each cache line should only has one state.
Kapteyn
@amaliujia, you're right according to the wiki page: http://en.wikipedia.org/wiki/MESI_protocol
the shared line and the dirty line will never be 1 at the same time. Modified means only one cache has the line.
aznshodan
@ekr You said snoop-valid line is just a bit to indicate if every processor on the bus has had a chance to respond to the "Bus request."
What is this bus request? Are these requests coming from a
processor when there's a cache miss and it has to send out the address to read from memory or from other caches?
memory when it needs invalidate other caches?
I'm still not sure what snoop-valid bit is indicating.
Kapteyn
@aznshodan: the bus requests are referring to all memory requests made by processors such as BusRdx, BusRd, BusUpgrade. As per the snooping cache coherence protocol, all processors need to "snoop" all memory requests made by other processors and respond appropriately.
Say P1 sends a BusRd for line A. It needs to wait for all other processors to tell it whether or not they have the line in the shared state (using the shared line) or whether or not they have it in the dirty state (using the dirty line). It cannot take the appropriate action if it has not received a response from all processors.
For example, what if all but one of the processors responded to P1's BusRd and said they have it in the shared state. Say P1 did not wait to hear what the last processor's snoop response was and that this last processor happened to have it in the dirty state? P1 and the memory manager would both think that P1 can just get the line from memory and it would be up to date when in fact it is stale. That is why we need the snoop valid line to know for sure that all processors have responded with their snoop results.
This slide presents a possible implementation of the snoop line, where the line is a logical OR of a bit from each processor. All processor bits for this line are initially set to 1. Once a processor responds with its snoop result, it sets its bit to 0. Thus, if the line has value 1, it means that not all of the processors have responded yet (because it's an OR). Once the line has value 0 it means that all processors have responded.
yuel1
@Kapteyn regarding your third paragraph, if one of the caches has the line in the dirty state, wouldn't that imply that all the other shared lines would actually be invalid?
Kapteyn
Ah you're right! That should read "what if all but one of the processors responded to P1's BusRd and said they do not have the line in their cache (i.e. it's invalid)"
P1 doesn't wait to hear the remaining processor's response which would tell P1 that it has the line in the dirty state.
Zarathustra
What I got from reading all this:
When the bus transaction starts, the "snoop-valid" bit is 1 for all processors. As they check their respective caches and report on the condition of the requested line (dirty, shared), they put that result on the bus and change the "snoop-valid" bit to 0, indicating they are done.
When the "snoop-valid" bit is 0 for all processors (the OR of all the processor's "snoop-valid" bits is 0), then all of the processors have checked in: the snoop is complete for the entire system.
Technical jargon: If a cache "asserts a line", we just mean that the snoop-valid bit is 1 for that cache for the current snoop (it's not done). When the cache "de-asserts" the line, the snoop-valid bit for that cache is 0 (it is done).
toutou
I don't know whether I make a mistake here. What I understand is the snoop-valid line is a indicator of whether all processors have response to a request in bus. If it is 1, it means there is at least one processor has not response yet. And until the bit turns to 0 that it begins to check the shared and dirty line. If there is another request in Bus, the snoop-valid turns to 1 and waits for response in next turn.
I'm not sure I understand how these extra lines work. Can someone please explain? How does a 0 value indicate everyone has responded? Presumably some of the processors will respond with a 1 value if the data is shared, dirty, etc.?
I could be totally off base here, but as I recall the way the bus connects the caches in the system is typically in a ring fashion, so maybe if you initiate something on the bus, when it gets back to you you know everyone else has touched it?
I'm really not sure about this, so if someone could confirm or correct this it'd be appreciated.
@sgbowen: At the start, all the processors assert the snoop-valid line. Every processor then reports its snoop result (i.e., asserts shared or dirty line if it has the line in shared or dirty state respectively) and then de-asserts the snoop-valid line. When all the processors are done the snoop-valid line should have the value 0.
@sgbowen I believe the Snoop-valid line is just a bit to indicate if every processor on the bus has had a chance to respond to the Bus request. That is, if the second response line is 0, indicating the data is clean, but the last line is a 1, this means that not all of the processors have been able to respond to the snoop (due to cache access restrictions), so the bit indicating that the data is clean may not actually be correct.
Presumably the default value is a 1 for each processor, and as each processor responds, it sets its corresponding Snoop-valid bit to a 0.
These are all OR lines, so the only way to change the state of the Snoop-Valid line is to have all processors de-assert that line. If the line is high, then that means at least one processor has not responded, and has not de-asserted the line. afa4 and ekr are both correct here.
So let me try to make sense of this. Assuming that the snoop-valid line is 0 (all processors have responded):
Shared = 0, Dirty = 0: Get the line from memory, no one has it.
Shared = 0, Dirty = 1: Invalid state (It's saying no one else has the line, but the line is still dirty, which doesn't make sense)
Shared = 1, Dirty = 0: Someone else has the line in a shared state, we can get it from that cache.
Shared = 1, Dirty = 1: Someone else has the line in a dirty state (holds exclusive access), get it from that cache.
Is my understanding correct? I'm under the assumption that each processor puts a 1 on the shared line if it holds that line in a valid state (be it a exclusive or shared state).
@TypicalChazz Can shared line and Dirty line be 1 at the same time? From my point of view, shared line be 1 is cache in shared state while Dirty line be 1 is cache with modified state. In MESI, each cache line should only has one state.
@amaliujia, you're right according to the wiki page: http://en.wikipedia.org/wiki/MESI_protocol the shared line and the dirty line will never be 1 at the same time. Modified means only one cache has the line.
@ekr You said snoop-valid line is just a bit to indicate if every processor on the bus has had a chance to respond to the "Bus request."
What is this bus request? Are these requests coming from a
processor when there's a cache miss and it has to send out the address to read from memory or from other caches?
memory when it needs invalidate other caches?
I'm still not sure what snoop-valid bit is indicating.
@aznshodan: the bus requests are referring to all memory requests made by processors such as BusRdx, BusRd, BusUpgrade. As per the snooping cache coherence protocol, all processors need to "snoop" all memory requests made by other processors and respond appropriately.
Say P1 sends a BusRd for line A. It needs to wait for all other processors to tell it whether or not they have the line in the shared state (using the shared line) or whether or not they have it in the dirty state (using the dirty line). It cannot take the appropriate action if it has not received a response from all processors.
For example, what if all but one of the processors responded to P1's BusRd and said they have it in the shared state. Say P1 did not wait to hear what the last processor's snoop response was and that this last processor happened to have it in the dirty state? P1 and the memory manager would both think that P1 can just get the line from memory and it would be up to date when in fact it is stale. That is why we need the snoop valid line to know for sure that all processors have responded with their snoop results.
This slide presents a possible implementation of the snoop line, where the line is a logical OR of a bit from each processor. All processor bits for this line are initially set to 1. Once a processor responds with its snoop result, it sets its bit to 0. Thus, if the line has value 1, it means that not all of the processors have responded yet (because it's an OR). Once the line has value 0 it means that all processors have responded.
@Kapteyn regarding your third paragraph, if one of the caches has the line in the dirty state, wouldn't that imply that all the other shared lines would actually be invalid?
Ah you're right! That should read "what if all but one of the processors responded to P1's BusRd and said they do not have the line in their cache (i.e. it's invalid)"
P1 doesn't wait to hear the remaining processor's response which would tell P1 that it has the line in the dirty state.
What I got from reading all this:
When the bus transaction starts, the "snoop-valid" bit is 1 for all processors. As they check their respective caches and report on the condition of the requested line (dirty, shared), they put that result on the bus and change the "snoop-valid" bit to 0, indicating they are done.
When the "snoop-valid" bit is 0 for all processors (the OR of all the processor's "snoop-valid" bits is 0), then all of the processors have checked in: the snoop is complete for the entire system.
Technical jargon: If a cache "asserts a line", we just mean that the snoop-valid bit is 1 for that cache for the current snoop (it's not done). When the cache "de-asserts" the line, the snoop-valid bit for that cache is 0 (it is done).
I don't know whether I make a mistake here. What I understand is the snoop-valid line is a indicator of whether all processors have response to a request in bus. If it is 1, it means there is at least one processor has not response yet. And until the bit turns to 0 that it begins to check the shared and dirty line. If there is another request in Bus, the snoop-valid turns to 1 and waits for response in next turn.