Information Technology Reference
In-Depth Information
...
...
...
F
(
4
)
256
Figure 11.10
The decomposition of an FFT graph
F
(
12
)
into three stages each containing 256
copies of
F
(
4
)
. The gray areas identify rows of
F
(
12
)
in which inputs to one copy of
F
(
4
)
are
outputs of copies of
F
(
4
)
at the preceding level.
less than with
S
red pebbles. Let
d
1
=
.Then,
F
(
d
)
is decomposed into
d
1
stages
each containing 2
d−d
0
copies of
F
(
d
0
)
and one stage containing 2
d−t
copies of
F
(
t
)
where
t
=
d
d/d
0
d
0
,eachvertexin
F
(
t
)
can be pebbled with
S
0
pebbles without
re-pebbling vertices. The same applies to
F
(
d
0
)
.
The pebbling strategy for the red-blue pebble game is based on this decomposition.
Pebbles are advanced to outputs of each of the bottom FFT subgraphs
F
(
t
)
using 2
t
+
1
−
d
0
d
1
.Since
t
≤
S
0
red pebbles, after which the red pebbles are replaced with blue pebbles. The subgraphs
F
(
d
0
)
in each of the succeeding stages are then pebbled in the same fashion; that is, their blue-
pebbled inputs are replaced with red pebbles and red pebbles are advanced to their outputs
after which they are replaced with blue pebbles.
This strategy pebbles each vertex once with red pebbles with the exception of vertices
common to two FFT subgraphs which are pebbled twice. It follows that
T
(
L
)
1
≤
(
S
,
F
(
d
)
)
≤
2
d
+
1
(
d
+
1
)=
2
n
(log
2
n
+
1
)
. ThisstrategyalsoexecutesoneI/Ooperationforeach
of the 2
d
inputs and outputs to
F
(
d
)
and two I/O operations for each of the 2
d
vertices
common to adjacent stages. Since there are
d/d
0
d/d
0
−
stages, there are
1suchpairs
of stages. Thus, the number of I/O operations satisfies
T
(
L
)
2
(
S
,
F
(
d
)
)
2
d
+
1
≤
d/d
0
≤
2
n
(log
2
n/
(log
2
S/
4
)+
1
)=
O
(
n
log
n/
log
S
)
.
The bounds for the multi-level case generalize those for the red-blue pebble game. As with
matrix multiplication, care must be taken to avoid memory fragmentation.
THEOREM
11.5.5
Let the FFT graph on
n
=
2
d
inputs,
F
(
d
)
, be pebbled in the
standard MHG
with resource vector
p
.Let
s
l
=
j
=
1
p
j
and let
k
be the largest integer such that
s
k
≤
n
.When
3
, the following lower bounds hold for all pebblings of
F
(
d
)
and there exists a pebbling
p
1
≥
P
for
Search WWH ::
Custom Search