Adaptive tile matrix representation and multiplication

Patent metadata

Field	Value
Publication number	US-10061748-B2
Application number	US-201514966860-A
Country	US
Kind code	B2
Filing date	Dec 11, 2015
Priority date	Dec 11, 2015
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

Abstract

According to some embodiments, matrix A data may be loaded into a temporary, unordered starting representation that contains coordinates and values for each element of matrix A. Z-curve ordering of matrix A may be performed to create a two-dimensional density map of matrix A by counting matrix elements that are contained in logical two-dimensional block cells of a given size. A quad-tree recursion may be executed on the two-dimensional density map structure in reduced Z-space to identify areas of different densities in the two dimensional matrix space. An adaptive tile matrix representation of input matrix A may then be created. According to some embodiments, an adaptive tile matrix multiplication operation may perform dynamic tile-granular optimization based on density estimates and a cost model.

First claim

What is claimed is:

1. A computer processing system, comprising:
an in-memory column store containing big data analytic information;
a real-time analytics, interactive data exploration and application platform coupled to the in-memory column store;
a communication device coupled to the real-time analytics, interactive data exploration and application platform to receive a raw input matrix A associated with the big data analytic information contained in the in-memory column store; and
an adaptive tile matrix engine, coupled to the communication device, including:
a memory storing processor-executable program code, and
a multi-core computer processor to execute the processor-executable program code in order to cause the adaptive tile matrix engine to:
load matrix A data into a temporary, unordered starting representation that contains coordinates and values for each element of matrix A,
perform Z-curve ordering of matrix A and create a two-dimensional density map of matrix A by counting matrix elements that are contained in logical two-dimensional block cells of a given size,
execute a quad-tree recursion on the two-dimensional density map structure in reduced Z-space to identify areas of different densities in the two dimensional matrix space,
create an adaptive tile matrix representation of input matrix A,
execute an adaptive tile matrix multiplication operation that performs dynamic tile-granular optimization based on density estimates and a cost mode, wherein the adaptive tile matrix multiplication operation utilizes multiple sockets of the multi-core computer processor executing in parallel, and
transmit an indication of a result of said adaptive tile matrix multiplication operation to the real-time analytics, interactive data exploration and application platform.

2. The system of claim 1 , wherein the adaptive tile matrix representation includes adaptive tiles that store large sparse and dense matrices of an individual non-zero pattern.

3. The system of claim 2 , wherein tiles with lower densities utilize a compressed sparse row format.

4. The system of claim 1 , wherein a maximum adaptive matrix tile size is selected based at least in part on a size of a last level cache.

5. The system of claim 1 , wherein a maximum adaptive matrix tile size is selected based at least in part on a width of accumulator arrays used in a sparse matrix multiplication kernel.

6. The system of claim 1 , wherein the Z-curve ordering of matrix A comprises a locality-aware element re-ordering.

7. The system of claim 1 , wherein the adaptive tile matrix representation is used to determine a cosine similarity matrix for a plurality of electronic documents.

8. A computer-implemented method, comprising:
accessing, by a real-time analytics, interactive data exploration and application platform, big data analytic information contained in an in-memory column store;
loading matrix A data into a temporary, unordered starting representation that contains coordinates and values for each element of matrix A, wherein matrix A is associated with the big data analytic information;
performing, by a multi-core computer processor of an adaptive tile matrix engine, Z-curve ordering of matrix A to create a two-dimensional density map of matrix A by counting matrix elements that are contained in logical two-dimensional block cells of a given size;
executing, by the multi-core computer processor of the adaptive tile matrix engine, quad-tree recursion on the two-dimensional density map structure in reduced Z-space to identify areas of different densities in the two dimensional matrix space;
creating an adaptive tile matrix representation of input matrix A;
executing an adaptive tile matrix multiplication operation that performs dynamic tile-granular optimization based on density estimates and a cost mode, wherein the adaptive tile matrix multiplication operation utilizes multiple sockets of the multi-core computer processor executing in parallel; and
transmitting an indication of a result of said adaptive tile matrix multiplication operation to the real-time analytics, interactive data exploration and application platform.

9. The method of claim 8 , wherein the adaptive tile matrix representation includes adaptive tiles that store large sparse and dense matrices of an individual non-zero pattern.

10. The method of claim 9 , wherein tiles with lower densities utilize a compressed sparse row format.

11. The method of claim 8 , wherein a maximum adaptive matrix tile size is selected based at least in part on a size of a last level cache and a width of accumulator arrays used in a sparse matrix multiplication kernel.

12. The method of claim 8 , wherein the Z-curve ordering of matrix A comprises a locality-aware element re-ordering.

13. The method of claim 8 , wherein the adaptive tile matrix representation is associated with big data stored in an in-memory column store and is used to determine a cosine similarity matrix for a plurality of electronic documents.

Assignees

• Sap Se

Inventors

• Kernert David
• Lehner Wolfgang
• Koehler Frank

Classifications

• G06F17/16 Primary

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