Next: Chapter Notes
Up: 1 Parallel Computers and Computation
Previous: 1.5 Summary
Exercises 610 require you to describe a parallel
algorithm. You should describe the task/channel structure created by
the algorithm and provide a definition for each task, including its
interface (inports and outports), its local data, and the actions it
performs.

If today's workstations execute at operations per second, and
performance increases at a rate of 25 percent per year, how long will
it be before we have workstations capable of operations per
second? ?

A climate model requires floating point operations for a
tenyear simulation. How long would this computation take at
floating point operations per second (10 Mflops)?

A climate model generates bytes of data in a tenday
simulation. How fast must data be transferred to secondary storage?
What transfer rate is required if we are to search this data in ten
minutes?

Consider a threedimensional chip. Demonstrate that chip volume
V
and computation time T
are related as , just as area
A
and computation time are related as in a
twodimensional chip.

Execute the parallel algorithm described in Section 1.4.1 by
hand for N=4
, and satisfy yourself that execution is
deterministic.

Adapt the parallel algorithm of Section 1.4.1 to deal with a
twodimensional finite difference problem in which the value of each
point in a twodimensional grid of size
N
N
is updated as follows:

Describe a variant of the parallel algorithm of
Section 1.4.2 that allows for the case when N
is
even.

Describe a parallel algorithm for Hoare's quicksort
algorithm [153] based on the parallel divideandconquer
strategy employed in Section 1.4.3.

Describe a task/channel structure for a parallel database system in
which M
concurrently executing users can generate requests to
read and write data located in N
databases and requests to
access different databases can be handled concurrently. You must use
less than M.N
channels.
Extend this structure to allow a user to request that a set of read
and write operations be performed as an atomic operation, that is,
without read or write operations generated by other tasks intervening.

Extend the parallel algorithms of Sections 1.4.1
and 1.4.3 to provide for the loading of initial data
values in from disk and the writing out of the solutions to disk.
Next: Chapter Notes
Up: 1 Parallel Computers and Computation
Previous: 1.5 Summary
© Copyright 1995 by Ian Foster