Okay, so we have seen that we want coherence, and
now the question is how do we get it?
So how do we make caches become coherent?
The first option is don't do caching, but this is really bad for performance,
so we will not seriously consider this.
But if there are no caches, then all of the accesses go to memory, and
then writes to that memory will be seen by the reads to that memory.
And also, the order in which the memory receives the writes is the order in
which the writes will be seen by all the cores, so the system will be coherent.
The second option is if all cores share the same level one cache,
then the same argument for coherence applies.
The order of writes is the order seen by this level one cache.
And all of the accesses are going to go to the same cache where they see
the same version of the block.
So the system will be coherent, but
will still have really bad performance, better than this, but not by much.
Now we can try do do things like having private caches,
but make them write through.
In that case, the memory's actually seeing all the writes, but
the problem is that these caches are still allowed
to cache data that has only been read forever.
So once we read the value, it doesn't matter that all the other cores
are writing their values through to memory, because the cache that
only reads will potentially see forever the same failed value even after many,
many writes have occurred, and for a long time.
So this is really not a way to get coherence.
Even with write-through caches, private caches are not necessarily coherent.
What we must do really,
is to force reads made to one cache to see the writes made in another.
So we cannot allow caches to simply provide a same value over and
over once it's a cache hit.
Somehow, once a write occurs in one cache, another cache
needs to eventually start returning that value to its local processor.
So how do we do that?
One way is for every write to be sent to all the other caches
that might potentially have this block, and they need to update their value.
So pretty much I write to my cache.
It's kind of like a write-through cache in that it continues past the cache.
But now what really happens to it is not only does it get rid of backup memory,
it also gets sent and
seen by all the other caches, which now take that new value.
If that happens, then when I write, other caches now have my new value,
and then reads on those scores will actually provide the same value.
This is called write-update coherence,
because writes updates all of the other cache copies.
The other approach for maintaining coherence is for writes to prevent
other copies of the block from having hits.
So after I write one cache, all of the caches that
had a copy of this block need to behave like they're having a miss, or
they need to behave like the block is not valid in that cache.
So this is called write-invalidate.
A write will invalidate all the other copies.
Note that these are just the two general approaches.
We will be looking at several write-invalidated coherence protocols,
and also we will be considering a write-update protocol.
So this ensures, really, that reads see the values produced by writes.
So the coherence property two is maintained by either this or this.
So we need to pick one of these two approaches
to maintain coherence property two.
For coherence property three, we need to decide what's the order of writes and
all the cores need to see the same order.
One way to enforce the same order of writes being seen by all the cores
is that all writes are broadcast on the shared bus, and then the order in which
they appear in this shared bus is the order that should be seen by everybody.
Coherence done in this way is called snooping,
because when writes are broadcast on the bus,
everybody snoops those writes in order to tell what order they occurred on,
and also to update or invalidate their values in the cashes.
Of course, the shared bus can now become a bottleneck.
The other approach is that each block is assigned an ordering point, and
different ordering points can be used for different blocks.
So that for each block, all accesses are ordered by the same entity.
But different blocks use different entities, so they don't have contention.
This ordering point is called Directory when doing coherence.
So this family of approaches is called a Directory Based Coherence.
And this directory both serves as an ordering point for
a block, and also figures out who to update or invalidate.
When multiple caches have a version of the same block, an overwrite occurs.
So among these two approaches, we can also pick one.
And indeed all four possibilities, this and this, this and this, this and
this, and this and that, are all possible.
So you can have write-update with snooping, write-update with directory,
write-invalidate with snooping, write-invalidate with directory.