US 11,030,014 B2 · Concurrent distributed graph processing system with self-balance

Abstract

Techniques are provided for dynamically self-balancing communication and computation. In an embodiment, each partition of application data is stored on a respective computer of a cluster. The application is divided into distributed jobs, each of which corresponds to a partition. Each distributed job is hosted on the computer that hosts the corresponding data partition. Each computer divides its distributed job into computation tasks. Each computer has a pool of threads that execute the computation tasks. During execution, one computer receives a data access request from another computer. The data access request is executed by a thread of the pool. Threads of the pool are bimodal and may be repurposed between communication and computation, depending on workload. Each computer individually detects completion of its computation tasks. Each computer informs a central computer that its distributed job has finished. The central computer detects when all distributed jobs of the application have terminated.

Claims20

Dependent claims

A method comprising:

each computer of a plurality of computers independently performing:
receiving a respective distributed job to process a respective data partition of a plurality of data partitions of a same application;
dividing the respective distributed job into a plurality of local computation tasks that may concurrently execute;
dispatching the plurality of local computation tasks for execution to a first subset of a local plurality of bimodal threads that are configured for a first mode that executes local computation tasks, wherein:
a second subset of the local plurality of bimodal threads are configured for a second mode that provides remote data access, and
each bimodal thread of the local plurality of bimodal threads has two modes of operation and may be reconfigured for either the first mode that executes local computation tasks or the second mode that provides remote data access;
upon completion of a local computation task of the plurality of local computation tasks, reconfiguring a bimodal thread of the local plurality of bimodal threads for either the first mode that executes local computation tasks or the second mode that provides remote data access to increase system throughput.

4 more elements

One or more non-transitory computer-readable media storing instruction that, when executed by one or more processors, cause:

each computer of a plurality of computers independently performing:
receiving a respective distributed job to process a respective data partition of a plurality of data partitions of a same application;
dividing the respective distributed job into a plurality of local computation tasks that may concurrently execute;
dispatching the plurality of local computation tasks for execution to a first subset of a local plurality of bimodal threads that are configured for a first mode that executes local computation tasks, wherein:
a second subset of the local plurality of bimodal threads are configured for a second mode that provides remote data access, and
each bimodal thread of the local plurality of bimodal threads has two modes of operation and may be reconfigured for either the first mode that executes local computation tasks or the second mode that provides remote data access;
upon completion of a local computation task of the plurality of local computation tasks, reconfiguring a bimodal thread of the local plurality of bimodal threads for either the first mode that executes local computation tasks or the second mode that provides remote data access to increase system throughput.

4 more elements

Dependencies are inferred from the claim text.

Concurrent distributed graph processing system with self-balance

Life of this patent

Concurrent distributed graph processing system with self-balance

Life of this patent

Abstract

Claims20