A Caltech Library Service

The Tree Machine: An Evaluation of Strategies For Reducing Program Loading Time

Li, Pey-yun Peggy and Johnsson, Lennart (1983) The Tree Machine: An Evaluation of Strategies For Reducing Program Loading Time. California Institute of Technology . (Unpublished)

Other (Adobe PDF (2MB))
See Usage Policy.

See Usage Policy.


Use this Persistent URL to link to this item:


The Caltech Tree Machine has an ensemble architecture, Processors are interconnected into a binary tree. Each node executes its own code. No two nodes need to execute identical code. Nodes are synchronized by messages between adjacent nodes. Since the number of nodes is intended to be large, in the order of thousands, great care needs to be exercised in devising loading strategies to make the loading time as short as possible. A constraint is also imposed by the very limited storage associated with a processor. Nodes are assigned a type that identifies the code it shall execute. Nodes of the same type execute identical code. Tree Machine programs are frequently very regular. By exploiting this regularity, compact descriptions of the types of all nodes in the tree can be created. The limited storage of a node, and the desire to only use local information in the expansion of the compacted description implies constraints on the compression/decompression algorithms. A loading time proportional to the height of the tree is attainable in many cases with the algorithms presented. This time is also the worst case performance for one of the algorithms. The other algorithms have a worst case performance of 0 square root of N/f and O square root of (N to the power of 1/log2f), where N is the total number of nodes in a tree with fanout f. The algorithms with a less favorable upper bound, in some cases allow a more compact tree description, than the algorithm with the best upper bound.

Item Type:Report or Paper (Technical Report)
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1983.5084-tr-83
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:27010
Deposited By: Imported from CaltechCSTR
Deposited On:09 Aug 2002
Last Modified:03 Oct 2019 03:20

Repository Staff Only: item control page