Update based protocols tend to occupy much higher bandwidth than invalidate protocols. Example: If P1 and P2 load X, but P2 never uses it. It just sits in its cache and P1 continuously updates it, even though P2 does not require value of X, it will keep getting updated values. Also it is not the case that P1 has the option to get only the latest copy, it will get all the copies whenever an update happens. This adds significant bus traffic.
albusshin
But since the programs have temporal and space locality, the probability of data sitting in the cache and not being used ever again is pretty low, isn't it? In that case, aren't update-based protocols better than invalidation-based?
crow
Even though there is some locality in programs, there is frequently not a lot of it. Consider iterating through an array to compute the sum of elements -- after the first int in a 64 byte block is accessed, the next 15 ints are also loaded into cache, so we have locality there.
However, after those 16 ints are viewed once, they will stay in the cache for possibly a few thousand more loop iterations / processor cycles until they are evicted so most of the time is spent sitting in cache, not being read, and in total, each int is really accessed only once.
apr
So just for my understanding, I want to compare MOESI and Update protocols. In MOESI, when there are multiple caches in S state, if there is one cache that wants to modify, then it goes from S -> M, but the other caches go from S -> I. After that, if any cache wants to read, then the M cache goes from M -> O and the new caches now, get the data from the M cache (instead of M -- flush -> S in the case of MESI.)
On the other hand, in an update protocol, if there are multiple caches in SS state, and one cache wants to modify it, then that cache goes to SM state, and the other caches stay in SC state. Whenever there is an update to the cache in SM state (since that is the one modifying it), the update will be sent to all caches with that line in SC state.
In both protocols, we prevent flushes to memory when there are new reads and in both, all caches with the same line have the same data in them but there may be multiple caches which are not having the same value as main memory whereas in MESI, only one cache can have a value that is different from that in Main memory.
Update is better than MOESI in the case where you have multiple caches having the same line and reading and writing, since then we would avoid the need to invalidate each time (no flushes still needed.) MOESI is better than Update when many caches read the value once, but only one cache accesses it, after which no other cache needs the value. Normally, this should result in eviction of that cache line in the other caches, but if it is not evicted, then there is unnecessary activity on the bus in order to update the other caches with the same line in SC state.
It would be great if someone can confirm this summary!
Update based protocols tend to occupy much higher bandwidth than invalidate protocols. Example: If P1 and P2 load X, but P2 never uses it. It just sits in its cache and P1 continuously updates it, even though P2 does not require value of X, it will keep getting updated values. Also it is not the case that P1 has the option to get only the latest copy, it will get all the copies whenever an update happens. This adds significant bus traffic.
But since the programs have temporal and space locality, the probability of data sitting in the cache and not being used ever again is pretty low, isn't it? In that case, aren't update-based protocols better than invalidation-based?
Even though there is some locality in programs, there is frequently not a lot of it. Consider iterating through an array to compute the sum of elements -- after the first int in a 64 byte block is accessed, the next 15 ints are also loaded into cache, so we have locality there.
However, after those 16 ints are viewed once, they will stay in the cache for possibly a few thousand more loop iterations / processor cycles until they are evicted so most of the time is spent sitting in cache, not being read, and in total, each int is really accessed only once.
So just for my understanding, I want to compare MOESI and Update protocols. In MOESI, when there are multiple caches in S state, if there is one cache that wants to modify, then it goes from S -> M, but the other caches go from S -> I. After that, if any cache wants to read, then the M cache goes from M -> O and the new caches now, get the data from the M cache (instead of M -- flush -> S in the case of MESI.)
On the other hand, in an update protocol, if there are multiple caches in SS state, and one cache wants to modify it, then that cache goes to SM state, and the other caches stay in SC state. Whenever there is an update to the cache in SM state (since that is the one modifying it), the update will be sent to all caches with that line in SC state.
In both protocols, we prevent flushes to memory when there are new reads and in both, all caches with the same line have the same data in them but there may be multiple caches which are not having the same value as main memory whereas in MESI, only one cache can have a value that is different from that in Main memory.
Update is better than MOESI in the case where you have multiple caches having the same line and reading and writing, since then we would avoid the need to invalidate each time (no flushes still needed.) MOESI is better than Update when many caches read the value once, but only one cache accesses it, after which no other cache needs the value. Normally, this should result in eviction of that cache line in the other caches, but if it is not evicted, then there is unnecessary activity on the bus in order to update the other caches with the same line in SC state.
It would be great if someone can confirm this summary!