How to Assemble Tree Machines.
Abstract
Many researchers have proposed that ensembles of processing elements be organized as trees. This paper explores how large tree machines can be assembled efficiently from smaller components. A principal constraint considered is the limited number of external connections from an integrated circuit chip. We also explore the emerging capability of restructurable VLSI which allows a chip to be customized after fabrication. The authors give a linear-area chip of m processors and only four off-chip connections which can be used as the sole building block to construct an arbitrarily large complete binary tree. They also present a restructurable linear-area layout of m processors with O(lg m) pins that can realize an arbitrary binary tree of any size. This layout is based on a solution to the graph-theoretic problem: Given a tree in which each vertex is either black or white, determine how many edges need be cut in order to bisect the tree into equal-size components, each containing exactly half the black and half of the white vertices. These ideas extend to more general graphs using separator theorems or bifurcators. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 24, 1984
- Accession Number
- ADA139963
Entities
People
- C. E. Leiserson
- S. N. Bhatt
Organizations
- Massachusetts Institute of Technology