Efficient Embeddings of Binary Trees in VLSI Arrays
- 1 September 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-36 (9) , 1009-1018
- https://doi.org/10.1109/tc.1987.5009532
Abstract
We consider the problem of embedding a complete binary tree in squareor hexagonally-connected VLSI arrays Of processing elements (PE's). This problem can be solved in a radically different manner from current layout techniques which are aimed at laying out a given graph in the plane. The difference is due to the fact that a PE can be used both as a tree node and as a connecting element between distant nodes. New embedding schemes are presented in which (asymptotically) 100 percent of the PE's are utilized as tree nodes. This is a significant savings over known schemes, which achieve 50 percent utilization (the well-known H-tree) and 71 percent for some hexagonal schemes. These schemes also speed up signal propagation from the root to the leaves.Keywords
This publication has 16 references indexed in Scilit:
- Wafer-Scale Integration of Systolic ArraysIEEE Transactions on Computers, 1985
- NP-completeness for minimizing maximum edge length in grid embeddingsJournal of Algorithms, 1985
- Embedding Tree Structures in VLSI Hexagonal ArraysIEEE Transactions on Computers, 1984
- On Area and Yield Considerations for Fault-Tolerant VLSI Processor ArraysIEEE Transactions on Computers, 1984
- The Binary Tree as an Interconnection Network: Applications to Multiprocessor Systems and VLSIIEEE Transactions on Computers, 1981
- Universality considerations in VLSI circuitsIEEE Transactions on Computers, 1981
- A model of computation for VLSI with related complexity resultsPublished by Association for Computing Machinery (ACM) ,1981
- On the area of binary tree layoutsInformation Processing Letters, 1980
- Multidimensional Binary Search Trees in Database ApplicationsIEEE Transactions on Software Engineering, 1979
- Cost and performance of VLSI computing structuresIEEE Journal of Solid-State Circuits, 1979