Accession Number : ADA139963

Title :   How to Assemble Tree Machines.

Descriptive Note : Interim research,


Personal Author(s) : Bhatt,S N ; Leiserson,C E

PDF Url : ADA139963

Report Date : 24 Feb 1984

Pagination or Media Count : 22

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)

Descriptors :   *Chips(Electronics), *Multiprocessors, *Assembly, *Trees, *Packaging, Integrated circuits, Bifurcation(Mathematics), Graphs, Circuit interconnections, Fabrication, Separators, Theorems

Subject Categories : Electrical and Electronic Equipment
      Numerical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE