Information Technology Reference
In-Depth Information
CHAPTER
Space-Time Tradeoffs
An important question in the study of computation is how best to use the registers of a CPU
and/or the random-access memory of a general-purpose computer. In most computations, the
number of registers (space) available is insufficient to hold all the data on which a program
operates and registers must be reused. If the space is increased, the number of computation
steps (time) can generally be reduced. This is an example of a space-versus-time tradeoff. In
this chapter we examine tradeoffs between the number of storage locations and computation
time using the pebble game and the branching program model.
The pebble game assumes that computations are done with straight-line programs in a
data-independent fashion. Each such program is modeled by a directed acyclic graph. A
pebble on a vertex indicates that its value is in a register. The goal of the game is to pebble the
output vertices of the graph with numbers of pebbles (space) and steps (time) that are minimal,
that is, neither can be reduced without increasing the other.
A branching program models data-dependent computation under the assumption that in-
put variables assume a bounded number of values. Such a program is defined by a directed
acyclic multigraph (there may be more than one edge between vertices) that specifies the order
in which inputs are read. Time is the length of the longest path in a multigraph and space is
the logarithm of its number of vertices.
For both models we present techniques to derive lower bounds on the exchange of space
S
for time
T
. For most problems examined here these exchanges are of the form
ST
=Ω(
n
2
)
,
where
n
is the size of the problem input. Upper bounds on
ST
are obtained by evaluating
S
and
T
for particular algorithms.
Because the branching program is more general than the pebble game, it is more difficult
to obtain good lower bounds with it, and for this reason we begin with the pebble game. In
addition, the pebble game is appropriate for problems such as integer multiplication, convo-
lution, and matrix multiplication on which only straight-line programs are used. For other
problems, such as merging and sorting, the algorithms used typically involve branching and
for them the branching program is the better model.
We also exhibit extreme results for the pebble game by showing that the time to pebble
some graphs goes from minimal to exponential in the size of the graphs when the number
of pebbles changes by 1, a warning against trying too hard to minimize the number of CPU
registers used in a computation.
461
Search WWH ::
Custom Search