# US 2019/0171490 A1 · Concurrent distributed graph processing system with self-balance > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0171490 A1 - Document ID: US20190171490A1 - Status: Published application - Kind: A1 - Application number: 16/270,135 - Filed: 2019-02-07 - Published: 2019-06-06 - Earliest claimed: 2016-06-07 - Assignees: Oracle International Corporation - Applicants: Oracle International Corporation - Inventors: Thomas Manhardt; Sungpack Hong; Siegfried Depner; Jinsu Lee; Nicholas Roth; Hassan Chafi - Web page: https://patentgrep.com/patent/US20190171490A1 ## CPC - 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)} - H04L 67/10: in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) - G06F 9/5083: {Techniques for rebalancing the load in a distributed system} - G06F 9/522: {Barrier synchronisation} - G06F 11/3404: {for parallel or distributed programming} - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F 2209/5017: Task decomposition - 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) ## 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. ## Claims ### Claim 1 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 by a first subset of a local plurality of bimodal threads that are configured for computation, wherein: a second subset of the local plurality of bimodal threads are configured for communication, and each bimodal thread of the local plurality of bimodal threads may be reconfigured for either computation or communication; 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 computation or communication to increase system throughput. ### Claim 2 (depends on 1) The method of claim 1 wherein: said same application processes a logical graph; each local computation task of the plurality of local computation tasks traverses a different edge that originates from a same vertex of the logical graph. ### Claim 3 (depends on 1) The method of claim 1 further comprising the computer reporting completion of the plurality of local computation tasks by sending a single network packet. ### Claim 4 (depends on 1) The method of claim 1 wherein each local computation task of the plurality of local computation tasks implements a closure. ### Claim 5 (depends on 1) The method of claim 1 wherein: a thread pool that contains at least one bimodal thread of the local plurality of bimodal threads; the at least one bimodal thread is idle; said dispatching the plurality of local computation tasks comprises the at least one bimodal thread executes the plurality of local computation tasks. ### Claim 6 (depends on 1) The method of claim 1 wherein said dispatching the plurality of local computation tasks comprises removing the plurality of local computation tasks from an unordered backlog. ### Claim 7 (depends on 1) The method of claim 1 wherein said execution by the first subset of the local plurality of bimodal threads comprises a bimodal thread of the first subset of the local plurality of bimodal threads sends data to a second computer of the plurality of computers by appending the data onto an outbound queue to await transmission. ### Claim 8 (depends on 1) The method of claim 1 wherein: an outbound queue buffers write requests and read responses; the write requests are added to the outbound queue only by bimodal threads of the local plurality of bimodal threads that are configured for computation; the read responses are added to the outbound queue only by bimodal threads of the local plurality of bimodal threads that are configured for communication. ### Claim 9 (depends on 1) The method of claim 1 wherein said reconfiguring the bimodal thread of the local plurality of bimodal threads comprises: in response to receiving a read request from a second computer of the plurality of computers, reconfiguring the bimodal thread for communication; the bimodal thread processing the read request. ### Claim 10 (depends on 1) The method of claim 1 wherein said dispatching the plurality of local computation tasks comprises the bimodal thread executing multiple local computation tasks of the plurality of local computation tasks. ### Claim 11 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 by a first subset of a local plurality of bimodal threads that are configured for computation, wherein: a second subset of the local plurality of bimodal threads are configured for communication, and each bimodal thread of the local plurality of bimodal threads may be reconfigured for either computation or communication; 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 computation or communication to increase system throughput. ### Claim 12 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein: said same application processes a logical graph; each local computation task of the plurality of local computation tasks traverses a different edge that originates from a same vertex of the logical graph. ### Claim 13 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein the instructions further cause the computer reporting completion of the plurality of local computation tasks by sending a single network packet. ### Claim 14 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein each local computation task of the plurality of local computation tasks implements a closure. ### Claim 15 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein: a thread pool that contains at least one bimodal thread of the local plurality of bimodal threads; the at least one bimodal thread is idle; said dispatching the plurality of local computation tasks comprises the at least one bimodal thread executes the plurality of local computation tasks. ### Claim 16 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein said dispatching the plurality of local computation tasks comprises removing the plurality of local computation tasks from an unordered backlog. ### Claim 17 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein said execution by the first subset of the local plurality of bimodal threads comprises a bimodal thread of the first subset of the local plurality of bimodal threads sends data to a second computer of the plurality of computers by appending the data onto an outbound queue to await transmission. ### Claim 18 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein: an outbound queue buffers write requests and read responses; the write requests are added to the outbound queue only by bimodal threads of the local plurality of bimodal threads that are configured for computation; the read responses are added to the outbound queue only by bimodal threads of the local plurality of bimodal threads that are configured for communication. ### Claim 19 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein said reconfiguring the bimodal thread of the local plurality of bimodal threads comprises: in response to receiving a read request from a second computer of the plurality of computers, reconfiguring the bimodal thread for communication; the bimodal thread processing the read request. ### Claim 20 (depends on 11) The one or more non-transitory computer-readable media of claim 11 wherein said dispatching the plurality of local computation tasks comprises the bimodal thread executing multiple local computation tasks of the plurality of local computation tasks.