178 PARALLEL ALGORITHMS
eople have recognized for a long time that in most instances two people
can accomplish a task faster than one, and three people can accomplish
it even faster. The way that this has been implemented in practice has
varied. In offices, folders would be refiled faster if they were split among a
group of workers. Assembly lines speed up a process, because if one person
does the same task over and over, that person can do it more quickly because
he or she doesn’t need to take time to change tools. Bucket brigades were dis-
covered when people realized that more buckets of water could be moved if,
instead of having people running back and forth, they stood in a line and just
passed the buckets back and forth.
When we talk about parallel algorithms and programming, we see very sim-
ilar concepts. There are multitasking systems, where each processor does the
same task with different data. There are pipelined systems, where each proces-
sor does just one step of the task of decoding and executing a program instruc-
tion, passing the results onto another processor, which does the next step.
Dataflow systems set up a series of processors to carry out a task or calculation,
and then the input data is passed from processor to processor in the calculation
of the result.
This chapter is an introduction to the concept of parallel algorithms. Due to
the complex nature of parallel algorithms and programming, to cover these
ideas completely would at least double the size of this book. We begin with an
overview of some of the general concepts related to the structure of parallel
computer systems and then look at parallel algorithms for some of the prob-
lems we have considered in Chapters 2 through 6. The parallel algorithms pre-
sented will not always be the best parallel option but instead will give you an
idea of how the problem could be solved in a parallel manner. The amount of
detail that would be necessary to always present the most efficient parallel algo-
rithm is well beyond this text.7.1 Parallelism Introduction
In this section, we will introduce the basic concepts involved in a study of par-
allelism. We will begin looking at a way to categorize processing by a com-
puter. We then will look at architectures that are used to implement these
categories. This section will conclude with an examination of some of the
principles that we will use in our analysis of parallel algorithms.P