Patent ID: 9477532
Filing Date: 2016-10-25
CPC Classification: G06F

Claim Text:
1. A method comprising: dividing a graph into a plurality of partitions, wherein each partition of said plurality of partitions comprises a plurality of vertices that are connected to a plurality of edges; distributing, to each computer of a plurality of computers, a respective partition of said plurality of partitions; calculating a plurality of numeric workload values, wherein each numeric workload value of said plurality of numeric workload values is associated with a respective computer of said plurality of computers, wherein said each numeric workload value is determined by said respective computer based on a workload estimation function, wherein said each numeric workload value indicates an amount of computation to be performed by said respective computer to process said respective partition; sending said plurality of numeric workload values to a central computer, wherein said each numeric workload value is sent by said respective computer; detecting, by said central computer, that a difference between two numeric workload values of said plurality of numeric workload values exceeds a threshold; sending, by said central computer to an over-utilized computer of said plurality of computers, a directive that includes a balancing numeric workload value that indicates an amount of computation, wherein said directive identifies an under-utilized computer of said plurality of computers; determining, by said over-utilized computer and based on said workload estimation function, a portion of said respective partition, wherein said balancing numeric workload value indicates an amount of computation to process said portion; removing, by said over-utilized computer, said portion from said respective partition of said over-utilized computer; sending, by said over-utilized computer to said under-utilized computer, said portion; adding, by said under-utilized computer, said portion to said respective partition of said under-utilized computer.