[next] [prev] [prev-tail] [tail] [up]
The previous chapter studied the applicability of randomness to speeding up sequential
computations. This chapter considers how parallelism achieves a similar objective. The
first section introduces the notion of parallelism in programs. A generalization of RAM's,
called parallel random access machines, or PRAM's, that allows a high-level abstraction
for parallel computations is taken up in Section 2. The third section introduces families of
Boolean circuits, with the goal of providing a hardware-level abstraction for parallel
computations. The problems involved in adapting the general class of families of Boolean
circuits as a low-level abstraction is discussed in Section 4, and a restricted class
is proposed for such a purpose. The families in this restricted class are called
uniform families of circuits. The fifth section relates the uniform families of
circuits to sequential computations. In particular, it shows that parallelism does not
increase the class of tractable problems. In addition, it discusses the applicability of
parallelism in significantly increasing the speed of feasible computations. In
Section 6 the chapter concludes by relating PRAM's and uniform families of
circuits.
7.1 Parallel Programs
7.2 Parallel Random Access Machines
7.3 Circuits
7.4 Uniform Families of Circuits
7.5 Uniform Families of Circuits and Sequential Computations
7.6 Uniform Families of Circuits and PRAM's
Exercises
Bibliographic Notes
[next] [prev] [prev-tail] [front] [up]