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

5.6 Models of Memory Consistency: An Introduction
Cache coherence ensures that multiple processors see a consistent view of memory. It does
not answer the question of how consistent the view of memory must be. By “how consistent”
we are really asking when must a processor see a value that has been updated by another
processor? Since processors communicate through shared variables (used both for data values
and for synchronization), the question boils down to this: In what order must a processor ob-
serve the data writes of another processor? Since the only way to “observe the writes of anoth-
er processor” is through reads, the question becomes what properties must be enforced among
reads and writes to different locations by different processors?
Although the question of how consistent memory must be seems simple, it is remarkably
complicated, as we can see with a simple example. Here are two code segments from processes
P1 and P2 , shown side by side:
P1: A = 0; P2: B = 0;
..... .....
A = 1; B = 1;
L1: if (B == 0)… L2: if (A == 0)…
Assume that the processes are running on different processors, and that locations A and B are
originally cached by both processors with the initial value of 0. If writes always take immedi-
ate effect and are immediately seen by other processors, it will be impossible for both if state-
ments (labeled L1 and L2 ) to evaluate their conditions as true, since reaching the if statement
means that either A or B must have been assigned the value 1. But suppose the write invalidate
is delayed, and the processor is allowed to continue during this delay. Then, it is possible that
both P1 and P2 have not seen the invalidations for B and A (respectively) before they attempt to
read the values. The question now is should this behavior be allowed, and, if so, under what
conditions?
The most straightforward model for memory consistency is called sequential consistency .
Sequential consistency requires that the result of any execution be the same as if the memory
accesses executed by each processor were kept in order and the accesses among different pro-
cessors were arbitrarily interleaved. Sequential consistency eliminates the possibility of some
nonobvious execution in the previous example because the assignments must be completed
before the if statements are initiated.
The simplest way to implement sequen-tial consistency is to require a processor to delay the
completion of any memory access until all the invalidations caused by that access are com-
pleted. Of course, it is equally effective to delay the next memory access until the previous one
is completed. Remember that memory consistency involves operations among different vari-
ables: The two accesses that must be ordered are actually to different memory locations. In our
example, we must delay the read of A or B ( A == 0 or B == 0 ) until the previous write has com-
pleted ( B = 1 or A = 1 ). Under sequential consistency, we cannot, for example, simply place the
write in a write buffer and continue with the read.
Although sequential consistency presents a simple programming paradigm, it reduces po-
tential perfor-mance, especially in a multiprocessor with a large number of processors or long
inter-connect delays, as we can see in the following example.
Example