TY - GEN
T1 - How to assemble tree machines
AU - Bhatt, Sandcep N.
AU - Leiserson, Charles R.
N1 - Publisher Copyright:
© 1982 ACM.
PY - 1982/5/5
Y1 - 1982/5/5
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84990686641&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84990686641&partnerID=8YFLogxK
U2 - 10.1145/800070.802179
DO - 10.1145/800070.802179
M3 - Conference contribution
AN - SCOPUS:84990686641
SN - 0897910702
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 77
EP - 84
BT - Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982
T2 - 14th Annual ACM Symposium on Theory of Computing, STOC 1982
Y2 - 5 May 1982 through 7 May 1982
ER -