System and method of storing and analyzing information

• US 10,146,828 B2
• Filed: 07/23/2014
• Issued: 12/04/2018
• Est. Priority Date: 07/23/2014
• Status: Active Grant

• Current Assignee: Battelle Memorial Institute
• Original Assignee: Battelle Memorial Institute
• Inventors: Feo, John T., Haglin, David J., Morari, Alessandro, Tumeo, Antonino, Villa, Oreste, Weaver, Jesse R.
• Primary Examiner(s): Ruiz, Angelica
• Application Number:
  US14/339,163
• Publication Number:
  US 20160026677A1
• Time in Patent Office: 1,595 Days
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 9/54 Interprogram communication

Abstract

A system and method of storing and analyzing information is disclosed. The system includes a compiler layer to convert user queries to data parallel executable code. The system further includes a library of multithreaded algorithms, processes, and data structures. The system also includes a multithreaded runtime library for implementing compiled code at runtime. The executable code is dynamically loaded on computing elements and contains calls to the library of multithreaded algorithms, processes, and data structures and the multithreaded runtime library.

Claims

1. A method for storing and analyzing information comprising:

receiving, at runtime, a graph database query specified in a query language;

during the runtime, converting the query to data parallel source code;

during the runtime, with a compiler layer, compiling the data parallel source code to provide executable code;

during the runtime, dynamically loading the executable code onto a plurality of computing elements;

during the runtime, executing the executable code, the executing comprising;

calling one or more methods of a graph database library, the graph database library comprising multithreaded algorithms, processes, and data structures for managing the graph database and query execution, the graph database library comprising a plurality of methods for accessing the multithreaded algorithms, processes, and data structures, one or more of the methods being called by the executable code;

calling one or more methods of a multithreaded runtime library, the multithreaded runtime library comprising a plurality of methods for implementing a global address space and thread management, the calling the one or more methods of the multithreaded runtime library comprising;

calling an API of the multithreaded runtime library to allocate memory in the global address space; and

calling an API of the multithreaded runtime library to free memory in the global address space;

calling a method of the graph database library to instantiate at least one data structure of the graph database library in the global address space, the global address space being partition between the plurality of computing elements;

with the runtime library, aggregating data requests for a computing element of the plurality of computing elements;

with the runtime library, sending the aggregated data requests to the computing element of the plurality of computing elements; and

returning query execution results in response to the graph database query.

2. The method of claim 1 wherein the query language is SPARQL and the data parallel source code is C++.

3. The method of claim 1 wherein the data structures of the library of multithreaded algorithms, processes, and data structures are implemented in a partitioned, global address space managed by the multithreaded runtime library.

4. The method of claim 1, wherein the multithreaded runtime library exposes to the library of multithreaded algorithms, processes, and data structures an Application Programming Interface (API) that permits scheduling of threads to computing elements for execution.

5. The method of claim 1, further comprising a MPI message passing layer for sending and receiving messages to and from the computing elements.

6. The method of claim 1, wherein the data structures of the library of multithreaded algorithms, processes, and data structures include an array, table, graph and dictionary with APIs to access them.

7. The method of claim 1, wherein a routine of the multithreaded graph library moves data to a local address space for manipulation and then writes them back to the global address space.

8. The method of claim 1, wherein the data structures of the multithreaded graph library are implemented using shared arrays in the global address space.

9. The method of claim 1, wherein each computing element executes an instance of the multithreaded runtime library.

10. The method of claim 1, wherein the executing further comprises:

generating at least a first worker thread, the at least a first worker thread executing application code;

generating at least a first helper thread, the at least a first helper thread managing the global address space and synchronizing commands from at least a portion of the plurality of computing elements; and

generating at least a first communication server thread, the at least a first communication server thread managing incoming and outgoing communications for at least one computing element of the plurality of computing elements.

11. The method of claim 1, wherein the executing further comprises:

creating a dictionary data structure using the multithreaded graph library; and

with the dictionary data structure, mapping vertex and edge labels of a graph to unique integer identifiers.

12. A method of implementing a graph database with an oversubscription of threads to computing elements comprising:

receiving a query, at runtime, specified in a query language;

during the runtime, converting the query to data parallel source code;

during the runtime, compiling the data parallel source code to provide data parallel executable code;

loading the data parallel executable code onto computing elements; and

executing the data parallel executable code, the executing comprising;

calling at least one method of a graph database library of multithreaded algorithms, processes, and data structures for managing a graph database and query execution, the calling at the least one method of the graph database library comprising calling a method to instantiate at least one of the data structures;

calling at least a first method and at least a second method of a multithreaded runtime library for implementing a global address space and thread management, the at least a first method allocating memory in the global address space and the at least a second method freeing memory in the global address space, wherein the at least one of the data structures is implemented in memory allocated by the at least a first method; and

returning query execution results in response to the query.

13. The method of claim 12 wherein the query language is SPARQL and the data parallel executable code is C++.

14. The method of claim 13 further comprising providing an MPI message passing layer for sending and receiving messages to and from the computing elements.

15. The method of claim 12 wherein the data structures of the library of multithreaded algorithms, processes, and data structures are implemented in a partitioned, global address space managed by the multithreaded runtime library.

16. The method of claim 15 wherein the multithreaded runtime library exposes to the library of multithreaded algorithms, processes, and data structures an API that permits allocating, accessing, and freeing data in the partitioned, global address space.

17. The method of claim 12 wherein the multithreaded runtime library exposes to the library of multithreaded algorithms, processes, and data structures an API that permits scheduling of threads to computing elements for execution.

18. The method of claim 12 wherein the data structures of the library of multithreaded algorithms, processes, and data structures include an array, table, graph and dictionary with APIs to access them.

19. A method of implementing a graph database with an oversubscription of threads to computing elements comprising:

receiving a user SPARQL query during runtime;

during the runtime, converting the user SPARQL query to a C++source code;

during the runtime, compiling the C++source code to produce an executable code;

loading the executable code onto computing elements;

executing the executable code, the executing comprising;

making program calls to a graph database library of multithreaded algorithms, processes, and data structures for managing a graph database and query execution, wherein making program calls to the graph database library comprises;

calling the graph database library to create at least one of an array, a table, a graph, and a dictionary using an API of the graph database library; and

making program calls to a multithreaded runtime library comprising a plurality of methods for implementing a global address space and thread management wherein the multithreaded runtime library exposes to the library of multithreaded algorithms, processes, and data structures an API that permits allocating, accessing, and freeing data in the partitioned global address space, the making program calls to the multithreaded runtime library comprising;

calling an API of the multithreaded runtime library to allocate memory; and

calling an API of the multithreaded runtime library to free memory;

sending and receiving messages to and from the computing elements using a MPI message passing layer; and

returning query execution results in response to the user SPARQL query.

20. The method of claim 19 wherein the data structures of the library of multithreaded algorithms, processes, and data structures are implemented in a partitioned, global address space managed by the multithreaded runtime library.

21. The method of claim 19 wherein the multithreaded runtime library exposes to the library of multithreaded algorithms, processes, and data structures an API that permits scheduling threads to computing elements.

22. The method of claim 19, wherein the executing further comprises:

creating a dictionary data structure using the multithreaded graph library; and

with the dictionary data structure, mapping vertex and edge labels of a graph to unique integer identifiers.

23. The method of claim 19, wherein the executing further comprises:

generating at least a first worker thread, the at least a first worker thread executing application code;

generating at least a first helper thread, the at least a first helper thread managing the global address space and synchronizing commands from at least a portion of the computing elements; and

generating at least a first communication server thread, the at least a first communication server thread managing incoming and outgoing communications for at least one computing element of the computing elements.

24. One or more non-transitory computer-readable media comprising computer-executable instructions that, when executed, cause a computing system to perform processing to implement a graph database query processor, the processing comprising:

at runtime, receiving a query specified in a query language;

converting the query to data parallel source code;

compiling the data parallel source code to produce data parallel executable code;

loading the executable code onto a plurality of computing elements; and

executing the executable code, the executing comprising;

making program calls to a graph database library of multithreaded algorithms, processes, and data structures for managing a graph database and query execution, the making program calls to the graph database library comprising;

calling an API of the graph database library to instantiate at least one data structure; and

making calls to a multithreaded runtime library comprising a plurality of methods for implementing a global address space and thread management, the making calls to the multithreaded runtime library comprising;

calling an API of the multithreaded runtime library to allocate memory in the global address space; and

calling an API of the multithreaded runtime library to free memory in the global address space; and

returning query execution results in response to the query.

25. The one or more computer-readable media of claim 24, wherein the data structures of the library of multithreaded algorithms, processes, and data structures are implemented in a partitioned, global address space managed by the multithreaded runtime library.

26. The one or more computer-readable media of claim 24, wherein the data structures of the library of multithreaded algorithms, processes, and data structures include an array, table, graph, and dictionary, with APIs to access them.

27. The one or more computer-readable media of claim 24, wherein the multithreaded runtime library exposes to the library of multithreaded algorithms, processes, and data structures an API that permits allocating, accessing, and freeing data in the partitioned, global address space.

28. The one or more computer-readable media of claim 24, wherein the multithreaded runtime library exposes to the library of multithreaded algorithms, processes, and data structures an API that permits scheduling threads to computing elements.