Browse Prior Art Database

THE TREE MACHINE AN EVALUATION OF STRATEGIES FOR REDUCING PROGRAM LOADING TIME

IP.com Disclosure Number: IPCOM000147851D
Original Publication Date: 1983-May-23
Included in the Prior Art Database: 2007-Mar-28
Document File: 28 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Li, Pey-yun Peggi: AUTHOR [+3]

Abstract

THE TREE MACHINE AN EVALUATION OF STRATEGIES

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 28

THE TREE MACHINE

  AN EVALUATION OF STRATEGIES
FOR REDUCING PROGRAM LOADING TIME

Pey-yun Peggy Li
and

Lennart Johnsson

       Computer Science
California Institute of Technology
Pasadena CA 91125

23 May 1983

              To be presented at
1983 International Conference on Parallel Processing
Bellaire, Michigan
August 23-26, 1983

   The research in this report was sponsored in part
by an IBM Predoctoral Fellowship,
the Systems Development Foundation,
and the Defense Advanced Research Agency, ARPA order 3771,
monitored by the Office of Naval Research
under contract N00014-79C-0597

California Institute of Technology

[This page contains 1 picture or other non-text object]

Page 2 of 28

[This page contains 1 picture or other non-text object]

Page 3 of 28

THE TREE MACHINE

AN EVALUATION OF STRATEGIES FOR REDUCING PROGRAM LOADING TIME

Pey-yun Peggy Li and Lennart Johnsson

Computer Science

California Institute of Technology
Pasadena, CA, 91125

23 May 1983

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 i n devising loading strategies to make the loading t i m e 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 i n 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 i n many cases with the algorithms presented. This t i m e is also the worst case performance for one of the al orithms. The other algorithms have a worst case performance of O(&) and 0(bJl/lo~2f), 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.

INTRODUCTION

  The Caltech Tree Machine has an ensemble architecture, [Seitz 821, with processors interconnected as a binary tree. Each node is a complete, alchough small, von Neumann machine that can execute its own program. Synchronization is made by message passing. Hence, the Caltech Tree Xachine is significantly different from other tree machine projects such as reported in [Mago 801 and [Shaw 821. A common idea is to keep the processors small i n exchange for...