The semantic and syntactic manipulation of vacancies in associative binary trees

Abstract

Execution of sub-processes within a program segment are subject to a partial ordering. In certain cases (such as expressions and assignment statements) this ordering reduces to a tree which, according to the characteristics of the operators present, may be manipulated to influence the extent to which parallel processing capabilities of multiple-processor configurations can be utilized in its evaluation. A strategy is presented which uses associativity of certain operators to adjust the shape of the trees to allow a degree of overlap between adjacent subtrees. Although only optimal in the local sense, the transformation yields significant improvements in the “parallel dimensions” of the tree and, more importantly, can be couched in syntactic terms. Consequently, it is possible in principle to perform these manipulations within the syntax analysis phase of compilation, regardless of other operational characteristics of the operators, or of the parallel capabilities of the target run-time system.

Keywords:

• Binary tree
• vacancy
• tree height
• insertion
• balanced tree

C.R. Categories::

• 5.23
• 5.24