Information Technology Reference
In-Depth Information
We close this section by describing a normal-form tree program for
table lookup
,an
important programming tool that can be used to compute an arbitrary function
f
(
n
)
:
A
n
→
m
on
n
variables whose value is an
m
-tuple. Each of the
n
variables is read and the value of
the function is found in a table. This is simulated by a tree program with branching factor
A
|A|
in which the variables are read in succession until they are all read, at which point the value of
the function is provided. An example of such a tree program for a function
f
(
3
)
:
B
3
→B
3
n
assignments to the
n
inputs. The sink vertices are labeled by the appropriate
m
-tuple. Such
table-lookup tree programs have computation time
n
and space proportional to
n
log
|A|
is shown in Fig.
10.13
. There is one path through the tree for each of the possible
|A|
since
n
+
1
they have
(
|A|
−
1
)
/
(
|A|−
1
)
vertices with
A
edges per vertex except for those at the lowest
level.
10.9.1 Branching Programs and Other Models
We begin this section with a comparison of branching programs and pebble games and con-
clude with a brief comparison of branching programs and the RAM model of computation.
The pebble model assumes that computation is serial and straight-line. If all algorithms
used for a particular problem are of this type, the pebble game is the appropriate model, es-
pecially if the lower bounds on space-time exchanges are larger than those provided by the
branching program model. (All algorithms used today for integer multiplication are straight-
line and the lower bounds on the space-time product for this problem are larger with the
pebble game than with the branching program model.) If the two models give the same lower
bounds, then we can invoke Lemma
10.9.3
to derive lower bounds on the space-time ex-
changes for pebbling from those for branching programs when
log
2
T
P
is small by comparison
with
S
P
,where
T
P
and
S
P
are the time and space used by the pebbling model.
Data-dependent reading of inputs may allow the branching program to perform a com-
putation more quickly than the pebbling model. For example, merging requires a space-time
product that is quadratic in the length of the input strings with the pebble game but only
linear in the branching program. (See Section
10.10.2
.) This demonstrates that the branching
program is a much more natural model for this problem.
If the lower bounds derived with the branching program are comparable in strength to
those offered by the pebbling model, as is true for most of the problems considered in this
chapter, straight-line programs are the better model for these problems. But the extra flexibility
offered by branching programs means that when their results are comparable to those provided
by the pebble game, one must work harder to obtain them. (See Sections
10.11
and
10.12
.)
The branching program measures the time to read inputs but ignores the time for com-
putations and the production of outputs. By contrast, the pebble game measures the time to
read inputs, perform computations, and produce outputs. Although the time for computations
generally cannot be ignored, the methods available today to derive lower bounds for both mod-
els are based on the time spent reading inputs. But while for many problems the time to read
inputs dominates computation time for many values of space, when space is large the pebbling
model has the potential to give larger lower bounds than the branching program model. For
example, no way is known to compute the
n
-point DFT with fewer than
Θ(
n
log
n
)
steps,
the number used by the FFT algorithm, although in the limit of large space the branching
program gives a lower bound on space proportional to
n
.
To simulate the pebbling of a DAG by a branching program we must give an
interpreta-
tion
to each vertex of the DAG: assign an operation to each non-input vertex and a variable as
Search WWH ::
Custom Search