# US 2018/0024869 A1 · Guided load balancing of graph processing workloads on heterogeneous clusters

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0024869 A1
- Document ID: US20180024869A1
- Status: Published application
- Kind: A1
- Application number: 15/631,848
- Filed: 2017-06-23
- Published: 2018-01-25
- Earliest claimed: 2016-07-22
- Assignees: Board of Regents, The University of Texas System
- Applicants: Board of Regents, The University of Texas System
- Inventors: Lizy Kurian John; Shuang Song; Andreas Gerstlauer
- Web page: https://patentgrep.com/patent/US20180024869A1

## CPC

- G06F 9/5083: {Techniques for rebalancing the load in a distributed system}
- G06F 9/5005: {to service a request}
- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- G06F 9/46: Multiprogramming arrangements
- H04L 45/46: {Cluster building}
- H04L 47/125: by balancing the load, e.g. traffic engineering
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

A method, system and computer program product for load balancing of graph processing workloads. Synthetic proxy graphs are generated to characterize machines' graph processing speeds in a cluster. Each of the graph applications executing in the cluster is profiled using the synthetic graphs to form profiling sets. These formed profiling sets are run among the machines in the cluster to capture the machines' graph processing speeds. A metric for each of the graph applications is computed from a relative speedup among the machines in the cluster and/or the graph processing speeds. A graph file of a natural graph and a graph application are loaded. A metric out of the computed metrics is selected based on the graph application. The natural graph is then partitioned into multiple chunks which is distributed onto two or more machines in the cluster based on the selected metric and a user selected partitioning algorithm.

## Claims

### Claim 1

A method for load balancing of graph processing workloads, the method comprising:
generating synthetic proxy graphs to characterize machines' graph processing speeds in a cluster;
profiling each of a plurality of graph applications executing in said cluster using said synthetic graphs to form profiling sets;
running said formed profiling sets among machines in said cluster to capture said machines' graph processing speeds;
computing a relative speedup among said machines in said cluster;
computing a metric for each of said graph applications from said relative speedup and/or said graph processing speeds, wherein said metric represents the application-specific relations between said graph processing speeds of said machines in said cluster;
loading a graph file of a natural graph and a first graph application;
selecting a metric out of said computed metrics based on said first graph application; and
partitioning, by a processor, said natural graph into multiple chunks and distributing said chunks onto two or more of said machines in said cluster based on said selected metric and a user selected partitioning algorithm.

### Claim 2 (depends on 1)

The method as recited in claim 1, wherein said metric comprises α parameter corresponding to an execution time of a slowest machine in said cluster.

### Claim 3 (depends on 1)

The method as recited in claim 1, wherein each of said generated synthetic proxy graphs is guided by a distribution factor that determines a sparsity level of said proxy graph and using a number of vertices.

### Claim 4 (depends on 3)

The method as recited in claim 3 further comprising:
computing a probability density function corresponding to a probability of each vertex based on said distribution factor.

### Claim 5 (depends on 4)

The method as recited in claim 4 further comprising:
transforming said probability density function into a cumulative density function, wherein said cumulative density function generates a total number of degrees of any vertex.

### Claim 6 (depends on 3)

The method as recited in claim 3 further comprising:
computing said distribution factor using a number of vertices and edges in an existing natural graph.

### Claim 7 (depends on 1)

The method as recited in claim 1, wherein said synthetic proxy graphs are power-law proxy graphs, wherein said proxy graphs follow a power-law distribution, wherein said power-law distribution is a functional relationship between two objects in statistics, wherein a first object of said two objects varies as a power of a second object of said two objects.

### Claim 8 (depends on 1)

The method as recited in claim 1, wherein said cluster is a heterogeneous cluster.

### Claim 9 (depends on 1)

The method as recited in claim 1 further comprising:
classifying said machines of said cluster into different groups;
selecting one machine from each group to be profiled;
running each profiling set on one machine from each group to capture each machine's graph processing speed by obtaining a runtime of each group; and
computing said relative speedup among machines in each group from said runtime.

### Claim 10 (depends on 1)

The method as recited in claim 1, wherein said metric represents the application-specific relations between graph processing speeds of different types of machines in a heterogeneous cluster.

### Claim 11 (depends on 1)

The method as recited in claim 1 further comprising:
storing said computed metrics for said graph applications.

### Claim 12 (depends on 1)

The method as recited in claim 1 further comprising:
finalizing said natural graph by constructing connections among said machines in said cluster; and
executing said first graph application.

### Claim 13

A method for selecting which machines in a cluster to perform a job, the method comprising:
generating synthetic proxy graphs to characterize machines' graph processing speeds in a cluster;
generating information by profiling said generated proxy graphs; and
selecting, by a processor, two or more machines in said cluster to perform said job using said information.

### Claim 14 (depends on 13)

The method as recited in claim 13, wherein said information comprises one of the following: cost, speedup, performance and energy.

### Claim 15

A computer program product for load balancing of graph processing workloads, the program code comprising the programming instructions for:
generating synthetic proxy graphs to characterize machines' graph processing speeds in a cluster;
profiling each of a plurality of graph applications executing in said cluster using said synthetic graphs to form profiling sets;
running said formed profiling sets among machines in said cluster to capture said machines' graph processing speeds;
computing a relative speedup among said machines in said cluster;
computing a metric for each of said graph applications from said relative speedup and/or said graph processing speeds, wherein said metric represents the application-specific relations between said graph processing speeds of said machines in said cluster;
loading a graph file of a natural graph and a first graph application;
selecting a metric out of said computed metrics based on said first graph application; and
partitioning said natural graph into multiple chunks and distributing said chunks onto two or more of said machines in said cluster based on said selected metric and a user selected partitioning algorithm.

### Claim 16 (depends on 15)

The computer program product as recited in claim 15, wherein said metric comprises a parameter corresponding to an execution time of a slowest machine in said cluster.

### Claim 17 (depends on 15)

The computer program product as recited in claim 15, wherein each of said generated synthetic proxy graphs is guided by a distribution factor that determines a sparsity level of said proxy graph and using a number of vertices.

### Claim 18 (depends on 17)

The computer program product as recited in claim 17, wherein the program code further comprises the programming instructions for:
computing a probability density function corresponding to a probability of each vertex based on said distribution factor.

### Claim 19 (depends on 18)

The computer program product as recited in claim 18, wherein the program code further comprises the programming instructions for:
transforming said probability density function into a cumulative density function, wherein said cumulative density function generates a total number of degrees of any vertex.

### Claim 20 (depends on 15)

The computer program product as recited in claim 15, wherein said synthetic proxy graphs are power-law proxy graphs, wherein said proxy graphs follow a power-law distribution, wherein said power-law distribution is a functional relationship between two objects in statistics, wherein a first object of said two objects varies as a power of a second object of said two objects.
