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 capabilities of restructurable VLSI which allows a chip to be customized after fabrication. We 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 arbirtarily large complete binary tree. We also present a restructurable linear-areas 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 to be cut in order to bisect the tree into equal-size components, each containing exactly half the black and half the white vertices. These ideas extend to more general graphs using separator theoerems and bifurcators.