
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) : 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 lineararea chip of m processors and only four offchip connections which can be used as the sole building block to construct an arbitrarily large complete binary tree. They also present a restructurable lineararea 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 graphtheoretic 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 equalsize 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