Reasoning About Parallel Architectures (RAPA)
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 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.

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.

  1. The various rules of program order and of cache coherence are clearly defined.

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

  3. In some few cases it is shown that for particular A1 and A2, no distinguishing program exists. Then A1 and A2 are called indistinguishable.

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

  5. 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 (ISBN 0-13-767187-3).

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.

Related Links

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

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

To contact the author .

Last updated June 8, 2008.