How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs was a short article published in 1979 by Leslie Lamport, and according to him,

"What made this paper worth reading was its simple, precise definition of sequential consistency as the required correctness condition [for multiprocess algorithms]."

And although defining sequential consistency is what this article is most known for, it was not the only purpose of the article.

According to Lamport, the customary approach to designing and proving the correctness of multiprocess algorithms assumes that the multiprocessor computer is sequentially consistent, but a computer built of sequential processors does not guarantee that that is the case. Lamport then introduces two requirements for multiprocess computers that ensure the computer is in fact, sequentially consistent.

Let's look at the definitions of a sequential processor, sequential consistency, and then look at an example that shows that a computer with several sequential processors is not necessarily sequentially consistent. After that we'll take a look at the requirements a multiprocessor computer must implement in order to be sequentially consistent.

A single processor may execute operations in a different order than is specified by the program that it is executing. Imagine that a program has a write instruction to memory followed by a read instruction from a different section of memory. If the write instruction is waiting for a value to write, the processor could go ahead and execute the read instruction while it is waiting. The program will still be correct as long as the result of the execution is the same as if the operations were executed in the order specified by the program.

A processor that satisfies that condition is sequential.

A multiprocessor computer satisfying the following condition is sequentially consistent:

The result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

In other words, the program specifies an order in which operations are to be performed. Each processor executes some of these operations, and within each processor, these operations were performed in the order that is specified in the program. But each processor is running those operations concurrently, and sequential consistency does not require the operations across all processors to have occurred in the order specified by the program.

Sequential consistency does imply that the operations within a processor are executed atomically, so one processor will not see the result of an operation performed by another until it is completed.

A multiprocessor computer built from sequential processors might lead one to think that it would naturally be sequentially consistent, but an example shows that this is not the case.

The following example is a mutual exclusion protocol with two processes. The purpose is that only one process will execute its critical section at any time.

A sequential processor could very well execute the read operation on the second line before the write operation on the first line, which could potentially cause both critical sections to run at the same time. So two sequential processors in a multiprocessor system could cause incorrect behavior.

If the system was also sequentially consistent, the operations on each processor would be performed in the order of the program, and it would not be possible for both critical sections to run at the same time.

The problem above leads to the first requirement.

Each processor issues memory requests in the order specified by its program.

And the second requirement

Memory requests from all processors issued to an individual memory module are serviced from a single FIFO queue. Issuing a memory request consists of entering the request on this queue.

arises from a problem where each memory module can have several ports, each port servicing memory requests for a particular processor. If multiple processors are waiting for requests on a memory module, and the memory module does not process them as a FIFO queue (round robin, for example), then race conditions can also cause the example above to execute both critical sections at the same time.

These two requirements, along with a multiprocess computer built of sequential processors, ensures that it is sequentially consistent. Unfortunately, these requirements also make it impossible to for some optimizations that would be possible on single processor computers.

The advantage of sequential consistency is that one could then use conventional methods for designing and proving correctness of multiprocess algorithms.