184 PARALLEL ALGORITHMS
If we consider that the general model for the algorithms presented in Chap-
ters 2 through 6 is a machine that can randomly access any location of mem-
ory, we can call that a random access machine (RAM). The base model that we
will use for this chapter is a parallel version of this machine called a parallel
random access machine (PRAM). Our PRAM will be a tightly coupled
machine with all of the processors sharing one block of memory. Each proces-
sor may have a small number of registers so that some data can be kept with the
processor, but in general we will assume that the data is kept in the shared
memory.
In addition to having a tightly coupled machine, we will also require that all
of our processors follow the same processing cycle of a read from memory,
doing an operation, and then writing a result back to memory. This means that
all of the processors will read at the same time, process at the same time, and
write at the same time. There are two times when we may have contention for
a memory location: when reading and when writing. By enforcing this three-
step cycle, we don’t need to worry about the additional problem of processor
X reading a value from memory, and while it is working with it, processor Y
changes the value in that memory location. We also don’t need to worry about
contention between a processor reading from a memory location while
another one is trying to write to that location.
We can handle the contention times by allowing access to be either concur-
rent or exclusive. In concurrent access, more than one processor can have
access to a memory location at one time. In exclusive access, only one proces-
sor can have access to a memory location and an attempt by more than one to
gain access is signaled as an error.
In the case of reading, concurrent access will not be a problem. We will,
however, look at some algorithms that can operate under exclusive read access.
If we are operating under an exclusive read, and more than one processor tries
to read from one memory location, an error will occur.
When we write, we also have the choice of exclusive or concurrent. If we
have exclusive write, only one processor will be allowed to write into one
location of memory, and an error will occur if more than one tries. With
exclusive write, two processors are, however, allowed to write to different
memory locations at the same time. With concurrent access, we have a more
involved situation because we must decide how the conflict will be resolved. In