Boosting method and apparatus in a parallel computer

Claim 1

A parallel computer comprising: means for executing instructions organized in basic blocks, each basic block including a plurality of linear instructions, each linear instruction providing only one result upon execution, each basic block ending in a branch instruction having two alternative results and selecting one of the alternative results upon execution of the branch instruction, wherein the basic blocks are arranged in sequential order of a precedent basic block and corresponding subsequent basic blocks for sequential execution, each branch instruction of a precedent basic block supplying, upon execution, one of the alternative results to the respective one of the corresponding subsequent basic blocks; means for moving the linear instructions of two corresponding subsequent basic blocks, in the sequential order, for parallel rather than sequential execution with linear instructions of the precedent basic block; a data bus for communicating data; a bypass control circuit for outputting a control signal and indicating whether data on the data bus is used; and data selecting means for selecting data in accordance with the control signal.

Claim 3

A method of boosting in a parallel computer programmed to execute instructions organized in basic blocks, each basic block including a plurality of linear instructions, each linear instruction providing only one result upon execution, each basic block ending in a branch instruction having two alternative results and selecting one of the alternative results upon execution of the branch instruction, the basic blocks being arranged in sequential order including a precedent basic block and corresponding subsequent basic blocks for sequential execution, each branch instruction of a precedent basic block supplying, upon execution, one of the alternative results to the respective one of the corresponding subsequent basic blocks, the method comprising: moving the linear instructions of the two corresponding subsequent basic blocks, in the sequential order, for parallel rather than sequential execution with the linear instructions of the precedent basic block; adding an identifier to each moved linear instruction identifying the respective subsequent basic block from which the linear instructions was moved; limiting the number of moved linear instructions, wherein execution of the moved linear instructions is completed not later than execution of the branch instruction in the precedent basic block since the alternative result selected by execution of the branch instruction of the precedent basic block is determined before any result of execution of the moved linear instructions is determined, whereby no memory is required for storing the result of execution of the moved linear instructions until the result of execution of the branch instruction of the precedent basic block is determined.

Claim 4

A method of boosting in a parallel computer programmed to execute instructions organized in basic blocks, each basic block including a plurality of linear instructions, each linear instruction providing only one result upon execution, each basic block ending in a branch instruction having two alternative results and selecting one of the alternative results upon execution of the branch instruction, the basic blocks being arranged in sequential order including a precedent basic block and corresponding subsequent basic blocks for sequential execution, each branch instruction of a precedent basic block supplying, upon execution, one of the alternative results to the respective one of the corresponding subsequent basic blocks, the method comprising: moving the linear instructions of the two corresponding subsequent basic blocks, in the sequential order, for parallel rather than sequential execution with the linear instructions of the precedent basic block; adding an identifier to each moved linear instruction identifying the respective subsequent basic block from which the linear instructions was moved; limiting the number of moved linear instructions, wherein execution of the moved linear instructions is completed not later than execution of the branch instruction in the precedent basic block since the alternative result selected by execution of the branch instruction of the precedent basic block is determined before any result of execution of the moved linear instructions is determined, whereby no memory is required for storing the result of execution of the moved linear instructions until the result of execution of the branch instruction of the precedent basic block is determined.