Hardware Reference
In-Depth Information
attempting to write the same word, and some of the request messages may pass
each other in transit and be delivered in a different order than they were issued.
Add to this problem the existence of multiple copies of some blocks of memory
(e.g., in caches), and the result can easily be chaos unless strict measures are taken
to prevent it. In this section we will see what shared memory really means and
look at how memories can reasonably respond under these circumstances.
One view of memory semantics is to see it as a contract between the software
and the memory hardware (Adve and Hill, 1990). If the software agrees to abide
by certain rules, the memory agrees to deliver certain results. The discussion then
centers around what the rules are. These rules are called
consistency models
, and
many different ones have been proposed and implemented (Sorin et al., 2011).
To give an idea of what the problem is, suppose that CPU 0 writes the value 1
to some memory word and a little later CPU 1 writes the value 2 to the same word.
Now CPU 2 reads the word and gets the value 1. Should the computer owner bring
the computer to the repair shop to get it fixed? That depends on what the memory
promised (its contract).
Strict Consistency
The simplest model is
strict consistency
. With this model, any read to a loca-
tion
x
always returns the value of the most recent write to
x
. Programmers love
this model, but it is effectively impossible to implement in any way other than hav-
ing a single memory module that simply services all requests first-come, first-
served, with no caching and no data replication. Such an implementation would
make memory an enormous bottleneck and is thus not a serious candidate, unfor-
tunately.
Sequential Consistency
Next best is a model called
sequential consistency
(Lamport, 1979). The idea
here is that in the presence of multiple read and write requests, some interleaving
of all the requests is chosen by the hardware (nondeterministically), but all CPUs
see the same order.
To see what this means, consider an example. Suppose that CPU 1 writes the
value 100 to word
x
, and 1 nsec later CPU 2 writes the value 200 to word
x
.Now
suppose that 1 nsec after the second write was issued (but not necessarily com-
pleted yet) two other CPUs, 3 and 4, read word
x
twice in rapid succession, as
shown in Fig. 8-24(a). Three possible orderings of the six events (two writes and
four reads) are shown in Fig. 8-24(b)-(d), respectively. In Fig. 8-24(b), CPU 3
gets (200, 200) and CPU 4 gets (200, 200). In Fig. 8-24(c), they get (100, 200) and
(200, 200), respectively. In Fig. 8-24(d), they get (100, 100) and (200, 100), re-
spectively. All of these are legal, as well as some other possibilities that are not
shown. Note that there is not single ''correct'' value.
