Information Technology Reference
In-Depth Information
LINEAR ARRAYS
7.8 Generalize the example of Section
7.5.1
to show that the product of an
n
×
n
matrix
1 steps on a linear systolic array.
7.9 Show that every algorithm on a linear array to compute the product of an
n
and an
n
-vector can be realized in 3
n
−
n
matrix
and an
n
-vector requires at least
n
steps. Assume that components of the matrix and
vector enter cells individually.
7.10 Design an algorithm for a linear array of length
O
(
n
)
that convolves two sequences
each of length
n
in
O
(
n
)
steps. Show that no substantially faster algorithm for such a
linear array exists.
×
MULTIDIMENSIONAL ARRAYS
7.11 Show that at most
σ
(
d
)=
2
d
2
+
2
d
+
1 cells are at most
d
edges away from any cell
in a two-dimensional systolic array.
7.12 Derive an expression for the distance between vertices
(
n
1
,
n
2
,
...
,
n
d
)
and
(
m
1
,
m
2
,
...
,
m
d
)
in a
d
-dimensional toroidal mesh and determine the maximum distance be-
tween two such vertices.
7.13 Design efficient algorithms to multiply two
n
×
n
matrices on a
k
×
k
mesh,
k
≤
n
.
HYPERCUBE-BASED MACHINES
7.14 Show that the vertices of the 2
d
-input FFT graph can be numbered so that edges be-
tween levels correspond to swaps across the dimensions of a
d
-dimensional hypercube.
7.15 Show that the convolution function
f
(
n
,
m
)
:
R
n
+
m
R
n
+
m−
1
over a commutative
→
conv
can be implemented by a fully normal algorithm in time
O
(log
n
)
.
7.16 Prove that the unshuffle operation on a linear array of
n
=
2
d
cells can be done with
2
d
ring
R
1 comparison/exchange steps.
7.17 Prove that the algorithm described in Section
7.7.4
to simulate a normal hypercube
algorithm on a linear array of
n
=
2
d
elements correctly places into exchange locations
elements whose indices differ by successive powers of 2.
7.18 Describe an efficient algorithm for a linear array that merges two sorted sequences of
the same length.
7.19 Show that Batcher's sorting algorithm based on bitonic merging can be realized on an
p
-vertex hypercube by a normal algorithm in
O
(log
2
p
)
steps.
7.20 Show that Batcher's sorting algorithm based on bitonic merging can be realized on a
linear array of
n
=
2
d
cells in
O
(
n
)
steps.
7.21 Sh
o
w th
at
Batcher's sort
in
g algorithm based on bitonic merging can be realized on an
−
×
√
n
array in
O
(
√
n
)
steps.
7.22 Design an
O
(
√
n
)
-step alg
o
rith
m
to implement an arbitrary permutation of
n
items
√
n
×
√
n
mesh.
7.23 Describe a normal algorithm to realize a prefix computation on a
p
-vertex hypercube in
O
(log
p
)
steps.
placed one per cell of an
√
n
Search WWH ::
Custom Search