Configurable partitioning of parallel data for parallel processing

• US 8,806,426 B2
• Filed: 06/04/2008
• Issued: 08/12/2014
• Est. Priority Date: 06/04/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Duffy, Joe, Ostrovsky, Igor, Yildiz, Huseyin, Toub, Stephen
• Primary Examiner(s): Nahar, Qamrun
• Application Number:
  US12/132,613
• Publication Number:
  US 20090319992A1
• Time in Patent Office: 2,260 Days
• Field of Search: None
• US Class Current: 717/106
• CPC Class Codes: G06F 8/00 Arrangements for software engineering testing or debugging G06F11/36; administrative, planning or organisation aspects of software project management G06Q10/06

Abstract

A data partitioning interface provides procedure headings to create data partitions for processing data elements in parallel, and for obtaining data elements to process, without specifying the organizational structure of a data partitioning. A data partitioning implementation associated with the data partitioning interface provides operations to implement the interface procedures, and may also provide dynamic partitioning to facilitate load balancing.

Claims

1. A method which may be used by a software developer to configure partitioning of parallel data for parallel processing, the method comprising the steps of:

obtaining a data partitioning interface, namely, obtaining at least one procedure heading for invoking a procedure to create a data partitioning and obtaining at least one procedure heading for invoking a procedure to obtain a data element from a data partition, the data partitioning having an organizational structure which is unspecified in the data partitioning interface and in particular the data partitioning interface being free of an organizational structure which specifies data element partitions based on whether data elements are replicated and also being free of an organizational structure which specifies data element partitions based on where data elements are replicated; and

associating a data partitioning implementation with the data partitioning interface, namely, associating at least one procedure body which implements creation of a data partitioning and at least one procedure body which implements obtaining a data element from a data partition for parallel processing with at least one other parallel data element, the organizational structure of the data partitioning being specific in the data partitioning implementation.

2. The method of claim 1, further comprising configuring software to invoke data partitioning implementation instructions which indicate whether a data partitioning supports access to a data element based on an ordinal position of the data element.

3. The method of claim 1, further comprising configuring software to invoke data partitioning implementation instructions which indicate whether a data partitioning supports dynamic partitioning.

4. The method of claim 1, further comprising configuring software to invoke data partitioning implementation instructions which perform dynamic partitioning to facilitate load balancing.

5. The method of claim 1, further comprising configuring software to transmit at least one partitioning assistance value to data partitioning implementation instructions.

6. The method of claim 5, wherein the software is configured to transmit to the data partitioning implementation instructions at least one of the following partitioning assistance values:

a processing-time-distribution value indicating how processing time for data elements correlates with the number of data elements, a partitioning-method value identifying a particular partitioning scheme.

7. The method of claim 1, wherein the method comprises defining a constructor for a class which implements a specific data partitioning organizational structure.

8. A computer system with parallel data for parallel processing in heterogeneous partitions defined by data partitioning algorithm implementations, the system comprising:

at least one memory configured with executable instructions;

at least one logical processor configured to execute at least a portion of the instructions for data partitioning;

a data partitioning interface which configures the memory and is designed to invoke a procedure to create a data partitioning and to invoke a procedure to obtain a data element from a data partition, the data partitioning having an organizational structure which is unspecified in the data partitioning interface and in particular the data partitioning interface being free of an organizational structure which specifies data element partitions based on whether data elements are replicated and also being free of an organizational structure which specifies data element partitions based on where data elements are replicated;

a first data partitioning implementation which configures the memory and is associated with the data partitioning interface, namely, instructions which implement creation of a first data partitioning and instructions which implement obtaining a data element from a data partition of the first data partitioning for parallel processing with at least one other parallel data element, the first data partitioning having a first organizational structure which is specific in the first data partitioning implementation; and

a second data partitioning implementation which configures the memory and is associated with the data partitioning interface, namely, instructions which implement creation of a second data partitioning and instructions which implement obtaining a data element from a data partition of the second data partitioning for parallel processing with at least one other parallel data element, the second pluggable custom data partitioning having a second organizational structure which is specific in the second data partitioning implementation and different from the first organizational structure.

9. The system of claim 8, wherein the data partitioning interface comprises a supports-ordinal-positions procedure heading for invoking data partitioning implementation instructions which indicate whether a data partitioning supports access to a data element of a data partition based on an ordinal position of the data element.

10. The system of claim 8, wherein the data partitioning interface comprises a supports-dynamic-partitioning procedure heading for invoking data partitioning implementation instructions which indicate whether a data partitioning supports at least one of the following:

adding a data partition to a previously created group of data partitions in a data partitioning, removing a data partition from a previously created group of data partitions in a data partitioning.

11. The system of claim 8, wherein the system comprises multiple logical processors.

12. The system of claim 8, wherein the system comprises memory configured by an interface definition which provides a get-current-partitions property for obtaining a current data partitioning.

13. The system of claim 8, wherein the system comprises memory configured by an interface definition which provides an individual-data-partition property for accessing a data partition in a data partitioning.

14. The system of claim 8, wherein the system comprises memory configured by an interface definition which provides a get-next-data-element property for obtaining a data element from a data partition of a data partitioning.

15. A storage medium configured with computer data and computer instructions for partitioning parallel data for parallel processing in partitions defined by a pluggable custom data partitioning algorithm implementation, the method comprising the steps of:

associating a pluggable custom data partitioning implementation with a data partitioning interface, the pluggable custom data partitioning implementation designed to implement creation of a pluggable custom data partitioning and to implement obtaining a data element from a pluggable custom data partition of the pluggable custom data partitioning for parallel processing, the pluggable custom data partitioning having an organizational structure that is specific in the pluggable custom data partitioning implementation and unspecified in the data partitioning interface and in particular the data partitioning interface being free of an organizational structure which specifies data element partitions based on whether data elements are replicated and also being free of an organizational structure which specifies data element partitions based on where data elements are replicated; and

executing instructions of the pluggable custom data partitioning implementation for creating a pluggable custom data partitioning of parallel data for parallel processing.

16. The configured medium of claim 15, wherein the method comprises executing instructions of the pluggable custom data partitioning implementation to create a first pluggable custom data partitioning from a collection of data elements while running an application program a first time, and executing instructions of the pluggable custom data partitioning implementation to create a second pluggable custom data partitioning from the collection of data elements while running the application program a second time, and wherein the data partitionings differ in that at least one of the data elements is assigned to a different data partition in the first data partitioning than in the second data partitioning.

17. The configured storage medium of claim 15, wherein the step of executing instructions of the data partitioning implementation for creating a data partitioning assigns data elements to data partitions, wherein the number of data elements assigned to a given data partition drops to a predetermined threshold, and in response to the drop the computer instructions assign at least one other data element to the given data partition.

18. The configured storage medium of claim 15, wherein the step of executing instructions of the data partitioning implementation for creating a data partitioning assigns data elements to data partitions, and wherein an additional data partition is created and is assigned data elements after data elements have been already been assigned to and obtained from at least one other data partition.

19. The configured medium of claim 15, wherein the method comprises executing instructions of the data partitioning implementation to receive at least one partitioning assistance value for data partitioning.

20. The configured medium of claim 15, wherein the method comprises executing instructions by which an allowing thread can grant other threads permission to process data elements that were previously assigned to the allowing thread.