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

low complexity. For problems of higher complexity, such as n

n matrix-matrix multiplication,
we cannot achieve AT -optimality because stronger lower bounds apply. In particular, both
AT 2 and A 2 T must grow as n 4 for this problem, as we show. AT , AT 2 and A 2 T are the only
measures of VLSI performance considered in this chapter.

×

12.5 Chip Layout
In this section we describe and discuss layouts for a number of important graphs and problems.
These include balanced binary trees, multi-dimensional meshes, and the cube-connected cycle.

12.5.1 The H-Tree Layout
H-trees are embeddings of binary trees that use area efficiently. Let H k be an H-tree with 4 k
leaves. Figure 12.2 shows the H-tree H 2 with 16 darkly shaded squares that can be viewed
either as subtrees or leaves. The lightly shaded regions are internal vertices of the binary tree.
Leaves often perform special functions that are not performed by internal vertices whereas
internal vertices of a tree often perform the same function. Each quadrant of the tree shown in
Fig. 12.2 can be viewed as the H-tree H 1 on four subtrees or leaves.
The layout of H k is recursively defined as follows: replace each of the four leaves of H k− 1
with a copy of H 1 .Thus, H 2 in Fig. 12.2 is obtained by replacing each leaf in H 1 with a copy
of H 1 .
We now derive an upper bound on the area of an H-tree under the assumption that each
vertex is square, leaf vertices occupy area b 2 , and the separation between leaf vertices is c .If
S ( k ) is the length of a side of H k ,then S ( 1 )= 2 b + c . Also, from the recursive construction
of H k the following recurrence holds:

S ( k )= 2 S ( k −

1 )+ c

Figure 12.2 The H-tree H 2 containing 16 subtrees (or leaves).