Information Technology Reference
In-Depth Information
v
1
v
2
u
1
u
2
p
2
Figure 11.8
A two-input butterfly graph with pebbles
p
1
and
p
2
resident on inputs.
p
1
obtain an upper bound on the number of pebbled vertices if we assume that both of them
are pebbled. In this proof we let
denote the
S
pebbles available to pebble
G
. We assign an integer cost
num
(
p
i
)
(initialized to zero) to the
i
th pebble
p
i
in order to
derive an upper bound to the total number of pebble placements made on
G
.
Consider a matching pair of output vertices
v
1
and
v
2
of a two-input butterfly graph
and their common predecessors
u
1
and
u
2
, as suggested in Fig.
11.8
. Suppose that on the
next step we can place a pebble on
v
1
. Then pebbles (call them
p
1
and
p
2
)mustresideon
u
1
and
u
2
.Advance
p
1
and
p
2
to both
v
1
and
v
2
. (Although the rules stipulate that an
additional pebble is needed to advance the two pebbles, violating this restriction by allowing
their movement to
v
1
and
v
2
can only increase the number of possible moves, a useful effect
since we are deriving an upper bound on the number of pebble placements.)
After advancing
p
1
and
p
2
,if
num
(
p
1
)=
num
(
p
2
)
, augment both by 1; otherwise,
augment the smaller by 1. Since the predecessors of two vertices in an FFT graph are in
disjoint trees, there is no loss in assuming that all
S
pebbles remain on the graph in a
pebbling that maximizes the number of pebbled vertices. Because two pebble placements
are possible each time
num
(
p
i
)
increases by 1 for some
i
,
ρ
(
S
,
G
)
{
p
i
|
1
≤
i
≤
S
}
2
1
≤i≤S
num
(
p
i
)
.
We now show that the number of vertices that contained pebbles initially and are con-
nected via paths to the vertex covered by
p
i
is at least 2
num
(
p
i
)
.Thatis,2
num
(
p
i
)
≤
≤
S
or
num
(
p
i
)
log
2
S
, from which the upper bound on
ρ
(
S
,
G
)
follows. Our proof is by
induction. For the base case of
num
(
p
i
)=
1, two pebbles must reside on the two immedi-
ate predecessors of a vertex containing the pebble
p
i
. Assume that the hypothesis holds for
num
(
p
i
)
≤
1. We show that it holds for
num
(
p
i
)=
e
. Consider the first point in
time that
num
(
p
i
)=
e
. At this time
p
i
and a second pebble
p
j
reside on a matching pair
of vertices,
v
1
and
v
2
. Before these pebbles are advanced to these two vertices from
u
1
and
u
2
, the immediate predecessors of
v
1
and
v
2
, the smaller of
num
(
p
i
)
and
num
(
p
j
)
has a
value of
e
≤
e
−
1. This must be
p
i
because its value has increased. Thus, each of
u
1
and
u
2
has at least 2
e−
1
predecessors that contained pebbles initially. Because the predecessors of
u
1
and
u
2
are disjoint, each of
v
1
and
v
2
has at least 2
e
−
=
2
num
(
p
i
)
predecessors that carried
pebbles initially.
This upper bound on the
S
-spaniscombinedwithTheorem
11.4.1
to derive a lower
bound on the I/O time at level
l
to pebble the FFT graph. We derive upper bounds that match
to within a multiplicative constant when the FFT graph is pebbled in the standard MHG. We
develop bounds for the red-blue pebble game and then generalize them to the MHG.
Search WWH ::
Custom Search