AUTOMATIC GENERATION OF MULTI-SOURCE BREADTH-FIRST SEARCH FROM HIGH-LEVEL GRAPH LANGUAGE FOR DISTRIBUTED GRAPH PROCESSING SYSTEMS

• US 20200133663A1
• Filed: 10/31/2018
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Dwars, Martijn, Sevenich, Martin, Hong, Sungpack, Chafi, Hassan
• Granted Patent: US 10,795,672 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 8/31 Programming languages or programming paradigms
• CPC Class Codes: G06F 8/314 Parallel programming languages G06F8/313 takes precedence
• CPC Class Codes: G06F 8/452 Loops
• CPC Class Codes: G06F 8/51 Source to source
• CPC Class Codes: G06F 8/75 Structural analysis for program understanding

Abstract

Techniques are described herein for automatic generation of multi-source breadth-first search (MS-BFS) from high-level graph processing language that can be executed in a distributed computing environment. In an embodiment, a method involves a computer analyzing original software instructions. The original software instructions are configured to perform multiple breadth-first searches to determine a particular result. Each breadth-first search originates at each of a subset of vertices of a graph. Each breadth-first search is encoded for independent execution. Based on the analyzing, the computer generates transformed software instructions configured to perform a MS-BFS to determine the particular result. Each of the subset of vertices is a source of the MS-BFS. In an embodiment, the second plurality of software instructions comprises a node iteration loop and a neighbor iteration loop, and the plurality of vertices of the distributed graph comprise active vertices and neighbor vertices. The node iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, and the node iteration loop is configured to determine the particular result. The neighbor iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, and each iteration of the neighbor iteration loop is configured to activate one or more neighbor vertices of the plurality of vertices for the following iteration of the neighbor iteration loop.

Claims

1. A method comprising:

analyzing a first plurality of software instructions, wherein the first plurality of software instructions is configured to perform a plurality of breadth-first searches to determine a particular result, wherein each breadth-first search originates at each of a plurality of vertices of a distributed graph, wherein each breadth-first search is encoded for independent execution;

based on said analyzing, generating a second plurality of software instructions configured to perform a multi-source breadth-first search to determine the particular result, wherein each of the plurality of vertices is a source of the multi-source breadth-first search,

wherein the second plurality of software instructions comprises a node iteration loop and a neighbor iteration loop, wherein the plurality of vertices of the distributed graph comprise active vertices and neighbor vertices;

wherein the node iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, wherein the node iteration loop is configured to determine the particular result;

wherein the neighbor iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, wherein each iteration of the neighbor iteration loop is configured to activate one or more neighbor vertices of the plurality of vertices for the following iteration of the neighbor iteration loop.

2. The method of claim 1, wherein activating one or more neighbor vertices of the plurality of vertices for the following iteration of the neighbor iteration loop includes a first machine that stores a particular active vertex of the active vertices in local memory sending a message to a second machine that stores a particular neighbor vertex of the neighbor vertices in local memory.

3. The method of claim 2, wherein the message indicates that the particular neighbor vertex of the active vertices will be active for the following iteration of the neighbor iteration loop.

4. The method of claim 3, wherein the message is sent over a network.

5. The method of claim 1, wherein analyzing a first plurality of software instructions includes identifying batched variables and expressions, and re-writing read and write access to the batched variables and expressions.

6. The method of claim 1, wherein the second plurality of software instructions are configured to be executed by a distributed graph processing engine.

7. The method of claim 1, wherein the first plurality of software instructions comprises statements of a domain specific language (DSL).

8. The method of claim 7, wherein the DSL comprises Green-Marl.

9. The method of claim 1, wherein generating the second plurality of software instructions comprises generating at least one of:

Java source code, Java bytecode, Python, or C++ source code.

10. The method of claim 1, wherein the first plurality of software instructions is configured to calculate at least one of:

graph centrality, network flow, or all-pairs shortest paths.

11. A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, cause the one or more processors to perform a method comprising:

analyzing a first plurality of software instructions, wherein the first plurality of software instructions is configured to perform a plurality of breadth-first searches to determine a particular result, wherein each breadth-first search originates at each of a plurality of vertices of a distributed graph, wherein each breadth-first search is encoded for independent execution;

based on said analyzing, generating a second plurality of software instructions configured to perform a multi-source breadth-first search to determine the particular result, wherein each of the plurality of vertices is a source of the multi-source breadth-first search,

wherein the second plurality of software instructions comprises a node iteration loop and a neighbor iteration loop, wherein the plurality of vertices of the distributed graph comprise active vertices and neighbor vertices;

wherein the node iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, wherein the node iteration loop is configured to determine the particular result;

wherein the neighbor iteration loop is configured to iterate once per each active vertex of the plurality of vertices of the distributed graph, wherein each iteration of the neighbor iteration loop is configured to activate one or more neighbor vertices of the plurality of vertices for the following iteration of the neighbor iteration loop.

12. The non-transitory computer-readable storage medium of claim 11, wherein activating one or more neighbor vertices of the plurality of vertices for the following iteration of the neighbor iteration loop includes a first machine that stores a particular active vertex of the active vertices in local memory sending a message to a second machine that stores a particular neighbor vertex of the neighbor vertices in local memory.

13. The non-transitory computer-readable storage medium of claim 12, wherein the message indicates that the particular neighbor vertex of the active vertices will be active for the following iteration of the neighbor iteration loop.

14. The non-transitory computer-readable storage medium of claim 13, wherein the message is sent over a network.

15. The non-transitory computer-readable storage medium of claim 11, wherein analyzing a first plurality of software instructions includes identifying batched variables and expressions, and re-writing read and write access to the batched variables and expressions.

16. The non-transitory computer-readable storage medium of claim 11, wherein the second plurality of software instructions are configured to be executed by a distributed graph processing engine.

17. The non-transitory computer-readable storage medium of claim 11, wherein the first plurality of software instructions comprises statements of a domain specific language (DSL).

18. The non-transitory computer-readable storage medium of claim 17, wherein the DSL comprises Green-Marl.

19. The non-transitory computer-readable storage medium of claim 11, wherein generating the second plurality of software instructions comprises generating at least one of:

Java source code, Java bytecode, Python, or C++ source code.

20. The non-transitory computer-readable storage medium of claim 11, wherein the first plurality of software instructions is configured to calculate at least one of:

graph centrality, network flow, or all-pairs shortest paths.