System and method for multilevel promotion

Claim 2

A computer implemented method for generating a target program from a source program, the source program written using a high level language supporting data parallel processing, the target program adapted for use in a data parallel computer, said computer implemented method comprising the steps of: (1) locating in said source program a parallel instruction requiring performance of a type conversion operation involving a base type and a target type and a promotion operation; (2) calculating a first run-time cost resulting from executing code generated by compiling said promotion operation, followed by executing code generated by compiling said type conversion operation; (3) calculating a second run-time cost resulting from executing code generated by compiling said type conversion operation, followed by executing code generated by compiling said promotion operation; and (4) compiling said type conversion operation and said promotion operation to be executed in an order selected according to said first and second run-time costs to thereby generate the target program, such that an actual run-time cost of executing said compiled conversion and promotion operations is minimized.

Claim 3

The method of claim 1 in which the data parallel computer comprises a plurality of nodes for processing data in parallel, wherein step (2) comprises the steps of: (a) estimating a third run-time cost of executing a compiled instruction to transmit a value of the base type to the nodes of the data parallel computer; (b) estimating a fourth run-time cost of executing a compiled instruction to convert, in the nodes of the data parallel computer, a value from the base type to the target type; and (c) generating said first run-time cost as a function of said third and fourth run-time costs.

Claim 4

The method of claim 1 in which the data parallel computer comprises a plurality of nodes for processing data in parallel, wherein step (3) comprises the steps of: (a) estimating a third run-time cost of executing a compiled instruction to convert, in a scalar computer, a value from the base type to the target type; (b) estimating a fourth run-time cost of executing a compiled instruction to transmit a value of the target type to the nodes of the data parallel computer; and (c) generating said second run-time cost as a function of said third and fourth run-time costs.

Claim 5

The method of claim 1, wherein step (4) comprises the steps of: compiling said promotion operation and said type conversion operation such that said compiled promotion operation is executed before said compiled type conversion operation if said first run-time cost is less than said second run-time cost; and compiling said promotion operation and said type conversion operation such that said compiled type conversion operation is executed before said compiled promotion operation if said first run-time cost is greater than said second run-time cost.

Claim 6

A computer implemented method for generating a target program from a source program, the source program written using a high level language supporting data parallel processing, the target program adapted for use in a data parallel computer, said computer implemented method comprising the steps of: (1) empirically determining whether code generated in accordance with a first compilation method, wherein a promotion operation is compiled to be executed before a type conversion operation, is more run-time efficient than code generated in accordance with a second compilation method, wherein a type conversion operation is compiled to be executed before a promotion operation; (2) selecting said first compilation method if code generated in accordance with said first compilation method is more run-time efficient than code generated in accordance with said second compilation method as indicated by said empirical determination, and selecting said second compilation method if code generated in accordance with said second compilation method is more run-time efficient than code generated in accordance with said first compilation method as indicated by said empirical determination; (3) locating in said source program a parallel instruction requiring performance of a type conversion operation and a promotion operation; and (4) compiling said located parallel instruction in accordance with said selected compilation method to thereby generate the target program.

Claim 7

A computer implemented method for generating a target program from a source program, the source program written using a high level language supporting data parallel processing, the target program adapted for use in a data parallel computer, said computer implemented method comprising the steps of: (1) empirically determining whether code generated in accordance with a first compilation method, wherein a promotion operation is compiled to be executed before a type conversion operation, is more run-time efficient than code generated in accordance with a second compilation method, wherein a type conversion operation is compiled to be executed before a promotion operation; (2) selecting said first compilation method if code generated in accordance with said first compilation method is more run-time efficient than code generated in accordance with said second compilation method as indicated by said empirical determination, and selecting said second compilation method if code generated in accordance with said second compilation method is more run-time efficient than code generated in accordance with said first compilation method as indicated by said empirical determination; (3) locating in said source program a parallel instruction requiring performance of a type conversion operation and a promotion operation; and (4) compiling said located parallel instruction in accordance with said selected compilation method to thereby generate the target program.

Claim 8

The method of claim 5, wherein step (2) comprises the step of selecting said first compilation method.

Claim 9

The method of claim 5, wherein step (2) comprises the step of selecting said second compilation method.

Claim 12

The apparatus of claim 8 in which the data parallel computer comprises a plurality of nodes for processing data in parallel, said first run-time cost calculating means comprising: means for estimating a third run-time cost of executing a compiled instruction to transmit a value of the base type to the nodes of the data parallel computer; means for estimating a fourth run-time cost of executing a compiled instruction to convert, in the nodes of the data parallel computer, a value from the base type to the target type; and means for generating said first run-time cost as a function of said third run-time cost and said fourth run-time cost.

Claim 13

The apparatus of claim 8 in which the data parallel computer comprises a plurality of nodes for processing data in parallel, wherein said second run-time cost calculating means comprises: means for estimating a third run-time cost of executing a compiled instruction to convert, in a scalar computer, a value from the base type to the target type; means for estimating a fourth run-time cost of executing a compiled instruction to transmit a value of the target type to the nodes of the data parallel computer; and means for generating said second run-time cost as a function of said third run-time cost and said fourth run-time cost.

Claim 14

The apparatus of claim 8, wherein said compiling means comprises: means for compiling said promotion operation and said type conversion operation such that said compiled promotion operation is executed before said compiled type conversion operation if said first run-time cost is less than said second run-time cost; and means for compiling said promotion operation and said type conversion operation such that said compiled type conversion operation is executed before said compiled promotion operation if said first run-time cost is greater than said second run-time cost.

Claim 19

A control subsystem arrangement for controlling a computer to generate a target program from a source program, the source program written using a high level language supporting data parallel processing, the target program adapted for use in a data parallel computer, said control subsystem arrangement comprising: a parser for enabling the computer to locate in said source program a parallel instruction requiring performance of a type conversion operation involving a base type and a target type and a promotion operation; first run-time cost calculating means for enabling the computer to calculate a first run-time cost resulting from executing code generated by compiling said promotion operation, followed by executing code generated by compiling said type conversion operation; second run-time cost calculating means for enabling the computer to calculate a second run-time cost resulting from executing code generated by compiling said type conversion operation, followed by executing code generated by compiling said promotion operation; and compiling means for enabling the computer to compile said type conversion operation and said promotion operation to be executed in an order selected according to said first and second run-time costs to thereby generate the target program, such that an actual run-time cost of executing said compiled conversion and promotion operations is minimized.

Claim 20

A control subsystem arrangement for controlling a computer to generate a target program from a source program, the source program written using a high level language supporting data parallel processing, the target program adapted for use in a data parallel computer, said control subsystem arrangement comprising: a parser for enabling the computer to locate in said source program a parallel instruction requiring performance of a type conversion operation involving a base type and a target type and a promotion operation; first run-time cost calculating means for enabling the computer to calculate a first run-time cost resulting from executing code generated by compiling said promotion operation, followed by executing code generated by compiling said type conversion operation; second run-time cost calculating means for enabling the computer to calculate a second run-time cost resulting from executing code generated by compiling said type conversion operation, followed by executing code generated by compiling said promotion operation; and compiling means for enabling the computer to compile said type conversion operation and said promotion operation to be executed in an order selected according to said first and second run-time costs to thereby generate the target program, such that an actual run-time cost of executing said compiled conversion and promotion operations is minimized.