## 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(*n*^{1/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