Patent Document ID: 5485612
Application ID: 07830673
Patent Flag: 1

Claim One:
1. In a computer system comprising a plurality of processors each having a local memory, a method of assigning said plurality of processors to execute in parallel a plurality of operations for an expression represented by a plurality of operands stored in said local memories and said plurality of operations, said method comprising the steps of: (a) representing said expression in a form of a tree having a plurality of leaf nodes and a plurality of interior nodes, said operands being assigned to said leaf nodes, and said operations being assigned to said interior nodes, and assigning a processor having a local memory which stores an operand represented by a leaf node to said leaf node; (b) tracing said tree in a bottom-up fashion for determining a set of candidate processors to be assigned to each of said plurality of interior nodes for executing an operation assigned to each of said plurality of interior nodes, from a set of processors which are assigned to children nodes of said each interior node in accordance with a majority method, said majority method being based on a rule that a processor which is most frequently assigned to the children nodes of said each interior node is determined as a candidate processor; (c) determining definitively a root processor to be assigned to a root node of said interior nodes of said tree by arbitrarily selecting one of the candidate processors determined for said root node when a plurality of candidate processors are determined for said root node in the above step (b); and (d) tracing said tree in a top-down fashion to determine definitively one of the candidate processors determined for each of the interior nodes as a determined processor to be assigned to execute the operation at each of said interior nodes (i) when a processor assigned to a parent node of said each interior node is contained in the set of candidate processors of said each interior node, the processor assigned to said parent node is selected as the processor to be assigned to said each interior node; and (ii) when the processor assigned to the parent node of said each interior node is not contained in the set of the candidate processors of said each interior node, a one processor of the set of candidate processors of said each interior node is arbitrarily selected to be definitively assigned to said each interior node.