Automatic generation of multi-source breadth-first search from high-level graph language

Patent metadata

Field	Value
Publication number	US-10133827-B2
Application number	US-201514710117-A
Country	US
Kind code	B2
Filing date	May 12, 2015
Priority date	May 12, 2015
Publication date	Nov 20, 2018
Grant date	Nov 20, 2018

Abstract

Techniques are described herein for automatic generation of multi-source breadth-first search (MS-BFS) from high-level graph processing language. 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, parallel execution of the MS-BFS is regulated with batches of vertices. In an embodiment, the original software instructions are expressed in Green-Marl graph analysis language. In an embodiment, the transformed software instructions are expressed in a general purpose programming language such as C, C++, Python, or Java.

First claim

What is claimed is:

1. A method comprising:
a computer detecting that a 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 a respective source vertex of a plurality of source vertices of a graph, wherein each breadth-first search is encoded for independent execution;
based on the detecting, the computer consolidating the plurality of breadth-first searches into a simultaneous multi-source breadth-first search by transforming the first plurality of software instructions into a second plurality of software instructions that is configured to perform the simultaneous multi-source breadth-first search to determine the particular result, wherein each source vertex of the plurality of source vertices is a source of the simultaneous multi-source breadth-first search;
the computer executing, or sending or storing for execution, said second plurality of software instructions to perform said simultaneous multi-source breadth-first search.

2. The method of claim 1 wherein the first plurality of software instructions comprises a control flow loop, wherein the control flow loop is configured to iterate once per each of the plurality of source vertices, wherein the control flow loop is configured to determine the particular result, wherein the computer detecting comprises the computer identifying the control flow loop, wherein the second plurality of software instructions does not comprise the control flow loop.

3. The method of claim 1 wherein the first plurality of software instructions comprise a plurality of scalar assignments and a plurality of scalar expressions, wherein each scalar assignment writes one of a plurality of variables, wherein each scalar expression reads at least one of the plurality of variables, wherein the computer detecting comprises the computer identifying the plurality of scalar assignments and the plurality of scalar expressions, wherein the computer generating comprises: the computer generating a vector element assignment for each scalar assignment, and the computer generating comprises the computer generating a vector element expression for each scalar expression.

4. The method of claim 3 wherein the computer generating a vector element assignment comprises the computer generating an element assignment of a vector, wherein a size of the vector is based on the size of the plurality of source vertices and an amount of central processing units (CPU).

5. The method of claim 3 wherein the computer generating a vector element assignment comprises the computer generating an element assignment of a vector, wherein a size of the vector is based on a cache line size of a CPU.

6. The method of claim 1 wherein the first plurality of software instructions comprise a plurality of first function invocations, wherein each first function invocation takes a scalar argument, wherein the computer detecting comprises the computer identifying the plurality of first function invocations, wherein the computer generating comprises the computer generating, for each of the plurality of first function invocations, a second function invocation that takes a vector argument.

7. The method of claim 1 wherein the first plurality of software instructions comprise a plurality of conditional branches, wherein each conditional branch comprises a plurality of conditional paths, wherein the computer detecting comprises the computer identifying the plurality of conditional branches, wherein the computer generating comprises the computer generating, for each of the plurality of conditional branches, software instructions that determine which sources of the simultaneous multi-source breadth-first search correspond to each of the conditional paths.

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

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

10. The method of claim 1 wherein the computer generating comprises the computer generating at least one of: Java source code, Java bytecode, Python, or C++ source code.

11. The method of claim 1 wherein the first plurality of software instructions is configured to calculate at least one of: graph centrality or network flow.

12. One or more non-transient computer readable media comprising a third plurality of instructions that, when executed by one or more processors, cause:
detecting that a 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 a respective source vertex of a plurality of source vertices of a graph, wherein each breadth-first search is encoded for independent execution;
based on the detecting, consolidating the plurality of breadth-first searches into a simultaneous multi-source breadth-first search by transforming the first plurality of software instructions into a second plurality of software instructions that is configured to perform the simultaneous multi-source breadth-first search to determine the particular result, wherein each source vertex of the plurality of source vertices is a source of the simultaneous multi-source breadth-first search;
the computer executing, or sending or storing for execution, said second plurality of software instructions to perform said simultaneous multi-source breadth-first search.

13. The one or more non-transient computer readable media of claim 12 wherein the first plurality of software instructions comprises a control flow loop, wherein the control flow loop is configured to iterate once per each of the plurality of source vertices, wherein the control flow loop is configured to determine the particular result, wherein the third plurality of instructions that cause detecting further cause identifying the control flow loop, wherein the second plurality of software instructions does not comprise the control flow loop.

14. The one or more non-transient computer readable media of claim 12 wherein the first plurality of software instructions comprise a plurality of scalar assignments and a plurality of scalar expressions, wherein each scalar assignment writes one of a plurality of variables, wherein each scalar expression reads at least one of the plurality of variables, wherein the third plurality of instructions that cause detecting further cause identifying the plurality of scalar assignments and the plurality of scalar expressions, wherein the third plurality of instructions that cause generating further cause: generating a vector element assignment for each scalar assignment, and generating a vector element expression for each scalar expression.

15. The one or more non-transient computer readable media of claim 14 wherein the third plurality of instructions that cause generating a vector element assignment further cause generating an element assignment of a vector, wherein a size of the vector is based on the size of the plurality of source vertices and an amount of CPUs.

16. A computer comprising:
a memory;
a processor connected to the memory and configured to:
detect that a first plurality of software instructions stored in the memory is configured to perform a plurality of breadth-first searches to determine a particular result, wherein each breadth-first search originates at a respective source vertex of a plurality of source vertices of a graph, wherein each breadth-first search is encoded for independent execution;

based on the detecting, consolidating the

Assignees

• Oracle Int Corp

Inventors

• Then Manuel
• Hong Sungpack
• Sevenich Martin
• Chafi Hassan

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F17/30958 Primary

  Physics · mapped topic