METHOD TO DYNAMICALLY DISTRIBUTE A MULTI-DIMENSIONAL WORK SET ACROSS A MULTI-CORE SYSTEM

• US 20110161943A1
• Filed: 12/30/2009
• Published: 06/30/2011
• Est. Priority Date: 12/30/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Horton, Brian H., Bellows, Gregory H., Madruga, Joaquin, Minor, Barry L.
• Granted Patent: US 8,495,604 B2
• Time in Patent Office: Days
• US Class Current: 717/149
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

A method provides efficient dispatch/completion of an N Dimensional (ND) Range command in a data processing system (DPS). The method comprises: a compiler generating one or more commands from received program instructions; ND Range work processing (WP) logic determining when a command generated by the compiler will be implemented over an ND configuration of operands, where N is greater than one (1); automatically decomposing the ND configuration of operands into a one (1) dimension (1D) work element comprising P sequentially ordered work items that each represent one of the operands; placing the 1D work element within a command queue of the DPS; enabling sequential dispatching of 1D work items in ordered sequence from to one or more processing units; and generating an ND Range output by mapping the 1D work output result to an ND position corresponding to an original location of the operand represented by the 1D work item.

Claims

1. In a data processing system, a method for efficient dispatch/completion of an N Dimensional (ND) Range command, said method comprising:

a compiler generating one or more commands from received program instructions, wherein said one or more commands are utilized by a runtime scheduler to schedule work for execution on one or more processing units within the data processing system;

ND Range work scheduling (WS) logic associated with the compiler determining when a command generated by the compiler will be implemented over an ND Range of operands that are arranged in an N dimensional configuration, where N is greater than one;

when N is greater than one, automatically decomposing the ND Range of operands into a one (1) dimension work element comprising P sequentially ordered work items that each represent, within the one dimensional work element, one of the ND Range of operands;

placing the single dimension work element within one or more entries of a command queue of the data processing system, wherein each of the one or more entries holds a 1D array of work items in an ordered sequence; and

enabling sequential dispatch of the 1D array of work items from the command queue to the one or more processing units, wherein the 1D array of work items are dispatched for execution in the ordered sequence.

2. The method of claim 1, wherein said automatically decomposing the ND Range of operands into a one dimension work element further comprises:

selecting a first mapping order for re-arranging the ND Range of operands, which order is provided by a first logic/algorithm for decomposing ND Range of operands, wherein said first mapping order is a pre-programmed first order;

utilizing the first mapping order, dynamically mapping each operand from the ND Range to a location within the single dimension array of the work element;

tagging the work element with an indication of the first mapping order utilized to create the single dimension array from the ND Range.

3. The method of claim 1, wherein said automatically decomposing the ND Range of operands into a one dimension work element further comprises:

determining a numerical size of each dimension within the ND Range, wherein a first numerical size represents a total number of operands in a first dimension of the N dimensions;

representing the numerical size of each dimension in an index format having each numerical size presented in sequence;

calculating a total number of operands within the ND Range of operands; and

storing the total number and the index format within a persistent storage of the data processing system.

4. The method of claim 3, wherein said calculating a total number of operands within the ND Range of operands comprises multiplying the numerical size of each dimension with each other and subtracting any index space within the ND Range that does not include an operand.

5. The method of claim 3, further comprising:

providing a unique identification (ID) for the command;

associating the unique ID to one or more stored parameters of the command, including the total number and index format and a mapping order;

storing the unique ID along with the one or more stored parameters; and

assigning the unique ID to the work element and to each work item dispatched from the work element.

6. The method of claim 5, further comprising:

detecting the unique ID from within a single dimension work output result corresponding to a single dimension work item of the single dimension work element dispatched to the one or more processing units for execution;

retrieving from the persistent storage, the ND Range parameters associated with the unique ID; and

generating an ND Range output from multiple of the single dimension work output result utilizing a second algorithm which factors in the total number, index format, and first mapping order from the first algorithm.

7. The method of claim 1, further comprising:

responsive to receipt from the one or more processing units of a single dimension work output result corresponding to a single dimension work item of the single dimension work element dispatched to the one or more processing units for execution, the ND Range WP logic generating an ND Range output by mapping the received single dimension work output result to an ND position corresponding to an original location of the ND Range operand represented by the single dimension work item.

8. The method of claim 5, wherein:

the command queue is a global command queue of a multi-node, data processing system; and

the method further comprises;

providing each processing unit to which a work item of the single dimension work element is dispatched with the unique ID of the work item;

enabling each processing unit to retrieve the sequentially ordered work items of the single dimension work element in correct sequential order to maintain an ordered dispatch and tracking sequence relative to a mapping from the ND Range operations;

enabling each processing unit to tagged each work output result generated by executing the work item with the unique ID and information identifying the correct sequential order.

9. The method of claim 8, further comprising:

sequentially dispatching each work item as one item within a chunk of sequential work items, wherein the chunk of sequential work items are dispatched as a first sized chunk for low latency processing nodes and a larger second chunk size for high latency processing nodes;

automatically tracking a number of work items remaining within the work element; and

forwarding to a first processing unit to which a first chunk of work items is dispatched a first count of work items remaining, which is utilized along with a first chunk size to determine which work items are dispatched to the first processing unit;

decrementing the work items remaining by the first chunk size to generate a second count which is forwarded to a next processing unit to which a second chunk of work items are dispatched; and

forwarding the unique ID of the command to the first processing unit and subsequent processing units to which the work items are dispatched.

10. A data processing system, comprising:

one or more processing units;

a memory coupled to the one or more processing units;

a compiler generating one or more kernels/commands from received program instructions, wherein said one or more kernels/commands are utilized by a runtime scheduler to schedule work for execution on one or more processing units within the data processing system;

ND Range work scheduling (WS) logic associated with the compiler performing the functions of;

determining when a command generated by the compiler will be implemented over an ND Range of operands that are arranged in an N dimensional configuration, where N is greater than one;

when N is greater than one, automatically decomposing the ND Range of operands into a one dimension work element comprising P sequentially ordered work items that each represent, within the one dimensional work element, one of the ND Range of operands; and

a scheduler performing the functions of;

placing the single dimension work element within one or more entries of a command queue of the data processing system, wherein each of the one or more entries holds a 1D array of work items in an ordered sequence; and

enabling sequential dispatch of the 1D array of work items from the command queue to the one or more processing units, wherein the 1D array of work items are dispatched for execution in the ordered sequence.

11. The data processing system of claim 10, wherein said automatically decomposing the ND Range of operands into a one dimension work element further comprises:

selecting a first mapping order for re-arranging the ND Range of operands, which order is provided by a first logic/algorithm for decomposing ND Range of operands, wherein said first mapping order is a pre-programmed first order;

utilizing the first mapping order, dynamically mapping each operand from the ND Range to a location within the single dimension array of the work element; and

tagging the work element with an indication of the first mapping order utilized to create the single dimension array from the ND Range.

12. The data processing system of claim 11, wherein said automatically decomposing the ND Range of operands into a one dimension work element further comprises:

determining a numerical size of each dimension within the ND Range, wherein a first numerical size represents a total number of operands in a first dimension of the N dimensions;

representing the numerical size of each dimension in an index format having each numerical size presented in sequence;

calculating a total number of operands within the ND Range of operands; and

storing the total number and the index format within a persistent storage of the data processing system.

13. The data processing system of claim 12, wherein said calculating a total number of operands within the ND Range of operands comprises multiplying the numerical size of each dimension with each other and subtracting any index space within the ND Range that does not include an operand.

14. The data processing system of claim 12, further comprising processing logic that performs the functions of:

providing a unique identification (ID) for the command;

associating the unique ID to one or more stored parameters of the command, including the total number and index format and a mapping order;

storing the unique ID along with the one or more stored parameters; and

assigning the unique ID to the work element and to each work item dispatched from the work element.

15. The data processing system of claim 14, wherein the processing logic further comprises logic that performs the functions of:

detecting the unique ID from within a single dimension work output result corresponding to a single dimension work item of the single dimension work element dispatched to the one or more processing units for execution;

retrieving from the persistent storage, the ND Range parameters associated with the unique ID; and

generating an ND Range output from multiple of the single dimension work output result utilizing a second algorithm which factors in the total number, index format, and first mapping order from the first algorithm.

16. The data processing system of claim 14, wherein the processing logic further comprises logic that performs the functions of:

responsive to receipt from the one or more processing units of a single dimension work output result corresponding to a single dimension work item of the single dimension work element dispatched to the one or more processing units for execution, the ND Range WS logic generating an ND Range output by mapping the received single dimension work output result to an ND position corresponding to an original location of the ND Range operand represented by the single dimension work item.

17. The data processing system of claim 14, wherein:

the command queue is a global command queue of a multi-node, data processing system; and

the scheduler further performs the functions of;

providing each processing unit to which a work item of the single dimension work element is dispatched with the unique ID of the work element;

enabling each processing unit to retrieve the sequentially ordered work items of the single dimension work element in correct sequential order to maintain an ordered dispatch and tracking sequence relative to a mapping from the ND Range operations;

enabling each processing unit to tagged each work output result generated by executing the work item with the unique ID and information identifying the correct sequential order.

18. The data processing system of claim 10, wherein the scheduler comprises logic that performs the functions of:

sequentially dispatching each work item as one item within a chunk of sequential work items, wherein the chunk of sequential work items are dispatched as a first sized chunk for low latency processing nodes and a larger second chunk size for high latency processing nodes;

automatically tracking a number of work items remaining within the work element;

forwarding to a first processing unit to which a first chunk of work items is dispatched a first count of work items remaining, which is utilized along with a first chunk size to determine which work items are dispatched to the first processing unit;

decrementing the work items remaining by the first chunk size to generate a second count which is forwarded to a next processing unit to which a second chunk of work items are dispatched; and

forwarding the unique ID of the command to the first processing unit and subsequent processing units to which the work items are dispatched.

19. The data processing system of claim 14, wherein:

processing logic for generating work that is executed by the one or more processing units comprises a compiler and ND Range WS logic associated with the compiler;

work scheduling logic for dispatching work elements to the one or more processing units comprises a scheduler; and

processing logic for re-creating an ND Range output from the single dimension work items of the single dimension work element comprises the ND Range WS logic.

20. An article of manufacture embodied as a computer program product comprising:

a computer readable storage medium; and

program code on the computer readable storage medium that is executed by a first processing unit of a data processing system to provide the method functions comprising;

triggering a compiler to generate one or more kernels/commands from received program instructions, wherein said one or more kernels/commands are utilized by a runtime scheduler to schedule work for execution on one or more processing units within the data processing system;

ND Range work scheduling (WS) logic associated with the compiler determining when a kernel/command generated by the compiler will be implemented over an ND Range of operands that are arranged in an N dimensional configuration, where N is greater than one;

when N is greater than one, automatically decomposing the ND Range of operands into a one dimension work element comprising P sequentially ordered work items that each represent, within the one dimensional work element, one of the ND Range of operands;

placing the single dimension work element within one or more entries of a command queue of the data processing system, wherein each of the one or more entries holds a 1D array of work items in an ordered sequence; and

enabling sequential dispatch of the 1D array of work items from the command queue to the one or more processing units, wherein the 1D array of work items are dispatched for execution in the ordered sequence.

21. The article of manufacture of claim 20, wherein the method functions of automatically decomposing the ND Range of operands into a one dimension work element further comprises:

selecting a first mapping order for re-arranging the ND Range of operands, which order is provided by a first logic/algorithm for decomposing ND Range of operands, wherein said first mapping order is a pre-programmed first order;

utilizing the first mapping order, dynamically mapping each operand from the ND Range to a location within the single dimension array of the work element;

tagging the work element with an indication of the first mapping order utilized to create the single dimension array from the ND Range;

determining a numerical size of each dimension within the ND Range, wherein a first numerical size represents a total number of operands in a first dimension of the N dimensions;

representing the numerical size of each dimension in an index format having each numerical size presented in sequence;

calculating a total number of operands within the ND Range of operands by multiplying the numerical size of each dimension with each other and subtracting any index space within the ND Range that does not include an operand; and

storing the total number and the index format within a persistent storage of the data processing system.

22. The article of manufacture of claim 21, wherein the method further comprises:

providing a unique identification (ID) for the kernel/command;

associating the unique ID to one or more stored parameters of the command, including the total number and index format and a mapping order;

storing the unique ID along with the one or more stored parameters;

assigning the unique ID to the work element and to each work item dispatched from the work element;

detecting the unique ID from within a single dimension work output result corresponding to a single dimension work item of the single dimension work element dispatched to the one or more processing units for execution;

retrieving from the persistent storage, the ND Range parameters associated with the unique ID; and

generating an ND Range output from multiple of the single dimension work output result utilizing a second algorithm which factors in the total number, index format, and first mapping order from the first algorithm.

23. The article of manufacture of claim 20, wherein the method further comprises:

responsive to receipt from the one or more processing units of a single dimension work output result corresponding to a single dimension work item of the single dimension work element dispatched to the one or more processing units for execution, the ND Range WS logic generating an ND Range output by mapping the received single dimension work output result to an ND position corresponding to an original location of the ND Range operand represented by the single dimension work item.

24. The article of manufacture of claim 22, wherein:

the command queue is a global command queue (GCQ) of a multi-node, data processing system; and

the method further comprises;

providing each processing unit to which a work item of the single dimension work element is dispatched with the unique ID of the work element;

enabling each processing unit to retrieve the sequentially ordered work items of the single dimension work element in correct sequential order to maintain an ordered dispatch and tracking sequence relative to a mapping from the ND Range operations; and

enabling each processing unit to tagged each work output result generated by executing the work item with the unique ID and information identifying the correct sequential order.

25. The article of manufacture of claim 24, wherein the method further comprises:

sequentially dispatching each work item as one item within a chunk of sequential work items, wherein the chunk of sequential work items are dispatched as a first sized chunk for low latency processing nodes and a larger second chunk size for high latency processing nodes;

automatically tracking a number of work items remaining within the work element;

forwarding to a first processing unit to which a first chunk of work items is dispatched a first count of work items remaining, which is utilized along with a first chunk size to determine which work items are dispatched to the first processing unit;

decrementing the work items remaining by the first chunk size to generate a second count which is forwarded to a next processing unit to which a second chunk of work items are dispatched; and

forwarding the unique ID of the command to the first processing unit and subsequent processing units to which the work items are dispatched.