Graph-data partitioning for workload-balanced distributed computation with cost estimation functions
US9477532B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 6, 2015 |
| Grant date | Oct 25, 2016 |
| Priority date | — |
| Expiry date | Oct 6, 2035 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2209/5022
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques herein perform workload-balanced graph partitioning. Each graph partition is distributed to a respective computer. Each computer applies a workload-estimation function to its partition to calculate a numeric workload-value that indicates how much computation the partition needs. Each computer sends its numeric workload-value to a master computer. The master compares the highest and lowest numeric workload-values. If the difference exceeds a threshold, the master detects how much work should overloaded-computers offload to under-utilized computers. To each overloaded-computer, the master sends a directive with a balancing numeric workload-value that indicates how much computation to offload and an identifier of an under-utilized computer to receive the offload. Based on this directive and the workload-estimation function, an overloaded-computer selects a portion of its partition that corresponds to the balancing numeric workload-value, removes that portion from its partition, and transfers the portion to the under-utilized computer, which adds the portion to its partition.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.