Change search
ReferencesLink to record
Permanent link

Direct link
The Tree Machine: An evaluation of program loading strategies
KTH, School of Computer Science and Communication (CSC), Centres, Centre for High Performance Computing, PDC. (Parallelldatorcentrum)
1983 (English)Conference paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
1983. 202-205 p.
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-65763OAI: diva2:483663
), The 1983 International Conference on Parallel Processing
NR 20140805Available from: 2012-01-25 Created: 2012-01-25Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Johnsson, Lennart
By organisation
Centre for High Performance Computing, PDC
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 9 hits
ReferencesLink to record
Permanent link

Direct link