Information Technology Reference
In-Depth Information
bound. Turan [
337
] exhibits a function and a predicate with
Ω(
n
3
/
2
log
n
)
and
Ω(
n
log
n
)
lower bounds to their multilective planar circuit size, respectively. The
w
(
u
,
v
)
-flow and
w
(
u
,
v
)
-separated properties used in Section
12.7
were introduced in [
291
].
Lower bounds on the area of chips have been explored by a number of authors. Yao [
367
]
examined addition; Baudet [
30
] studied functions that do not have a large information flow;
Heintz [
131
] derived bounds for matrix-matrix multiplication; Leighton [
191
] introduced and
used the crossing number of a graph to derive area bounds; Siegel [
309
] derived bounds for
sorting; and Savage [
288
] examined functions with many subfunctions. Bilardi and Preparata
[
42
] have generalized arguments of [
30
]and[
152
]toderivestrongerarea-timelowerbounds
for functions, such as prefix, for which the information flow arguments give weak results.
Lower bounds on the area of multilective chips were obtained by Savage [
291
], Hromkovic
[
142
,
143
], and DuriˇsandGalil[
93
].
Models for 3D VLSI chips, which are not yet a reality, have been introduced by Rosenberg
[
282
,
283
]andstudiedbyPreparata[
263
].
Search WWH ::
Custom Search