Information Technology Reference
In-Depth Information
The upper bound follows from Theorem
11.5.5
. We advance level-
L
pebbles to the
outputs of each of the two bottom FFT graphs
F
(
2
d
)
in Fig.
11.11
and then pebble the top
FFT graph. The number of I/O and computation steps used is triple that used to pebble
one such FFT graph. In addition, we perform
O
(
n
)
I/O and computation steps to combine
inputs to the top FFT graph.
The bounds for the I/O-limited version of the MHG for the convolution problem are
considerably larger than those for the standard MHG. They have a much stronger dependence
on
S
and
n
than do those for the FFT graph.
THEOREM
11.5.8
Let
H
(
n
)
convolve
be the graph of any DAG for the convolution of two
n
-tuples
using the convolution theorem,
n
=
2
d
.L t
H
(
n
)
convolve
be pebbled in the I/O-limited MHG
with the resource vector
p
and let
s
l
=
j
=
1
p
j
.If
S
=
s
L−
1
≤
n
, then the time to pebble
H
(
n
)
convolve
at the
l
th level,
T
(
L
)
(
p
,
H
(
n
)
convolve
)
, satisfies the following lower bounds simultaneously
l
≤
l
≤
L
:
for
1
convolve
)=Ω
n
3
S
2
T
(
L
)
l
(
p
,
H
(
n
)
when
S
n/
log
n
.
Proof
A lower bound is derived for this problem by considering a generalization of the
graph shown in Fig.
11.11
in which the three copies of the FFT graph
F
(
2
d
)
are replaced by
an arbitrary DAG for the DFT. This could in principle yield in a smaller lower bound on the
time to pebble the graph. We then invoke Lemma
11.3.2
to show that a lower bound can
be derived from a reduction of this new graph, namely, that consisting of two back-to-back
DFT graphs obtained by deleting one of the bottom FFT graphs. We then derive a lower
bound on the time to pebble this graph with the red pebble game and use it together with
Theorem
11.3.1
to derive the lower bounds mentioned above.
Consider pebbling two back-to-back DAGs for the DFT on
n
inputs,
n
even, in the red
pebble game. From Lemma
10.5.4
,the
n
-point DFT function is
(
2,
n
,
n
,
n/
2
)
-indepen-
dent. From the definition of the independence property (see Definition
10.4.2
), we know
that during a time interval in which 2
(
S
+
1
)
of the
n
outputs of the second DFT DAG
on
n
-inputs are pebbled, at least
n/
2
≤
2
(
S
+
1
)
of its inputs are pebbled. In a back-to-
back DFT graph these inputs are also outputs of the first DFT graph. It follows that for
each group of 2
(
S
+
1
)
of these
n/
2
−
−
2
(
S
+
1
)
outputs of the first DFT DAG, at least
n/
2
2
(
S
+
1
)
of its inputs are pebbled. Thus, to pebble a group of 2
(
S
+
1
)
outputs
of the second FFT DAG (of which there are at least
−
n/
(
2
(
S
+
1
))
groups), at least
(
n/
2
−
2
(
S
+
1
))
/
2
(
S
+
1
)
(
n/
2
−
2
(
S
+
1
))
inputs of the first DFT must be pe
bb
led.
n/
4
√
2and
Thus,
T
(
L
)
l
(
p
,
H
(
n
)
n
3
/
(
64
(
S
+
1
)
2
)
, since it holds both when
S
convolve
)
≥
≤
when
S>n/
4
√
2.
Let's now consider a pebbling strategy that achieves this lower bound up to a multiplica-
tive constant. The pebbling strategy of Theorem
11.5.5
can be used for this problem. It
represents the FFT graph
F
(
d
)
as a set of FFT graphs
F
(
e
)
on top and a set of FFT graphs
F
(
d−e
)
on the bottom. Outputs of one copy of
F
(
e
)
are pebbled from left to right. This
requires pebbling inputs of
F
(
d
)
from left to right once. To pebble all outputs of
F
(
d
)
,2
d−e
copies of
F
(
e
)
are pebbled and the 2
d
inputs to
F
(
d
)
are pebbled 2
d−e
times.
Search WWH ::
Custom Search