The Binary Tree as an Interconnection Network: Applications to Multiprocessor Systems and VLSI

1 April 1981

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-30 (4) , 247-253
https://doi.org/10.1109/tc.1981.1675772

Abstract

The binary tree is a natural way to organize complex computations by a computer. For problems that can be naturally divided into a tree structure, a great deal of parallelism may be employed. In this paper we examine several aspects of the binary tree structure as it relates to both multiprocessor systems and to VISI circuit design. First, we present an algorithm for mapping an arbitrary binary tree onto the plane. An analysis shows the density of this mapping. Second, we consider the problem of routing messages within a binary tree under the assumption that certain nodes may be faulty. Finally, we analyze the binary tree's capacity to transfer information between nodes and we compare it to the capacity of the linear array and the grid.

Keywords

This publication has 4 references indexed in Scilit:

Multidimensional Binary Search Trees in Database Applications
IEEE Transactions on Software Engineering, 1979
Simulation experiments of a tree organized multicomputer
Published by Association for Computing Machinery (ACM) ,1979
Can programming be liberated from the von Neumann style?
Communications of the ACM, 1978
X-Tree
Published by Association for Computing Machinery (ACM) ,1978