180 PARALLEL ALGORITHMS
different perspective, we see that finding if a number is prime can be
improved with this type of machine.^1 If we have N processors, in one cycle
we can determine if a number between 1 and N^2 is prime with a multiple
instruction single data (MISD) machine, because if X is not prime, it will
have a factor that is less than or equal to. To find out if X≤N^2 is prime,
we have the first processor divide by 2, the second divide by 3, the third
divide by 4, and so on up to processor K 1, which divides by K, where
If any of these processors finds that it can divide evenly by the
number it is given, X is not prime. So in one operation, each of the proces-
sors does its division and we have the result. On a sequential machine, you
should see that a simple solution to this problem would take at least
passes through a loop doing a division each time.Multiple Instruction Multiple Data
Our final category is the most flexible of the options. In this case, we have mul-
tiple processors, each of which is capable of carrying out a different instruction.
We also have multiple data streams, so that each processor can work on inde-
pendent data sets. In practice, this means that a multiple instruction multiple
data (MIMD) system could be running different programs on each processor or
different parts of the same program or the vector operations we saw for the
SIMD configuration. This category includes most of the modern attempts at
parallelism, including clusters of computers and multiprocessor systems.■ 7.1.2 Parallel Architectures
There are two main issues in the architecture of parallel computer systems:
How are memory and processors connected, and how do the processors com-
municate? These issues will be used when we discuss algorithms because some
parallel options are best suited to one or another of these configurations.Loosely versus Tightly Coupled Machines
In a loosely coupled machine, each of the processors has its own memory, and
communication between processors occurs across “network” cables. This is the
architecture of computer clusters, where each element of the cluster is a com-(^1) Recall that a prime number is one that is only evenly divisible by itself and the num-
ber 1. So, for example, 17 is a prime number because the only numbers between 1 and
17 that divide it evenly are 1 and 17.
X
KX=.
X