System and method for optimizing and generating computer-based code in a parallel processing environment
AssigneeThinking Machines Corporation
InventorsGary W. Sabot, David F. Lively, Alexander D. Vasilevsky
Life of this patent
Estimating the term…
Abstract
A system and method for optimizing statements to produce more efficient assembly language for use in a parallel processing environment. In doing this, the present invention separates elemental from non-elemental nodes in a statement, encapsulates the elemental statements, and generates a parallel assembly language code stream from encapsulated statements, and a scalar code stream from scalar statements and non-elemental nodes (for which the scalar assembly language is used to utilize a non-elemental resolver).
Claims19
A computer-based method of optimizing a computer program to generate an optimized computer program, the optimized computer program to be executed in a data parallel computer comprising a plurality of processors, the computer program represented by at least one representation tree comprising a plurality of nodes, said nodes comprising non-elemental nodes which require communication among processors and elemental nodes which do not require communication among processors, the method comprising the steps of:
- (1) traversing to a node of the representation tree using a predetermined traversal sequence;
- (2) determining whether said node requires communication among processors and is therefore a non-elemental node;
- and
- (3) in response to said determination, restructuring said nodes within said representation tree such that said node is grouped with other non-elemental nodes.
A computer-based method for optimizing a computer program to generate an optimized computer program, the optimized computer program to be executed in a data parallel computer comprising a plurality of processors, the computer program comprising a plurality of non-elemental statements which require communication among processors and elemental statements which do not require communication among processors, the method comprising the steps of:
- (1) classifying each of said statements as elemental or non-elemental;
- (2) identifying a block of two or more contiguous statements each having been classified as elemental;
- and
- (3) creating a block identifier and associating said block identifier with said identified block, such that said identified block is subsequently compliable as a single statement.
A computer-based method for optimizing a computer program to generate an optimized computer program, the optimized computer program to be executed in a computer comprising a scalar portion, a parallel portion, and an intermediary memory accessible by both the scalar portion and the parallel portion, the computer program comprising a contiguous block of elemental statements which do not require communication among processors in the parallel portion, said elemental statements represented by representation trees each comprising a plurality of nodes, the method comprising the steps of:
- (1) traversing to a node in one of the representation trees using a predetermined traversal sequence;
- (2) determining whether said node is a variable;
- and
- (3) creating, if said node is a variable, a store instruction node and a corresponding retrieve instruction node, wherein said store instruction node when executed in the computer enables the scalar portion to store a value of said variable in the intermediary memory, and said retrieve instruction node when executed in the computer enables the parallel portion to retrieve said value of said variable from said intermediary memory.
A method of generating a target computer program from a source computer program, the target computer program to be executed in a processor array comprising a plurality of processors, the source computer program including a plurality of instructions each represented by a representation tree having a plurality of nodes, each node being a non-elemental node involving communication among processors or an elemental node not involving communication among processors, said method comprising the steps of:
- (1) determining whether an instruction exists in the source computer program wherein the instruction, when executed in at least one of said processors of the processor array, enables said at least one of said processors to process elements of an array, wherein said array elements comprise local array elements maintained by each of said at least one of said processors during execution of the target computer program, and non-local array elements which are maintained by other processors of the processor array during execution of the target computer program;
- (2) selecting said instruction in response to said determination;
- (3) determining whether said selected instruction includes at least one non-elemental node;
- (4) identifying, in response to said determination, whether all non-elemental nodes of said selected instruction satisfy predetermined communication characteristics;
- (5) transforming, in response to said identification, said selected instruction to a plurality of lower intermediate representation (LIR) instructions, comprising the steps of
- (a) generating one or more LIR instructions which, when executed in the processor array, enable the transfer of said non-local array elements from said other processors to said at least one of said processors,
- (b) generating one or more LIR instructions which, when executed in said at least one of said processors, enable said at least one of said processors to process said local and non-local array elements, and
- (c) storing said generated LIR instructions in the target computer program.
Dependencies are inferred from the claim text.