SYSTEM AND METHOD OF STORING AND ANALYZING INFORMATION

• US 20160026677A1
• Filed: 07/23/2014
• Published: 01/28/2016
• 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.
• Granted Patent: US 10,146,828 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 system for storing and analyzing information comprising:

a. a compiler layer to convert user queries to data parallel source code and then to executable code;

b. a library of multithreaded algorithms, processes, and data structures; and

c. a multithreaded runtime library for implementing the parallel code at runtime, wherein 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.

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

3. The system 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 system of claim 1 wherein the computing elements include at least one of the following:

cores, processors, and, nodes.

5. The system 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.

6. The system of claim 3 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 global address space.

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

8. The system 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.

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

a. converting a query language to a data parallel executable code;

b. loading the executable code onto computing elements; and

c. making program calls to a library of multithreaded algorithms, processes, and data structures and a multithreaded runtime library.

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

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

12. The method of claim 9 wherein the computing elements include at least one of the following:

cores, processors, and, nodes.

13. The method of claim 9 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.

14. The method of claim 9 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.

15. The method of claim 13 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.

16. The method of claim 9 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.

17. A system for implementing a graph database with an oversubscription of threads to computing elements comprising:

a. a compiler layer to convert a SPARQL query to a C++ source code;

b. a library of multithreaded algorithms, processes, and data structures;

c. a multithreaded runtime library for implementing the algorithms, processes, and data structures at runtime; and

d. a MPI message passing layer for sending and receiving messages to and from the computing elements.

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

19. The system of claim 17 wherein the computing elements include at least one of the following:

cores, processors, and nodes.

20. The system of claim 17 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.

21. The system of claim 18 wherein the multithreaded runtime library exposes to the library of multithreaded algorithms, processes, and data structures an Application Programming Interface (API) that permits allocating, accessing, and freeing data in the global address space.

22. The system of claim 17 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.

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

a. converting a user SPARQL query to a C++ source code and then to an executable code;

b. loading the executable code onto computing elements;

c. making program calls to a library of multithreaded algorithms, processes, and data structures and a multithreaded runtime library; and

d. providing an MPI message passing layer for sending and receiving messages to and from the computing elements.

24. The method of claim 23 wherein the computing elements include at least one of the following:

cores, processors, and nodes.

25. The method of claim 23 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 method of claim 23 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.

27. The method of claim 25 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 method of claim 23 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.