MIPS R4000 Microprocessor User's Manual 267
Cache Organization, Operation, and Coherency
Strong Ordering
Cache-coherent multiprocessor systems must obey ordering constraints
on stores to shared data. A multiprocessor system that exhibits the same
behavior as a uniprocessor system in a multiprogramming environment is
said to be strongly ordered.
An Example of Strong Ordering
Given that locations X and Y have no particular relationship—that is,
they are not in the same cache line—an example of strong ordering is as
follows:
1. At time T, Processor A performs a store to location X and at the same
time processor B performs a store to location Y.
2. At time T+1, Processor A does a load from location Y and at the same
time processor B does a load from location X.
For the system to be considered strongly ordered, either processor A must
load the new value of Y, or processor B must load the new value of X, or
both processors A and B must load the new values of Y and X, respectively,
under all conditions.
If processors A and B load old values of Y and X, respectively, under any
conditions, the system is not strongly ordered.
Testing for Strong Ordering
Table 11-5 shows the algorithm for testing strong ordering.
Table 11-5 Algorithm for Testing Strong Ordering
For this algorithm to succeed, stores must have a global ordering in time;
that is, every processor in the system must agree that either the store to
location X precedes the store to location Y, or vice versa. If this global
ordering is enforced, the test algorithm for strong ordering succeeds.
Time Processor A Processor B
T Store to location X Store to location Y
T+1 Load from location Y Load from location X
To Next Page
Loading...