Parallel Computation - Models of Computation: Exploring the Power of Computing - page 318

role similar to that of the RAM for serial computation, that is, that programs written for the
BSP model can be translated into efficient code for a variety of parallel machines.
The BSP model explicitly assumes that a) computations are divided into supersteps ,b)all
processors are synchronized after each superstep, c) processors can send and receive messages
to and from all other processors, d) message transmission is non-blocking (computation can
resume after sending a message), and e) all messages are delivered by the end of a superstep.
The important parameters of this model are p , the number of processors, s , the speed of each
processor, l , the latency of the system, which is the number of processor steps to synchronize
processors, and g , the additional number of processor steps per word to deliver a message.
Here g measures the time per word to transmit a message between processors after the path
between them has been set up; l measures the time to set up paths between processors and/or
to synchronize all p processors. Each of these parameters must be appraised under “normal”
computational and communication loads if the model is to provide useful estimates of the time
to complete a task.
For the BSP model to be effective, it must be possible to keep the processors busy while
waiting for communications to be completed. If the latency of the network is too high, this
will not be possible. It will also not be possible if algorithms are not designed properly. For
example, if all processors attempt to send messages to a single processor, network congestion
will prevent the messages from being answered quickly. It has been shown that for many
important problems data can be distributed and algorithms designed to make good use of the
BSP model [ 348 ]. It should also be noted that the BSP model is not effective on problems that
are not parallelizable, such as may be the case for P -complete problems (see Section 8.9 ).
Although for many problems and machines the BSP model is a good one, it does not
take into account network congestion due to the number of messages in transit. The LogP
model extends the BSP model by explicitly accounting for the overhead time (the o in LogP)
to prepare a message for transmission. The model is also characterized by the parameters L , g ,
and P that have the same meaning as the parameters l , g ,and p in the BSP model. The LogP
and BSP models are about equally good at predicting algorithm performance.
Many other models have been proposed to capture one aspect or another of practical par-
allel computation. Chapter 11 discusses some of the parallel I/O issues.
.......................................
Problems
PARALLEL COMPUTERS WITH MEMORY
7.1 Consider the design of a bus arbitration sequential circuit for a computer containing
four CPUs. This circuit has four Boolean inputs and outputs, one per CPU. A CPU
requesting bus access sets its input to 1 and waits until its output is set to 1, after which
it puts its word and destination address on the bus. CPUs not requesting bus access set
their bus arbitration input variable to 0.
At the beginning of each cycle the bus arbitration circuit reads the input variables and,
if at least one of them has value 1, sets one output variable to 1. If all input variables
are 0, it sets all output variables to 0.
Design two such arbitration circuits, one that grants priority to the lowest indexed
input that is 1 and a second that grants priority alternately to the lowest and highest
indexed input if more than one input variable is 1.