Information Technology Reference
In-Depth Information
means that I/O operations at these levels are performed only on inputs, giving the bound
T
(
L
)
l
(
p
,
F
(
d
)
,
)=
O
(
n
)
,
n
=
2
d
,for
k
+
1
k
, we pebble
F
(
d
)
by
P
≤
r
≤
L
.When
r
≤
decomposing it into
stages such that each stage, except possibly the first, contains
2
d−d
k
copies of the FFT subgraph
F
(
d
k
)
. The first stage has 2
d−d
∗
copies of
F
(
d
∗
)
of depth
d
∗
=
d
d/d
k
1
)
d
k
, which we treat as subgraphs of the subgraph
F
(
d
k
)
and pebble to
completion with a number of operations at each level that is at most the number to pebble
F
(
d
k
)
. Each instance of
F
(
d
k
)
−
(
d/d
k
−
is pebbled with
s
k−
1
pebbles at level
k
−
1orlowerand
a pebble at level
k
or higher is left on its output. Since
s
k
+
1
≥
n
+
1, there are enough
pebbles to do this.
Thus
T
(
L
)
l
(
p
,
F
(
d
)
,
P
)
satisfies the following bound for 1
≤
l
≤
L
:
T
(
L
)
l
2
d−d
k
T
(
L
)
l
(
p
,
F
(
d
)
,
(
p
,
F
(
d
k
)
,
P
)
≤
d/d
k
P
)
Combining this with the earlier result, we have the following upper bound on the number
of I/O operations for 1
≤
l
≤
k
:
T
(
L
)
l
(
p
,
F
(
d
)
,
(
d
k
/d
l
)
2
d
+
1
P
)
≤
d/d
k
Since, as noted earlier,
d
r
≥
log(min(
s
r
−
1,
n
))
/
4, we obtain the desired upper bound on
T
(
L
)
l
)
by combining this result with the bound on
n
(
k
)
l
(
p
,
F
(
d
)
,
P
given above.
The above results are derived for standard MHG and the family of FFT graphs. We now
strengthen these results in two ways when the I/O-limited MHG is used. First, the I/O limita-
tion requires more time for a given amount of storage and, second, the lower bound we derive
applies to every graph for the discrete Fourier transform, not just those for the FFT.
It is important to note that the efficient pebbling strategy used in the standard MHG
makes extensive use of level-
L
pebbles on intermediate vertices of the FFT graph. When this is
not allowed, the lower bound on the I/O time is much larger. Since the lower bounds for the
standard and I/O-limited MHG on matrix multiplication are about the same, this illustrates
that the DFT and matrix multiplication make dramatically different use secondary memory.
(In the following theorem a
linear straight-line program
is a straight-line program in which
the operations are additions and multiplications by constants.)
THEOREM
11.5.6
Let
FFT
(
n
)
be
any DAG
associated with the DFT on
n
inputs when real-
ized by a linear straight-line program. Let
FFT
(
n
)
be pebbled with strategy
P
in the
I/O-limited
MHG
with resource vector
p
and let
s
l
=
j
=
1
p
j
.If
S
=
s
L−
1
≤
n
, then for each pebbling
P
, the computation and I/O time at level
l
must satisfy the following bounds:
strategy
)=Ω
n
2
S
T
(
L
)
l
(
p
,
FFT
(
n
)
,
P
≤
l
≤
L
for
1
Also, when
n
=
2
d
, there is a pebbling
of the FFT graph
F
(
d
)
such that the following relations
P
hold simultaneously when
S
≥
2
log
n
:
⎧
⎨
O
n
2
S
+
n
log
S
l
=
1
T
(
L
)
l
O
n
2
S
log
s
l
−
1
2
(
p
,
F
(
d
)
,
P
)=
⎩
log
S
+
n
≤
l
≤
L
Search WWH ::
Custom Search