Information Technology Reference
In-Depth Information
Odd Merge
Even Merge
u
1
v
1
u
2
z
1
x
1
x
2
x
3
z
2
z
3
z
4
z
5
z
6
z
7
z
8
v
2
u
3
x
4
y
2
y
1
y
4
y
3
v
3
u
4
v
4
Figure 10.9
Movement of an ordered subset of the items through Batcher's bitonic merge
algorithm.
This lower bound can be achieved to within a constant multiplicative factor when
2
log
2
n
≤
S
≤
(
n/
log
2
n
)+log
2
n
.
Proof
Let
n
be divisible by 2. Any consecutive
n/
2inputsin
x
can be shifted to the middle
n/
2 positions in
z
through a judicious choice of values for
y
. To see this, observe that the
first
k
=
n
−
n/
4
−
l
components of
y
,
l
≤
n/
2, can be chosen to be less than the first
l
components of
x
with the remaining
n
k
components of
y
chosen to be larger than the
first
l
+
n/
2 components of
x
. This will cause elements in positions
l
+
1,
l
+
2,
...
,
l
+
n/
2
to shift into positions
n
−
n/
4
+
1,
...
,
n
+
n/
4.
Since coalescing vertices in a graph reduces neither the time nor space needed to peb-
ble it, coalesce input vertices assigned to
x
whose indices are equivalent modulo
n/
2. By
Lemma
10.5.5
, the new graph has
n/
2-vertex disjoint paths between the new inputs and the
n/
2 outputs in positions
l
+
1,
l
+
2,
...
,
l
+
n/
2 for each of the
n/
2 cyclic permutations.
It follows that the argument applied to the cyclic shifting function (Lemma
10.5.2
) applies
to this function. Thus, the merging network computes a function containing a subfunction
that is
(
2,
n/
2,
n/
2,
n/
4
)
-independent. The lower bound follows from Corollary
10.4.1
.
As shown in Section
6.8
, the graph of Batcher's bitonic merging network is an FFT
graph. Thus, the upper bounds given in Theorem
10.5.5
apply.
−
10.6 Worst-Case Tradeoffs for Pebble Games*
In this section we show that degree-
d
graphs on
n
vertices can be pebbled with
O
(
n/
log
n
)
pebbles (Theorem
10.7.1
) and that some graphs require this many (Theorem
10.8.1
). These
results do not answer the question of how bad the space-time tradeoff can be for an arbitrary
graph. To address this question we must make it precise. Lengauer and Tarjan [
197
]stateit
as follows: is there a value for the space
S
,say,
S
J
(
n
)
,suchthatforpositiveconstants
c
1
(
d
)
and
c
2
(
d
)
if
S
≤
c
1
(
d
)
S
J
(
n
)
, some graph on
n
vertices requires time superpolynomial in
Search WWH ::
Custom Search