US 8,429,165 B1Granted

Systems and methods of partitioning data for synchronous parallel processing

AssigneeXerox Corporation

InventorsGueyoung Jung, Shanmuga-Nathan Gnanasambandam, Tridib Mukherjee

Life of this patent

Estimating the term…

Loading patent…

Abstract

Methods and systems for partitioning data for processing in a plurality of data centers are disclosed. For each of a plurality of data centers, a time period required for the data center to process an amount of information may be estimated. The plurality of data centers may be ordered based on the time period for each data center. Data may be received from one or more sources. A data center having a smallest time period from the ordered plurality of data centers may be selected to be added to a set of data centers. An overall execution time for the set of data centers to process the data may be determined. The selecting and determining operations may be repeated until the overall execution time satisfies one or more threshold criteria. The data may be transmitted to the set of data centers.

Claims18

Dependent claims

A method of partitioning data for processing in a plurality of data centers, the method comprising:

for each of a plurality of data centers, estimating, by a computing device, a time period required for the data center to process an amount of information;
ordering, by the computing device, the plurality of data centers based on the time period for each data center;
receiving data from one or more sources, wherein the data comprises at least a plurality of data partitions;
selecting, by the computing device, a data center having a smallest time period from the ordered plurality of data centers to add to a set of data centers;
determining, by the computing device, an overall execution time for the set of data centers to process the data, wherein determining the overall execution time for the set of data centers comprises:
sorting the plurality of data partitions into an ordered set of data partitions,
for each data center in the set of data centers, determining an amount of the data to assign to the data center,
selecting a data center from the set of data centers,
assigning the largest remaining data partition from the ordered set of data partitions to the selected data center while the difference between the amount of data assigned to the selected data center and the amount of data in the data partitions assigned to the selected data center is greater than the amount of data in the largest remaining data partition,
repeating the selecting and assigning operations for each data center,
repeating the selecting, assigning and first repeating operations until all data partitions are assigned to a data center, and
for each data center, ordering the data partitions assigned to the data center based on the size of the data partitions;
repeating the selecting and determining operations until the overall execution time satisfies one or more threshold criteria;
and
transmitting, by the computing device, the data to the set of data centers.

12 more elements

A system for partitioning data for processing in a plurality of data centers, the system comprising:

a computing device;
and
a non-transitory processor-readable storage medium in operable communication with the computing device,
wherein the non-transitory processor-readable storage medium contains one or more programming instructions that, when executed, cause the computing device to:
for each of a plurality of data centers, estimate a time period required for the data center to process an amount of information,
order the plurality of data centers based on the time period for each data center,
receive data from one or more sources, wherein the data comprises at least a plurality of data partitions,
select a data center having a smallest time period from the ordered plurality of data centers to add to a set of data centers,
determine an overall execution time for the set of data centers to process the data, wherein the one or more programming instructions that, when executed, cause the computing device to determine an overall execution time for the set of data centers comprises one or more programming instructions that, when executed, cause the computing device to:
sort the plurality of data partitions into an ordered set of data partitions,
for each data center in the set of data centers, determine an amount of the data to assign to the data center,
select a data center from the set of data centers,
assign the largest remaining data partition from the ordered set of data partitions to the selected data center the difference between the amount of data assigned to the selected data center and the amount of data in the data partitions assigned to the selected data center is greater than the amount of data in the largest remaining data partition,
repeat the selecting and assigning operations for each data center,
repeat the selecting, assigning and first repeating operations until all data partitions are assigned to a data center, and
for each data center, order the data partitions assigned to the data center based on the size of the data partitions,
repeat the selecting and determining operations until the overall execution time satisfies one or more threshold criteria, and
transmit the data to the set of data centers.

15 more elements

Dependencies are inferred from the claim text.