Information Technology Reference
In-Depth Information
n
matrix multiplication that achieves
AT
2
=
n
4
log
2
n
for
12.14 Design a VLSI chip for
n
×
T
=
O
(log
n
)
.
Hint:
Represent each matrix as a 2
(
n/
2
)
matrices and use the
standard algorithm that performs eight multiplications of
(
n/
2
)
×
2matrixof
(
n/
2
)
×
(
n/
2
)
matrices. A
multiplier has one side longer than the other. Place the long side of the
(
n/
2
)
×
×
(
n/
2
)
matrix multiplier at right angles to the long side of the
n
×
n
matrix multiplier. Apply
this rule to the recursive construction of the multiplier.
12.15 Show that an algorithm of the kind described in Problem
12.14
can be combined with
a mesh-based matrix multiplication algorithm of the kind described in Section
7.5.3
to
produce a family of algorithms that achieve the lower bound on
n
×
n
matrix multipli-
n
.
12.16 Devise a VLSI chip for
n
-bit integer multiplication function chip that uses area
A
and
time
T
efficiently.
Hint:
Let
x
and
y
denote binary numbers. Recursively form the product of these
integers as the sum of two products, that of
x
with the high-order
(
n/
2
)
bits of
y
and
that of
x
with the low-order
(
n/
2
)
bits of
y
. Use carry-save addition where possible.
12.17 Give a proof of Theorem
12.7.4
.
12.18 Show that the characteristic predicate of a function that has a
w
(
u
,
v
)
-flow is
w
(
u
,
v
)
-
separated.
cation for
Ω(log
n
)
≤
T
≤
AREA BOUNDS
12.19 Show that any VLSI algorithm that realizes a superconcentrator on
n
inputs requires
area
Θ(
n
)
.
Chapter Notes
Mead and Conway wrote an influential topic [
213
] that greatly simplified the design rules for
VLSI chips and made VLSI design accessible to a large audience. Ullman [
339
] summarized
the status of the field around 1984 and Lengauer [
193
] addressed the VLSI layout problem.
Lengauer has also written a survey paper [
194
] that provides an overview of the theory of VLSI
algorithms as of about 1990. The three transmission models described in Section
12.2
reflect
the analysis of Zhou, Preparata, and Khang [
372
].
Thompson [
326
] obtained the first important tradeoff results for the VLSI model of com-
putation. He demonstrated that under a suitable model a lower bound of
AT
2
=Ω(
n
2
)
could be derived for the discrete Fourier transform, a result he subsequently extended to sort-
ing [
327
]. Generalizations of this model were made to convex chips [
59
], compact plane
regions [
195
], and other closely related models [
202
]. Vuillemin [
355
] extended the models
to include pipelining. Chazelle and Monier [
67
] introduced the transmission-line model de-
scribed in Problems
12.1
and
12.2
. For a discussion of other models that take into account the
effects of distributed resistance, capacitance and inductance, see [
40
]and[
372
].
Systolic algorithms, which make good use of area and time, were popularized by Kung
[
177
] and others (see, for example, [
104
,
122
,179,
180
,181,
190
]). The H-tree featured in Sec-
tion
12.5.1
is due to Mead and Rem [
214
]. Prefix computations are discussed in Chapter
2
.
The cube-connected cycles network (its layout is given in Section
12.5.3
)andtheefficient
Search WWH ::
Custom Search