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

Abstract

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.