Dynamic Data Partitioning For Optimal Resource Utilization In A Parallel Data Processing System

• US 20120278587A1
• Filed: 06/27/2012
• Published: 11/01/2012
• Est. Priority Date: 04/26/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Caufield, Brian K., Ding, Fan, Shum, Mi Wan, Wei, Dong Jie, Wong, Samuel HK
• Granted Patent: US 9,811,384 B2
• Time in Patent Office: Days
• US Class Current: 711/173
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A method, computer program product, and system for dynamically distributing data for parallel processing in a computing system, comprising allocating a data buffer to each of a plurality of data partitions, where each data buffer stores data to be processed by its corresponding data partition, distributing data in multiple rounds to the data buffers for processing by the data partitions, where in each round the data is distributed based on a determined data processing capacity for each data partition, and where a greater amount of data is distributed to the data partitions with higher determined processing capacities, and periodically monitoring usage of each data buffer and re-determining the determined data processing capacity of each data partition based on its corresponding data buffer usage.

Claims

1. A computer-implemented method for dynamically distributing data for parallel processing in a computing system, comprising:

allocating a data buffer to each of a plurality of data partitions, wherein each data buffer stores data to be processed by its corresponding data partition;

distributing data in multiple rounds to the data buffers for processing by the data partitions, wherein in each round the data is distributed based on a determined data processing capacity for each data partition, wherein a greater amount of data is distributed to the data partitions with higher determined processing capacities; and

periodically monitoring usage of each data buffer and re-determining the determined data processing capacity of each data partition based on its corresponding data buffer usage.

2. The computer implemented method of claim 1, wherein said distribution is performed using a round robin distribution technique.

3. The computer implemented method of claim 1, further comprising:

storing the determined data processing capacity of each data partition in a partition processing table.

4. The computer implemented method of claim 3, wherein the determined data processing capacity for each data partition has an initial value based on a historical data processing rate for that data partition, and wherein the historical data processing rates are stored in the partition processing table.

5. The computer implemented method of claim 3, wherein the determined data processing capacity for each data partition has an initial value based on an estimated data processing rate for that data partition, and wherein the estimated data processing rates are stored in the partition processing table.

6. The computer implemented method of claim 1, wherein said re-determination of the determined data processing capacity further comprises:

for each partition, determining if a free portion of the corresponding data buffer is greater than or equal to half of the data buffer size, and if the result of the determination is yes, increasing the determined data processing capacity of the data partition.

7. The computer implemented method of claim 1,

wherein the data comprises a plurality of data records;

wherein each data buffer has a size 2 n, where n is a number of data records having a total size that is expected to fill half of each data buffer; and

wherein said re-determination of the determined data processing capacity is performed after every n/2 rounds of data distribution.

8. The computer implemented method of claim 7, wherein the determined data processing capacity has an initial value of x, and said re-determination of the determined data processing capacity further comprises:

for each partition, determining if a free portion of the corresponding data buffer is greater than or equal to half of the data buffer size, and if the result of the determination is yes, setting the determined data processing capacity of the data partition to a value greater than x, and if the result of the determination is no, setting the determined data processing capacity of the data partition to x.

9. The computer implemented method of claim 7, wherein the determined data processing capacity has an initial value of x, and said re-determination of the determined data processing capacity further comprises:

for each partition, determining if a free portion of the corresponding data buffer is greater than or equal to half of the data buffer size, and if the result of the determination is no, setting the determined data processing capacity of the data partition to a value less than x, and if the result of the determination is yes, setting the determined data processing capacity of the data partition to x.