hide
Free keywords:
-
Abstract:
We establish a lower bound on the efficiency of rea--universal circuits. The
area A u of every graph H that can host any graph G of area (at most) A with
dilation d, and congestion c p A= log log A satisfies the tradeoff A u =
OmegaGamma A log A=(c 2 log(2d))): In particular, if A u = O(A) then max(c; d)
= OmegaGamma p log A= log log A). 1 Introduction Bay and Bilardi [2] showed
that there is a graph H which can be laid out in area O(A) and into which any
graph G of area at most A can be embedded with load 1, and dilation and
congestion O(log A). As a consequence, they showed the existence of an area
O(A) VLSI circuit that can simulate any area A circuit with a slowdown of O(log
A). This note explores the feasibility of more efficient embeddings. Our main
result is Theorem 5 which establishes a limitation relating the area of a
universal graph to the parameters of the embedding. Informally, it asserts that
any circuit which is universal for a family of graphs of area A, a...
