On the area of binary tree layouts
56. R. P. Brent and
H. T. Kung,
On the area of binary tree layouts,
Information Processing Letters 11 (1980), 46-48.
Abstract:
dvi (3K),
pdf (76K).
Paper:
pdf (360K).
Abstract
The binary tree is an important interconnection pattern for VLSI
chip layouts. Suppose that the nodes are separated by at least
unit distance and that a wire has unit width. The usual layout of
a complete binary tree with n leaves takes
chip area at least of order n log n,
but it can be arranged that all the leaves are on the boundary of the chip.
In contrast, the "recursive H" layout has area of order
n, but has
only O(n1/2) leaves on the boundary.
Thus, the recursive H layout
enjoys a small area at the expense of a small number of possible I/O ports.
This paper shows that it is not possible to design a complete binary tree
layout with area O(n) and all leaves on the boundary. More precisely,
if the boundary of the chip is a convex plane curve and the leaves
on the boundary are separated by at least unit distance, then area of
order n log n
is necessary just to accomodate all the wires.
Comments
Related papers are Brent and Kung
[55, 60],
Brent and Goldschlager [64].
Go to next publication
Return to Richard Brent's index page