ON THE AREA OF BINARY TREE LAYOUTS

R. P. BRENT AND H. T. KUNG

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 Ω(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(\sqrt{n}) 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 note 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

Only the Abstract is given here. The full paper appeared as [2]. For related work, see [1, 3].

References

1. R. P. Brent and H. T. Kung, “The area-time complexity of binary multiplication”, Journal of the ACM 28 (1981), 521–534. CR 22#38242, MR 82i:68027. Corrigendum: ibid 29 (1982), 904. MR 83j:68046. rpb055.

2. R. P. Brent and H. T. Kung, “On the area of binary tree layouts”, Information Processing Letters 11 (1980), 46–48. Also appeared as Report TR-CS-79-07, Department of Computer Science, ANU (July 1979), 5 pp. rpb056.

3. R. P. Brent and L. M. Goldschlager, “Some area-time tradeoffs for VLSI”, SIAM J. on Computing 11 (1982), 737–747. MR 83k:68024. rpb064.

(Brent) Department of Computer Science, Australian National University, Canberra

(Kung) Department of Computer Science, Carnegie-Mellon University, Pittsburgh

1991 Mathematics Subject Classification. Primary 68Q35; Secondary 65Y05, 68M07, 68Q25. Key words and phrases. Chip area, area complexity, tree, layout, lower bound, VLSI. Received 27 September 1979; revised 11 April 1980. This research was supported in part by the National Science Foundation under Grant MCS 78-236-76

and the Office of Naval Research under Contracts N00014-76-C-0370 and N00014-80-C-0236. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1980, North-Holland Publishing Co. Abstract and Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb056a typeset using AMS-L^{A}TEX