Accession Number:

ADA139963

Title:

How to Assemble Tree Machines.

Descriptive Note:

Interim research,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1984-02-24

Pagination or Media Count:

22.0

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 Olg 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

Subject Categories:

  • Electrical and Electronic Equipment
  • Numerical Mathematics
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE