The Tree Machine: A Highly Concurrent Computing Environment

Creators: Browning, Sally A.

Abstract

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.

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.

Attached Files

Submitted - 3760-TR-80.pdf

Files

3760-TR-80.pdf

Files (8.3 MB)

Name	Size	Download all
3760-TR-80.pdf md5:718fe976861c52bb40eea8601151a327	8.3 MB	Preview Download

Additional details

	All versions	This version
Views	0	0
Downloads	0	0
Data volume	0 Bytes	0 Bytes