Granted Patent B2

US 10,067,910 · App. 15/201,123 · Granted Sep 4, 2018

Inventor: Rong Zhou (San Jose, CA)

Assignee: PALO ALTO RESEARCH CENTER INCORPORATED

G06F17/16G06F8/443

Abstract

Claims (56)

1. A computer-executable method for performing a general matrix-matrix multiplication (GEMM) operation on a graphics processing unit (GPU), comprising:

generating, by a computer, a plurality of kernels, wherein a respective kernel of the plurality of kernels is a function compiled for execution on the GPU, and wherein a respective kernel of the plurality of kernels is compiled with a respective maximum register count (MRC) value between zero and a predetermined number representing a maximum number of registers per thread, and wherein a thread performs operations associated with the kernel;

maintaining a set of rules, wherein a respective rule includes a mapping between dimensional parameters of respective input matrices of the GEMM operation and a corresponding kernel, wherein the mapping indicates that the corresponding kernel can perform the GEMM operation faster than any other kernel in the plurality of kernels for the dimensional parameters in the mapping based on the MRC value of the corresponding kernel;

storing data associated with two matrices in a memory device of the computer based on a row-major order or a column-major order with at least one row or column having no adjacent storage padding, wherein an adjacent storage padding is a set of bits for aligning a start address of the row or column, thereby reducing memory usage on the computer;

determining a first set of dimensional parameters of the two matrices;

loading a kernel from the plurality of kernels on the GPU for performing the GEMM operation on the GPU by looking up the first set of dimensional parameters in the set of rules; and

executing the loaded kernel on the GPU using the two matrices stored in the memory device as parameters, thereby performing the GEMM operation on the two matrices.

2. The method of claim 1 , wherein the loaded kernel is associated with a block size that is not a multiple of 16, and wherein the block size indicates a number of threads for computing a submatrix associated with the two matrices.

3. The method of claim 1 , wherein the loaded kernel is associated with at least one of a row-stop value δ x greater than 6 and a column-stop value δ y greater than 6.

4. The method of claim 3 , wherein the loaded kernel is a variable-dimension GEMM kernel with the row-stop value δ x not equal to the column-stop value δ y .

5. The method of claim 1 , further comprising maintaining a second set of rules, wherein a respective rule in the second set of rules includes a second mapping between dimensional parameters associated with respective input matrix and vector pair of a general matrix-vector multiplication (GEMV) operation and a corresponding GEMV kernel, wherein the second mapping indicates that the corresponding GEMV kernel can perform the GEMV operation faster than any other kernel among a set of GEMV kernels dimensional parameters in the second mapping based on the MRC value of the corresponding kernel.

6. The method of claim 5 , further comprising:

receiving data representing a matrix and a vector;

determining a second set of dimensional parameters of the matrix and the vector;

loading a kernel from the second set of kernels on the GPU for performing the GEMV operation on the GPU by looking up the second set of dimensional parameters in the plurality of rules; and

executing the loaded kernel on the GPU using the matrix and the vector as parameters, thereby performing the GEMV operation on the matrix and the vector.

7. The method of claim 1 , further comprising:

receiving data representing a sparse matrix and a vector; and

performing sparse matrix-vector multiplication (SpMV) on the GPU by performing operations that include applying a kernel compiled with an optimal MRC to at least one portion associated with at least one partition of the sparse matrix, wherein the portion includes a row of the sparse matrix, and wherein a respective portion is associated with a corresponding partition of the sparse matrix.

8. The method of claim 1 , further comprising:

using a kernel compiled with an optimal MRC to perform k-means clustering as an assignment kernel or as an update kernel, wherein the selected kernel compiled with the optimal MRC achieves the best performance among all k-means GPU assignment kernels or k-means GPU update kernels tested for at least one combination of test dimensions and test numbers of clusters.

9. The method of claim 1 , wherein of the GEMM operation is associated with at least one of: a machine learning operation, a data mining operation, and a graphics operation.

10. A non-transitory computer-readable storage medium storing instructions which when executed by a computer cause the computer to perform a method for general matrix-matrix multiplication (GEMM) on a graphics processing unit (GPU), the method comprising:

generating, by a computer, a plurality of kernels, wherein a respective kernel of the plurality of kernels is a function compiled for execution on the GPU, and wherein a respective kernel of the plurality of kernels is compiled with a respective maximum register count (MRC) value between zero and a predetermined number representing a maximum number of registers per thread, and wherein a thread performs operations associated with the kernel;

maintaining a set of rules, wherein a respective rule includes a mapping between dimensional parameters of respective input matrices of the GEMM operation and a corresponding kernel, wherein the mapping indicates that the corresponding kernel can perform the GEMM operation faster than any other kernel in the plurality of kernels for the dimensional parameters in the mapping based on the MRC value of the corresponding kernel;

storing data associated with two matrices in a memory device of the computer based on at a row major order or a column-major order with at least one row or column having no adjacent storage padding, wherein an adjacent storage padding is a set of bits for aligning a start address of the row or column, thereby reducing memory usage on the computer;

determining a first set of dimensional parameters of the two matrices;

loading a kernel from the plurality of kernels on the GPU for performing the GEMM operation on the GPU by looking up the first set of dimensional parameters in the set of rules; and

executing the loaded kernel on the GPU using the two matrices stored in the memory device as parameters, thereby performing the GEMM operation on the two matrices.

11. The non-transitory storage medium of claim 10 , wherein the loaded kernel is associated with a block size that is not a multiple of 16, wherein the block size indicates a number of threads for computing a submatrix associated with the two matrices.

12. The non-transitory storage medium of claim 10 , wherein the loaded kernel is associated with at least one of a row-stop value δ x greater than 6 and a column-stop value δ y greater than 6.

13. The non-transitory storage medium of claim 10 , wherein the loaded kernel is a variable-dimension GEMM kernel with the row-stop value δ x not equal to the column-stop value δ y .

14. The non-transitory storage medium of claim 10 , wherein the method further comprises maintaining a second set of rules, wherein a respective rule in the second set of rules includes a second mapping between dimensional parameters associated with respective input matrix and vector pair of a general matrix-vector multiplication (GEMV) operation and a corresponding GEMV kernel, wherein the second mapping indicates that the corresponding GEMV can perform the GEMV operation faster than any other kernel among a set of GEMV for the dimensional parameters in the second mapping based on the MRC value of the corresponding kernel.

15. The non-transitory storage medium of claim 14 , wherein the method further comprises:

receiving data representing a matrix and a vector;

determining a second set of dimensional parameters of the matrix and the vector;

loading a kernel from the second set of kernels on the GPU for performing the GEMV operation on the GPU by looking up the second set of dimensional parameters in the plurality of rules; and

executing the loaded kernel on the GPU using the matrix and the vector as parameters, thereby performing the GEMV operation on the matrix and the vector.

16. A computing system comprising:

one or more processors;

a graphics processing unit (GPU);

a memory device; and

a non-transitory computer-readable medium coupled to the one or more processors storing instructions stored that, when executed by the one or more processors, cause the computing system to perform a method for performing a general matrix-matrix multiplication (GEMM) operation on the GPU, the method comprising:

generating, by a computer, a plurality of kernels, wherein a respective kernel of the plurality of kernels is a function compiled for execution on the GPU, and wherein a respective kernel of the plurality of kernels is compiled with a respective maximum register count (MRC) value between zero and a predetermined number representing a maximum number of registers per thread, and wherein a thread performs operations associated with the kernel;

maintaining a set of rules, wherein a respective rule includes a mapping between dimensional parameters of respective input matrices of the GEMM operation and a corresponding kernel, wherein the mapping indicates that the corresponding kernel can perform the GEMM operation faster than any other kernel in the plurality of kernels for the dimensional parameters in the mapping based on the MRC value of the corresponding kernel;

storing data associated with two matrices in the memory device based on a row-major order or a column-major order with at least one row or column having no adjacent storage padding, wherein an adjacent storage padding is a set of bits for aligning a start address of the row or column, thereby reducing memory usage on the computer;

determining a first set of dimensional parameters of the two matrices;

loading a kernel from the plurality of kernels on the GPU for performing the GEMM operation on the GPU by looking up the first set of dimensional parameters in the set of rules; and

executing the loaded kernel on the GPU using the two matrices stored in the memory device as parameters, thereby performing the GEMM operation on the two matrices.

17. The computing system of claim 16 , wherein the loaded kernel is associated with at least one of a row-stop value δ x greater than 6 and a column-stop value δ y greater than 6.

18. The computing system of claim 16 , wherein the loaded kernel is a variable-dimension GEMM kernel with the row-stop value δ x not equal to the column-stop value δ y .

19. The computing system of claim 16 , wherein the method further comprises:

receiving data representing a sparse matrix and a vector; and

performing sparse matrix-vector multiplication (SpMV) on the GPU by performing operations that include applying a kernel compiled with an optimal MRC to at least one portion associated with at least one partition of the sparse matrix, wherein the portion includes a row of the sparse matrix, and wherein a respective portion is associated with a corresponding partition of the sparse matrix.

20. The computing system of claim 16 , wherein the method further comprises:

using a kernel compiled with an optimal MRC to perform k-means clustering as an assignment kernel or as an update kernel, wherein the selected kernel compiled with the optimal MRC achieves the best performance among all k-means GPU assignment kernels or k-means GPU update kernels tested for at least one combination of test dimensions and test numbers of clusters.

Assignments (10)

Continuity (1)

Cited By (3)

US 12,475,191 US 12,585,726 US 12,651,037