A Caltech Library Service

The Tree Machine: A Highly Concurrent Computing Environment

Browning, Sally A. (1980) The Tree Machine: A Highly Concurrent Computing Environment. Computer Science Technical Reports, 1980.3760. California Institute of Technology , Pasadena, CA. (Unpublished)

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


An architecture for a VLSI multiprocessor machine is proposed. The processors are connected together as a binary tree. A collection of algorithms are mapped onto the tree machine. These include heap sort, transitive closure, the travelling salesman, and matrix inversion, among others. A model of computational complexity for the tree machine is suggested, and the algorithms are analyzed in the context of that model. A notation for expressing the algorithms is described, a processor design is proposed, and a compiler for the notation and processor is presented.

Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription ItemCaltech PhD thesis
Additional Information:© 1980 California Institute of Technology. The Computer Science Department at Caltech provides a marvelous backdrop for learning how to do research. The faculty's unconventional approach to Computer Science is hard to resist. Two faculty members deserve special thanks. Carver Mead and I have maintained a dialog about Oregon and about software systems since my first week at Caltech. He proposed the tree machine as o potentially interesting concurrent programming environment suited to VLSI. That proposal led to the research described here. Martin Rem not only influenced the development of the tree machine notation, but was instrumental in constraining the scope of the research to a managable set of questions. His return to Holland in 1978 provided me with on excuse to see a lot or Europe while consulting him about tree machines. Three of my fellow students hove also contributed to this research. Bart Locanthi provided insights into the maze of numerical analysis algorithms and suggested improvements to the processor instruction set. Jim Rowson and Mike Ullner not only were involved in the design of many of the algorithms included here, but also had the fortitude to read and correct this document. Many thanks. During my first two years at Caltech, I was supported by a predoctoral fellowship from the International Business machines Corporation. My research has been partially supported by the Defense Advanced Research Projects Agency under contracts #N00123-78-C-0806 and #N00014-79-C-0597.
Group:Computer Science Technical Reports
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)3771
Office of Naval Research (ONR)N00123-78-C-0806
Office of Naval Research (ONR)N00014-79-C-0597
Series Name:Computer Science Technical Reports
Issue or Number:1980.3760
Record Number:CaltechCSTR:3760-tr-80
Persistent URL:
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26932
Deposited By: Imported from CaltechCSTR
Deposited On:10 Jul 2002
Last Modified:03 Oct 2019 03:19

Repository Staff Only: item control page