Information Technology Reference
In-Depth Information
A good strategy for pebbling the vertices of an FFT graph is
to pebble the top FFT
F
(
e
)
t
,
j
2
d−e
graphs
individually. The vertices of a top FFT graph in Fig.
10.8
are highlighted. To pebble its inputs, which are output vertices of FFT graphs below the
split, it suffices to pebble the subtrees rooted at these vertices. (They are also highlighted.)
Such subtrees are completely balanced binary trees with 2
d−e
inputs. Thus,
d
{
|
1
≤
j
≤
}
−
e
+
1 pebbles
and 2
d−e
+
1
−
1 pebble placements suffice to place a pebble on the root of one such subtree.
If these subtrees are pebbled in sequence, pebbles can be left on the inputs to a 2
e
-point FFT
graph
F
(
e
)
above the split using at most 2
e
+
d
e
pebbles and 2
e
(
2
d−e
+
1
1
)
pebble
placements. Since 2
e
+
1 pebbles and
e
2
e
pebble placements suffice to pebble
F
(
e
)
level by
level without repebbling vertices, it follows that all instances of
F
(
e
)
above the split can be
pebbled using a total of
T
=
2
d
(
2
d−e
+
1
+
e
−
−
1
)
pebble placements and
S
=
2
e
+
d
−
−
e
pebbles.
We now derive an upper bound on
T
by deriving upper and lower bounds on the value
of
e
satisfying
S
=
2
e
+
d
2
e
,wehave
e
−
e
.Because
S
≥
≤
log
2
S
.Let
e
0
be the smallest
integer such that 2
e
0
+
1
+
d
S
.Then,2
e
0
+
d
≥
−
e
0
≤
S
and
e
≥
e
0
.Consequently,
2
e
≥
(
S
−
d
)
/
2, from which we have
2
2
d
T
=
2
d
(
2
d−e
+
1
+
e
d
)
+
2
d
log
2
S
−
1
)
≤
4
(
S
−
2
d
/
(
S
22
d
/S
when 2
d
(
2
d
/d
)+
d
,fromwhichthe
Finally,
log
2
S
≤
−
d
)
≤
≤
S
≤
desired conclusion follows.
10.5.6 Merging Networks
In this section we consider networks of comparators to merge two sorted lists. Such networks
were described in Section
6.8
and an example was given, Batcher's
(
m
,
p
)
bitonic merging
network.
A
comparator element
computes the function
⊗
A
2
→A
2
that returns the maximum
:
⊗
(
a
,
b
)=(max(
a
,
b
)
,
min(
a
,
b
))
.
and minimum of its two arguments, that is,
LEMMA
10.5.5
Consider a comparator-based merging network that merges two sorted lists of
n
distinct elements
x
=(
x
1
,
x
2
,
...
,
x
n
)(
x
i
≤
x
i
+
1
)
and
y
=(
y
1
,
y
2
,
...
,
y
n
)(
y
i
≤
y
i
+
1
)
to produce the sorted list
z
=(
z
1
,
z
2
,
...
,
z
2
n
)
of
2
n
outputs
(
z
i
≤
z
i
+
1
)
.Theremu tbe
r
vertex-disjoint paths from any
r
inputs in
x
to the outputs in
z
to which they are mapped by the
network.
Proof
Working backwards from the
r
selected outputs, we see that each output exits from
the comparator elements to which it is attached via a disjoint path, as suggested for three
outputs in Fig.
10.9
. Extending this argument to the remainder of the network establishes
the result.
We next show that inputs can be given values to cause a merging network to shift its values
in a fashion that permits the derivation of a space-time lower bound.
THEOREM
10.5.6
Any straight-line comparator-based program that merges two sorted lists of
n
elements requires space
S
and time
T
satisfying
ST
=Ω(
n
2
)
Search WWH ::
Custom Search