GROUPING MECHANISM FOR MULTIPLE PROCESSOR CORE EXECUTION

• US 20110125805A1
• Filed: 11/24/2009
• Published: 05/26/2011
• Est. Priority Date: 11/24/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ostrovsky, Igor
• Granted Patent: US 8,380,724 B2
• Time in Patent Office: Days
• US Class Current: 707/803
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• 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 concurrent grouping operation for execution on a multiple core processor is provided. The grouping operation is provided with a sequence or set of elements. In one phase, each worker receives a partition of a sequence of elements to be grouped. The elements of each partition are arranged into a data structure, which includes one or more keys where each key corresponds to a value list of one or more of the received elements associated with that key. In another phase, the data structures created by each worker are merged so that the keys and corresponding elements for the entire sequence of elements exist in one data structure. Recursive merging can be completed in a constant time, which is not proportional to the length of the sequence.

Claims

1. A method of grouping a sequence of elements, comprising:

receiving multiple partitions of a sequence of elements, wherein the available cores of a multiple core processor each receive a separate partition of the multiple partitions for processing;

concurrently grouping each separate partition into a key table of at least one value lists of elements, wherein the elements in each value list include a common key; and

merging each of the key tables together to form a final key table such that all keys and their corresponding value lists are included in the final key table.

2. The method of claim 1 wherein each of the elements of the separate partition of elements has an associated key and elements having the same key are included in the value list of elements.

3. The method of claim 2 wherein each key table includes a plurality of keys each having a corresponding value list of elements with that key.

4. The method of claim 2 wherein the keys are generated with a key selector function operating on each of the elements of the separate partition.

5. The method of claim 1 wherein the merging includes generating a new key table.

6. The method of claim 1 wherein the merging includes expanding an existing key table.

7. The method of claim 1 wherein the merging includes,

adding keys and corresponding value lists into the key table if the key is present in only one key table;

and

concatenating value lists of common keys present in more than one key table.

8. The method of claim 7 wherein the merging includes repeatedly merging partial key tables together to form a complete key table.

9. The method of claim 8 wherein the partial key tables are sequentially merged together to form the complete key table.

10. The method of claim 8 wherein the partial key tables a recursively merged together to form the complete key table.

11. A computer readable storage medium storing computer executable instructions for controlling a computing device to perform a method comprising:

receiving multiple partitions of a sequence of elements, wherein the multiple partitions correspond with a number of available cores in the multiple core processor, wherein each core receives a separate partition for processing and wherein each element includes a corresponding key;

concurrently grouping each separate partition into a corresponding data structure having at least one key, wherein each key in the data structure corresponds with a value list of elements having that key; and

repeatedly merging data structures together to form a corresponding merged data structure until all keys and their corresponding value lists from each of the data structures are included in the complete data structure.

12. The computer readable storage medium of claim 11 wherein the keys are generated with a key selector function operating on each of the elements of the separate partition.

13. The computer readable storage medium of claim 11 wherein the data structure includes a linked list.

14. The computer readable storage medium of claim 11 wherein merging data structures includes providing keys and value lists into a new data structure in memory or adding keys and value lists into an existing data structure in the memory.

15. The computer readable storage medium of claim 14 wherein repeatedly merging data structures includes:

adding keys and corresponding value lists into the data structure if the key is present in only one data structure; and

concatenating value lists of keys present in more than one data structure.

16. The computer readable storage medium of claim 15 wherein repeatedly merging data structures includes:

combining small groups of data structures by adding together and concatenating value lists of the small groups of data structures to form partial data structures; and

repeatedly combining small groups of partial data structure by adding together and concatenating value lists of the small groups of data structures to form the complete data structure.

17. The computer readable storage medium of claim 16 wherein repeatedly merging data structures includes:

combining groups of two data structures by adding together and concatenating value lists of the of data structures to form a plurality of partial data structures; and

repeatedly combining groups of two partial data structure by adding together and concatenating value lists of the data structures to form the complete data structure.

18. The computer readable storage medium of claim 15 wherein repeatedly merging data structures includes sequentially combining together the data structures from each core to form the complete data structure.

19. A computer readable storage medium storing a grouping operation including computer executable instructions for controlling a computing device having a multiple core processor including a plurality of cores configured to execute a concurrent application, the grouping operation configured to perform a method comprising:

receiving multiple partitions of a sequence of elements, wherein the multiple partitions correspond with a number of available cores in the multiple core processor,

assigning each of the multiple partitions to a corresponding available core for processing such that each available core processes a separate partition of the multiple partitions;

determining a key for each element in each separate partition;

arranging the elements in each of the separate partitions into a corresponding key table through concurrent processing, wherein each key table includes at least one key corresponding with a value list having that key;

concurrently combining at least two subgroups of the key tables together to form corresponding partial key tables, wherein the combining includes,

adding keys and corresponding value lists into the data structure if the key is present in only one of the key tables in the subgroup; and

concatenating value lists of keys present in more than one key table of the subgroup; and

recursively and concurrently combining the partial key tables together to form a complete key table including all of the elements in the sequence of elements grouped together by common keys.

20. The computer readable storage medium of claim 19 wherein two key tables are included in each subgroup.