by William W. Collier

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 machines?

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 coherent machine.

RAPA describes programs which can detect the failure of a machine to be cache coherent, sequentially consistent, strongly ordered, etc.

From this simple model valuable results are obtained.

- The various rules of program order and of cache coherence are
clearly defined.
- 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
indistinguishable.
- 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
indistinguishable.
- A program search methodology is developed to facilitate proofs of indistinguishability. This will someday find application in the modelling of real machines.

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 price.

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 used_bookseller@yahoo.com.

For a list of known errors in RAPA, see Errata.

For an informal history of the writing of RAPA, see History.

To contact the author .

Last updated June 8, 2008.