Thread-Level Parallelism - Computer Architecture: A Quantitative Approach - page 352

FIGURE 5.3 The cache coherence problem for a single memory location (X), read and
written by two processors (A and B) . We initially assume that neither cache contains the
variable and that X has the value 1. We also assume a write-through cache; a write-back
cache adds some additional but similar complications. After the value of X has been written by
A, A's cache and the memory both contain the new value, but B's cache does not, and if B
reads the value of X it will receive 1!
Informally, we could say that a memory system is coherent if any read of a data item returns
the most recently writen value of that data item. This deinition, although intuitively appeal-
ing, is vague and simplistic; the reality is much more complex. This simple definition contains
two different aspects of memory system behavior, both of which are critical to writing cor-
rect shared-memory programs. The first aspect, called coherence , defines what values can be
returned by a read. The second aspect, called consistency , determines when a written value will
be returned by a read. Let's look at coherence first
A memory system is coherent if
1. A read by processor P to location X that follows a write by P to X, with no writes of X by
another processor occurring between the write and the read by P, always returns the value
written by P.
2. A read by a processor to location X that follows a write by another processor to X returns
the writen value if the read and write are suiciently separated in time and no other writes
to X occur between the two accesses.
3. Writes to the same location are serialized ; that is, two writes to the same location by any two
processors are seen in the same order by all processors. For example, if the values 1 and
then 2 are writen to a location, processors can never read the value of the location as 2 and
then later read it as 1.
The first property simply preserves program order—we expect this property to be true even
in uniprocessors. The second property defines the notion of what it means to have a coherent
view of memory: If a processor could continuously read an old data value, we would clearly
say that memory was incoherent.
The need for write serialization is more subtle, but equally important. Suppose we did not
serialize writes, and processor P1 writes location X followed by P2 writing location X. Serial-
izing the writes ensures that every processor will see the write done by P2 at some point. If
we did not serialize the writes, it might be the case that some processors could see the write
of P2 irst and then see the write of P1, maintaining the value writen by P1 indeinitely. The
simplest way to avoid such difficulties is to ensure that all writes to the same location are seen
in the same order; this property is called write serialization .