Information Technology Reference
In-Depth Information
THEOREM
11.5.4
Let the FFT graph on
n
=
2
d
inputs,
F
(
d
)
, be pebbled in the
red-blue
pebble game
with
S
red pebbles. When
S
≥
3
there is a pebbling of
F
(
d
)
such that the following
bounds hold simultaneously, where
T
(
2
)
1
(
p
1
,
F
(
d
)
)
and
T
(
2
)
(
p
1
,
F
(
d
)
)
are the computation and
2
I/O time in a minimal pebbling of
F
(
d
)
:
T
(
2
)
1
(
S
,
F
(
d
)
)=Θ(
n
log
n
)
(
S
,
F
(
d
)
)=Θ
n
log
n
log
S
T
(
2
)
2
Proof
The lower bound on
T
(
2
1
(
S
,
F
(
d
)
)
is obvious; every vertex in
F
(
d
)
must be peb-
bled a first time. The lower bound on
T
(
2
2
(
S
,
F
(
d
)
)
follows from Corollary
11.4.1
,Theo-
rem
11.3.1
, Lemma
11.5.2
, and the obvious lower bound on
|
V
|
. We now exhibit a pebbling
strategy giving upper bounds that match the lower bounds up to a multiplicative factor.
As shown in Corollary
6.7.1
,
F
(
d
)
can be decomposed into
d/e
stages,
d/e
stages
containing 2
d−e
copies of
F
(
e
)
and one stage containing 2
d−k
copies of
F
(
k
)
,
k
=
d
−
e
.(SeeFig.
11.9
.) The output vertices of one stage are the input vertices to the next.
For example,
F
(
12
)
can be decomposed into three stages with 2
12
−
4
=
256 copies of
F
(
4
)
on each stage and one stage with 2
12
copies of
F
(
0
)
,asinglevertex.(SeeFig.
11.10
.) We use
this decomposition and the observation that
F
(
e
)
can be pebbled level by level with 2
e
+
1
level-1 pebbles without repebbling any vertex to develop our pebbling strategy for
F
(
d
)
.
Given
S
red pebbles, our pebbling strategy is based on this decomposition with
e
=
d
0
=
d/e
log
2
(
S
−
1
)
.Since
S
≥
3,
d
0
≥
1. Of the
S
red pebbles, we actually use only
S
0
=
2
d
0
+
1. Since
S
0
≤
S
, the number of I/O operations with
S
0
red pebbles is no
...
F
(
e
)
t
,1
F
(
e
)
t
,2
F
(
e
)
t
,3
F
(
e
)
t
,4
F
(
e
)
t
,5
F
(
e
)
t
,6
F
(
e
)
t
,
τ
...
F
(
d−e
)
b
,1
F
(
d−e
)
b
,2
F
(
d−e
)
b
,
β
Figure 11.9
Decomposition of the FFT graph
F
(
d
)
into
β
=
2
e
bottom FFT graphs
F
(
d−e
)
and
τ
=
2
d−e
top
F
(
e
)
. Edges between bottom and top sub-FFT graphs identify common
vertices between the two.
Search WWH ::
Custom Search