How to assemble tree machines

Sandcep N. Bhatt, Charles R. Leiserson

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

24 Scopus citations

Abstract

Many researchers have proposed that ensembles of processing elements be organized as trees. This paper ex-I lores how large tree machines may be assembled efficiently from smaller components. A principal constraint that we consider 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. 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 arbitrarily large complete binary tree. We also present a restructurable linear-area layout of m processors with O(lg m) pins that can realize an arbitrary binary tree. This layout is based on a solution to the graph-theoretic problem: Given a tree in which each vertex is either black or white, determinc how many edges need be cut in order to bisect the tree into equal-size components, each containing exactly half the black and half the white vertices.

Original languageEnglish
Title of host publicationProceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982
Pages77-84
Number of pages8
DOIs
StatePublished - 5 May 1982
Event14th Annual ACM Symposium on Theory of Computing, STOC 1982 - San Francisco, United States
Duration: 5 May 19827 May 1982

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference14th Annual ACM Symposium on Theory of Computing, STOC 1982
Country/TerritoryUnited States
CitySan Francisco
Period5/05/827/05/82

Fingerprint

Dive into the research topics of 'How to assemble tree machines'. Together they form a unique fingerprint.

Cite this