Methods, systems and apparatus to optimize sparse matrix applications

Patent metadata

Field	Value
Publication number	US-9720663-B2
Application number	US-201514750635-A
Country	US
Kind code	B2
Filing date	Jun 25, 2015
Priority date	Jun 25, 2015
Publication date	Aug 1, 2017
Grant date	Aug 1, 2017

Abstract

Methods, apparatus, systems and articles of manufacture are disclosed to optimize sparse matrix execution. An example disclosed apparatus includes a context former to identify a matrix function call from a matrix function library, the matrix function call associated with a sparse matrix, a pattern matcher to identify an operational pattern associated with the matrix function call, and a code generator to associate a function data structure with the matrix function call exhibiting the operational pattern, the function data structure stored external to the matrix function library, and facilitate a runtime link between the function data structure and the matrix function call.

First claim

What is claimed is:

1. An apparatus to optimize sparse matrix execution, comprising:
a context former to identify a matrix function call to a matrix function library, the matrix function call associated with a sparse matrix;
a pattern matcher to identify an operational pattern associated with the matrix function call;
a code generator to:
generate a matrix data structure identifying when persistent data of the sparse matrix changes, the matrix data structure stored external to the matrix function library; and
generate a function data structure associated with the matrix function call, the function data structure stored external to the matrix function library; and
generate a runtime association between the matrix data structure, the function data structure, and the matrix function call to prevent re-computation of the operational pattern during subsequent use of the matrix function call; and

a version checker to determine when the persistent data of the sparse matrix changes based on a comparison of first version information of the matrix data structure and second version information of the function data structure, at least one of the context former, the pattern matcher, the code generator, or the version checker including hardware.

2. The apparatus as defined in claim 1 , wherein the runtime association is to enable access by the matrix function call to the persistent data associated with the sparse matrix.

3. The apparatus as defined in claim 2 , wherein the version checker is to determine that the persistent data associated with the sparse matrix changes when the first version information does not match the second version information.

4. The apparatus as defined in claim 3 , wherein the first version information of the matrix data structure identifies the latest version of the persistent data of the sparse matrix.

5. The apparatus as defined in claim 4 , further including a knob reader/writer to retrieve updated persistent data from the matrix data structure when the second version information of the persistent data associated with the sparse matrix is outdated.

6. The apparatus as defined in claim 4 , further including a task graph builder to rebuild the sparse matrix when the first version information of the persistent data is outdated.

7. The apparatus as defined in claim 1 , further including a function field of the function data structure to enable one of reusing the persistent data with a consumer function or performing a memory allocation operation.

8. The apparatus as defined in claim 7 , wherein the performing of the memory allocation operation includes storing a result vector of the matrix function when the consumer function is absent.

9. The apparatus as defined in claim 7 , wherein the function field is to enable blocking of the memory allocation operation when the consumer function executes during the matrix function call.

10. The apparatus as defined in claim 1 , wherein the operational pattern to be identified by the pattern matcher includes at least one of a memory access operation, a function call sequence, or a consumer function.

11. A method to optimize sparse matrix execution, comprising:
identifying a matrix function call to a matrix function library, the matrix function call associated with a sparse matrix;
identifying an operational pattern associated with the matrix function call;
generating, by executing an instruction with a processor, a matrix data structure identifying when persistent data of the sparse matrix changes, the matrix data structure stored external to the matrix function library;
generating, by executing an instruction with the processor, a function data structure associated with the matrix function call, the function data structure stored external to the matrix function library;
determining, by executing an instruction with the processor, when the persistent data of the sparse matrix changes based on a comparison of first version data of the matrix data structure and second version data of the function data structure; and
generating, by executing an instruction with the processor, a runtime association between the matrix data structure, the function data structure, and the matrix function call to prevent re-computation of the operational pattern during subsequent use of the matrix function call.

12. The method as defined in claim 11 , further including enabling access by the matrix function call to the persistent data associated with the sparse matrix.

13. The method as defined in claim 12 , wherein the determining that the persistent data associated with the sparse matrix changes includes determining the first version data does not match the second version data.

14. The method as defined in claim 13 , wherein the version data of the matrix data structure identifies the latest version of the persistent data of the sparse matrix.

15. The method as defined in claim 14 , further including retrieving updated persistent data from the matrix data structure when the second version data of the persistent data associated with the sparse matrix is outdated.

16. The method as defined in claim 14 , further including rebuilding the sparse matrix when the first version data of the persistent data is outdated.

17. The method as defined in claim 11 , further including accessing a function field of the function data structure to enable one of reusing the persistent data with a consumer function, or performing a memory allocation operation.

18. The method as defined in claim 11 , further including identifying the operational pattern in response to identifying at least one of a memory access operation, a function call sequence, or a consumer function.

19. A tangible non-transitory machine-readable medium comprising instructions that, when executed, cause a machine to at least:
identify a matrix function call to a matrix function library, the matrix function call associated with a sparse matrix;
identify an operational pattern associated with the matrix function call;
generate a matrix data structure identifying when persistent data of the sparse matrix changes, the matrix data structure stored external to the matrix function library;
generate a function data structure associated with the matrix function call, the function data structure stored external to the matrix function library;
compare first version data of the matrix data structure and second version data of the function data structure to determine when the persistent data of the sparse matrix changes; and
generate a runtime association between the matrix data structure, the function data structure, and the matrix function call to prevent re-computation of the operational pattern during subsequent use of the matrix function call.

20. The machine-readable medium as disclosed in claim 19 , wherein the instructions, when executed, cause the machine to enable access by the matrix function call to the persistent data associated with the sparse matrix.

21. The machine-readable medium as disclosed in claim 20 , wherein the instructions, when executed, cause the machine to determine that the persistent data associated with the sparse matrix changes when the first version data does not match the second version data.

22. The machine-readable medium as disclosed in claim 21 , wherein the first version data of the matrix data structure identifies the latest version of the persistent data of the sparse matrix.

23. The machine-readable medium as disclosed in claim 22 , wherei

Assignees

• Intel Corp

Inventors

• Rong Hongbo
• Park Jong Soo
• Smelyanskiy Mikhail
• Lowney Geoff

Classifications

• G06F8/4435

  Detection or removal of dead or redundant code · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G06F9/44521

  Dynamic linking or loading; Link editing at or after load time, e.g. Java class loading · CPC title

• G06F8/443

  Optimisation · CPC title

• G06F8/4434 Primary

  Reducing the memory space required by the program code · CPC title