Reasoning About Parallel
by William W. Collier
Application of the Ideas in RAPA
What does it mean to say that a shared memory multiprocessor
(SMMP) is cache coherent?
Suppose that there are two machines, identical in all respects,
except that one is cache coherent and the other is not. Clearly there
will exist some difference between the hardware in the two machines.
Will the difference extend to the software running on the two
If the difference is visible to software, then there must be at
least one program which can calculate an answer on the non-cache
coherent machine which it demonstrably cannot calculate on the cache
RAPA describes programs which can detect the failure of a machine
to be cache coherent, sequentially consistent, strongly ordered,
The Theory Presented in RAPA
RAPA defines a model of nondeterminism on a SMMP. Executions of
programs are represented by sequences of read events and write events.
The rules a SMMP obeys are represented by partial orders imposed on
the events for a program execution. An architecture for a SMMP
consists of the set of rules the SMMP is intended to obey.
From this simple model valuable results are obtained.
- The various rules of program order and of cache coherence are
- Let A1 and A2 be distinct architectures. In almost all cases
it can be shown that there is a simple program which can calculate a
result under one architecture which it demonstrably cannot calculate
under the other. Such a program is said to distinguish A1 and A2.
- In some few cases it is shown that for particular A1 and A2,
no distinguishing program exists. Then A1 and A2 are called
- Let A1 and A2 be two architectures consisting of any subset
of the normal rules of behavior. Further, let A1 and A2 be identical
except that A1 includes the rule that all processes see each write
operation at the same instant, and A2 includes the rule that all
processes see all changes in the values of all operands in the same
order. A major accomplishment of RAPA is to show that A1 and A2 are
- A program search methodology is developed to facilitate
proofs of indistinguishability. This will someday find application in
the modelling of real machines.
Publication and Order Information
RAPA was published in 1992 by Prentice-Hall, Englewood Cliffs, NJ
A photocopy of RAPA can be obtained by telephoning University
Microfilms at (U.S.A.)1.800.521.3042 and asking for Order No.
AU00490. The price is $79.40 (paperback) or $85.40 (hardback).
There are discounts for quantity orders.
Or you can go to
amazon.com and ask them to order it for you from University
Microfilms. Amazon, of course, will charge a slightly higher
The best deal, that I know of, can be found by going to Amazon
and clicking on 'Used and New'.
"Used_bookseller" offers RAPA for $22.95, plus $3.99 for
shipping and handling. I have ordered several copies of RAPA
from him; the books have been pristine. His email address is
Since the publication of RAPA in 1992, the ideas in the book have
been developed further, most concretely in the form of a program for
detecting relaxed behavior by running on real SMMPs. Further
information on this and other developments can be found through
the Site Map.
For a list of known errors in RAPA, see
For an informal history of the writing of RAPA, see History.
To contact the author .
Last updated June 8, 2008.