VLSI Models of Computation - Models of Computation: Exploring the Power of Computing - page 599

CHIP LAYOUT

12.3 Show that every layout of a balanced binary tree on n leaves in which the root and the
leaves are placed on the boundary of a convex region has area proportional to n log n .
Hint: Consider an inscribed quadrilateral defined by the longest chord and a chord
perpendicular to it.
12.4 The n

n mesh-of-trees network, n = 2 r , is described in Problem 7.4 .Giveanarea-
efficient layout for an arbitrary graph in this family of graphs and derive an expression
for its area.
12.5 Let n = 2 k . As suggested in Fig. 12.9 ,the n

×

n tree of meshes T n is a binary tree
in which each vertex is a mesh and the meshes are decreasing in size with distance from
the root. The edges between vertices are bundles of parallel wires. The root vertex is
an n

×

× n mesh, its immediate descendants are n/ 2 × n meshes, and their immediate

descendants are n/ 2 × n/ 2 descendants, and so on.

The depth- d , n n mesh of trees, T n , d ,is T n that has been truncated to vertices at

distance d or less from the root.
Determine the area of an area-efficient layout of the tree T n , d .

×

COMPUTATIONAL INEQUALITIES

12.6 Use the results of Problem 12.11 to extend Theorem 12.7.1 to multilective planar
circuits of order μ .
12.7 Further extend the results of Problem 12.6 to ( β , μ ) -multilective VLSI algorithms by
showing that, at the expense of a small increase in AT 2 and A 2 T , multiple inputs of a
variable at the same I/O port can be treated as a single input, thereby possibly reducing
the multilective order of the corresponding planar circuit. This implies that if multiple
copies of each variable are read at a single port, then the semellective planar circuit size
is a lower bound to both AT 2 and A 2 T .

Figure 12.9 The 4 ×

4treeofmeshes, T 4 .