A Caltech Library Service

Communication in a Tree Machine

Browning, Sally A. and Seitz, Charles L. (1981) Communication in a Tree Machine. In: Proceedings of the Second Caltech Conference on Very Large Scale Integration. California Institute of Technology , Pasadena, CA, pp. 509-526.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Communication assumes a progressively dominant and limiting role in VLSI because it becomes relatively more expensive in chip area, signal energy, and time. The principle of locality becomes alI important to integrated systems design, and implies that larger single processors are not the route to performance improvements. One computer architecture that can exploit the capabilities of VLSI is an ensemble of small processors operating concurrently. The tree machine is such a structure. Each of the many processors in the binary tree can communicate directly only with its parent and two children. However, the tree is programmed as if each processor had an arbitrary number of descendents, and the programs are compiled into code for a binary tree. We describe the communication structure of tree machine programs, the compilation process, and the underlying hardware.

Item Type:Book Section
Additional Information:The research described here was sponsored in part by the Defense Advanced Research Projects Agency, ARPA order #3771, and monitored by the Office of Naval Research under contract #NOOOI4-79-C-0597. Our starting point was a sketch of the machine presented in S. A. Browning's doctoral dissertation. A group of nine people met regularly to refine that sketch into a first implementation in silicon. Martin Rem, Lennart Johnsson, and Peggy Li made valuable contributions to the discussions of mapping problems between the notational abstraction and the machine implementation. Each potential design was examined in light of the requirements of the notation until one was found that satisfied both the programmers and the hardware designers. A compiler like the one described here is being implemented by S. A. Browning at Bell Laboratories. A tree machine processor has been designed and is being laid out by C. L. Seitz, Howard Derby, Chris Kingsley, and Chris Lutz. Erik deBenedictis and Peggy Li have written a collection of programs to evaluate the processor design.
Funding AgencyGrant Number
Defense Advanced Research Projects AgencyARPA order #3771
Office of Naval ResearchN00014-79-C-0597
Record Number:CaltechCONF:20120508-143029685
Persistent URL:
Related URLs:
URLURL TypeDescription
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:241
Deposited By: Kristin Buxton
Deposited On:09 May 2012 17:17
Last Modified:03 Oct 2019 22:50

Repository Staff Only: item control page