Compiler-generated invocation stubs for data parallel programming model

• US 8,589,867 B2
• Filed: 06/18/2010
• Issued: 11/19/2013
• Est. Priority Date: 06/18/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Lingli, Zhu, Weirong, Levanoni, Yosseff, Ringseth, Paul F., Callahan, Charles David II
• Primary Examiner(s): Nguyen, Phillip H
• Application Number:
  US12/819,108
• Publication Number:
  US 20110314444A1
• Time in Patent Office: 1,250 Days
• Field of Search: 717/119, 717/108, 717/157
• US Class Current: 717/106
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

Described herein are techniques for generating invocation stubs for a data parallel programming model so that a data parallel program written in a statically-compiled high-level programming language may be more declarative, reusable, and portable than traditional approaches. With some of the described techniques, invocation stubs are generated by a compiler and those stubs bridge a logical arrangement of data parallel computations to the actual physical arrangement of a target data parallel hardware for that data parallel computation.

Claims

1. A method comprising:

obtaining a representation of a call for a data parallel (DP) function, wherein the representation includes indicators of arguments associated with the call for the DP function;

generating an invocation stub, based at least in part upon the representation and the associated arguments, the invocation stub including computer executable instructions that bridge a logical arrangement of DP computations of the DP function to a physical arrangement of DP computations to be performed on DP hardware of one or more computing devices by calculating logic indices of each DP activity based on physical thread indices and a logical compute domain.

2. A method as recited in claim 1, wherein the generating comprises determining a physical location in the DP hardware where the DP computations will occur for the logical arrangement of the DP computations.

3. A method as recited in claim 1, wherein the generating comprises setting up a field for the DP function with target-dependent resources, wherein the field is a data set to be operated upon by the DP computations of the DP function.

4. A method as recited in claim 1, wherein the generating comprises setting up a field for the DP function with target-dependent resources, wherein the field comprises a data set to be operated upon by the DP computations of the DP function and wherein the setting up includes examining the arguments associated with the DP function and configuring the data set based upon the examining.

5. A method as recited in claim 1, wherein the generating comprises setting up a field for the DP function with target-dependent resources, wherein the field comprises a data set operated upon by the DP computations of the DP function and wherein the setting up includes declaring how many threads inside a thread group are to be deployed in multiple dimensions.

6. A method as recited in claim 1, wherein the generating comprises setting up a field for the DP function with target-dependent resources, wherein the field comprises a data set operated upon by the DP computations of the DP function and wherein the setting up includes mapping of a thread position of the DP hardware to a logical DP activity position in the logical arrangement of the DP computation.

7. A method as recited in claim 1, wherein the generating comprises setting up a field for the DP function with target-dependent resources, wherein the field comprises a data set operated upon by the DP computations of the DP function and wherein the setting up includes mapping of a thread position of the DP hardware to a logical DP activity position in the logical arrangement of the DP computation, the mapping including transformation index flattening and index raising.

8. A method as recited in claim 1, wherein the generating comprises preparing parameters of a kernel based upon what the kernel expects, the kernel being a unit DP computation of the DP function.

9. A method as recited in claim 1, wherein the generating comprises preparing parameters of a kernel based upon what the kernel expects, the kernel being a unit DP computation of the DP function, wherein the preparing includes:

determining whether the associated arguments include one or more special indices;

in response to the determining, creating index instances based upon a type of one or more special indices.

10. A method as recited in claim 1, wherein the generating comprises preparing parameters of a kernel based upon what the kernel expects, the kernel being a unit DP computation of the DP function, wherein the preparing includes:

determining whether the associated arguments match actual parameters of the kernel;

in response to the determining, broadcasting a value for the kernel to use.

11. A method as recited in claim 1, wherein the generating comprises preparing parameters of a kernel based upon what the kernel expects, the kernel being a unit DP computation of the DP function, wherein the preparing includes:

determining whether the associated arguments match actual parameters;

in response to the determining, projecting a field, wherein the field is a data set operated upon by the DP computations of the DP function.

12. A method as recited in claim 1, further comprising outputting the invocation stub into a memory.

13. A method as recited in claim 1, the DP hardware being capable of performing DP computations and the logical arrangement of the DP computations being defined, at least in part, by the representation of the call for the DP function with its associated arguments.

14. One or more computer-readable storage devices storing computer-executable instructions that, when executed, cause one or more computer to perform operations, the operations comprising:

obtaining a representation of a call for a DP function, wherein the representation includes indicators of arguments associated with the call for the DP function;

generating an invocation stub, based at least in part upon the representation and the associated arguments, the invocation stub including computer executable instructions that bridge a logical arrangement of DP computations of the DP function to a physical arrangement of DP computations to be performed on DP hardware of the one or more computing devices by calculating logic indices of each DP activity based on physical thread indices and a logical compute domain, the DP hardware being capable of performing DP computations and the logical arrangement of the DP computations being defined, at least in part, by the representation of the call for the DP function with its associated arguments,

the generating comprising;

determining a physical location in the DP hardware where the DP computations will occur for the logical arrangement of the DP computation;

choosing an appropriate thread deployment strategy;

setting up a field for the DP function with target-dependent resources, wherein the field comprises a data set operated upon by the DP computations of the DP function, the setting up including;

examining the arguments associated with the DP function and configuring the data set based upon the examining;

declaring how many threads inside a thread group are to be deployed in multiple dimensions;

preparing parameters of a kernel based upon what the kernel expects, the kernel being a unit DP computation of the DP function, the preparing including;

determining whether the associated arguments include one or more special indices;

in response to the determining regarding the one or more special indices, creating index instances based upon the one or more special index types;

determining whether the associated arguments match actual parameters;

in response to the determining regarding the associated arguments matching actual parameters, broadcasting a value for the kernel to use or projecting a field, wherein the field is a data set operated upon by the DP computations of the DP function.

15. A system comprising:

a data parallel (DP) compute engine comprising one or more graphics processing units; and

a non-DP host configured with instructions that are executable to perform acts comprising;

obtaining a representation of a call for a DP function, wherein the representation includes indicators of arguments associated with the call for the DP function;

generating an invocation stub, based at least in part upon the representation and the associated arguments, the invocation stub including computer executable instructions that bridge a logical arrangement of DP computations of the DP function to a physical arrangement of DP computations to be performed on DP hardware of the one or more computing devices, the DP hardware being capable of performing DP computations and the logical arrangement of the DP computations being defined by the representation of the call for a DP function with its associated arguments;

the generating comprising;

setting up a field for the DP function with target-dependent resources, wherein the field comprises a data set operated upon by the DP computations of the DP function;

preparing parameters of a kernel based upon what the kernel expects, the kernel being a unit DP computation of the DP function; and

outputting the invocation stub into a memory.

16. The system as recited in claim 15, wherein the setting up includes:

examining the arguments associated with the call for the DP function and configuring the data set based upon the examining;

declaring how many threads inside a thread group are to be deployed in multiple dimensions; and

mapping of a thread position of the DP hardware to a logical DP activity position in the logical arrangement of the DP computations.

17. The system as recited in claim 15, wherein the setting up includes mapping of a thread position of the DP hardware to a logical DP activity position in the logical arrangement of the DP computations, the mapping including transformation index flattening and index raising.

18. The system as recited in claim 15, wherein the preparing includes:

determining whether the associated arguments include one or more tokens;

in response to the determining regarding the one or more tokens, creating index instances based upon the one or more tokens.

19. The system as recited in claim 15, wherein the preparing includes:

determining whether the associated arguments match actual parameters;

in response to the determining regarding the associated arguments matching the actual parameters, broadcasting a value for the kernel to use or projecting a field, wherein the field comprises a data set operated upon by the DP computations of the DP function.

20. The system as recited in claim 15, wherein the preparing includes:

determining whether the associated arguments include one or more tokens;

in response to the determining regarding the one or more tokens, creating index instances based upon the one or more tokens;

determining whether the associated arguments match actual parameters;

in response to the determining regarding arguments matching the actual parameters, broadcasting a value for the kernel to use or projecting a field, wherein the field comprises a data set operated upon by the DP computations of the DP function.