Granted Patent B2

US 10,073,815 · App. 15/169,422 · Granted Sep 11, 2018

Inventor: Rong Zhou (San Jose, CA)

Assignee: PALO ALTO RESEARCH CENER INCORPORATED

G06F17/16

Abstract

Claims (59)

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

generating, by computer, a plurality of kernels, wherein a respective kernel of the plurality of kernels is a function compiled for execution on the GPU;

maintaining a plurality of rules, wherein a respective rule of the plurality of rules includes a mapping between dimensional parameters, which includes a number of rows and columns of a respective first matrix and a number of columns of a respective second matrix, 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;

storing data associated with two matrices in a memory of the computer based on at least 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 plurality of rules; and

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

2. The method of claim 1 , wherein the plurality of kernels includes a variable-K GEMM kernel, and wherein the method further comprises:

generating the variable-K GEMM kernel to perform GEMM operations in which a number of rows TB x of a matrix A that are processed by a thread block and a number of columns TB y of a matrix B that are processed by the thread block are not always the same value, TB x is equal to a multiple of a row-stop value, and TB y is equal to a multiple of a column-stop value.

3. The method of claim 1 , wherein the plurality of kernels includes a constant-K GEMM kernel, and wherein the method further comprises:

generating the constant-K GEMM kernel to perform GEMM operations in which a number of rows TB x of a matrix A that are processed by a thread block and a number of columns TB y of a matrix B that are processed by the thread block are not always the same value, TB x is equal to a multiple of a row-stop value, and TB y is equal to a multiple of a column-stop value.

4. The method of claim 1 , further comprising generating the plurality of rules, which involves:

determining, for a respective kernel of the set of kernels, computation times for performing GEMM operations for a specific set of dimensional parameters;

identifying a specific kernel for which the computation time is faster than any other kernel for the specific set of dimensional parameters; and

adding, to the plurality of rules, a rule comprising a mapping between the specific set of dimensional parameters and the specific kernel.

5. The method of claim 4 , further comprising:

using a constant parameter combined with other variable parameters to reduce a number of tests required.

6. The method of claim 4 , further comprising:

performing non-uniform sampling density along M, N, and K axes of a three-dimensional testing space to obtain a set of <M, N, K>test triples, wherein M, N, and K are associated with the specific set of dimensional parameters.

7. The method of claim 1 , further comprising storing the set of rules in a rule database that is accessible from multiple GPUs thereby allowing a respective GPU to select a kernel based on a given set of dimensional parameters without redundant tests.

8. The method of claim 1 , further comprising:

in response to determining that a lookup for the first set of dimensional parameters in the plurality of rules has failed, performing a lookup in the plurality of rules for finding a rule associated with a second set of dimensional parameters within one or more predetermined thresholds of the first set of dimensional parameters.

9. The method of claim 8 , further comprising using a non-negative parameter distance function to determine a proximity of rules to select the kernel from the set of kernels for loading on the GPU.

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

selecting the kernel in a rules database based on respective numbers of columns of the two matrices.

11. The method of claim 1 , further comprising:

performing a testing operation to determine that the kernel is faster than other kernels for performing the GEMM operation on the two matrices; and

including a rule that maps the first set of dimensional parameters to the kernel in the set of rules.

12. The method of claim 1 , further comprising:

using multiple dimensions of a thread grid of the GPU to encode a coordinate of a thread block, thereby increasing a number of rows or columns of matrices used in the GEMM operation.

13. The method of claim 1 , wherein the GEMM operation is performed as part of of a machine learning operation or a data mining operation using the GPU.

14. The method of claim 1 , wherein, among the plurality of kernels, the selected kernel performs the GEMM operation for the first set of dimensional parameters of the two matrices in a least amount of time.

15. The method of claim 1 , further comprising storing running sums associated with a respective thread of the GEMM operation in on-chip registers of the GPU.

16. 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) operation on a graphics processing unit (GPU), the method comprising:

generating a plurality of kernels, wherein a respective kernel of the plurality of kernels is a function compiled for execution on the GPU;

maintaining a plurality of rules, wherein a respective rule of the plurality of rules includes a mapping between dimensional parameters, which includes a number of rows and columns of a respective first matrix and a number of columns of a respective second matrix, 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;

storing data associated with two matrices in a memory of the computer based on at least 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 plurality of rules; and

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

17. The storage medium of claim 16 , wherein the plurality of kernels includes a constant-K GEMM kernel, and wherein the method further comprises:

generating the constant-K GEMM kernel to perform GEMM operations in which a number of rows TB x of a matrix A that are processed by a thread block and a number of columns TB y of a matrix B that are processed by the thread block are not always the same value, TB x is equal to a multiple of a row-stop value, and TB y is equal to a multiple of a column-stop value.

18. The storage medium of claim 16 , wherein the method further comprises generating the plurality of rules, which involves:

determining, for a respective kernel of the set of kernels, computation times for performing GEMM operations for a specific set of dimensional parameters;

identifying a specific kernel for which the computation time is faster than any other kernel for the specific set of dimensional parameters; and

adding, to the plurality of rules, a rule comprising a mapping between the specific set of dimensional parameters and the specific kernel.

19. A computing system comprising:

a graphics processing unit (GPU);

one or more processors;

a memory; 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 a plurality of kernels, wherein a respective kernel of the plurality of kernels is a function compiled for execution on the GPU;

maintaining a plurality of rules, wherein a respective rule of the plurality of rules includes a mapping between dimensional parameters, which includes a number of rows and columns of a respective first matrix and a number of columns of a respective second matrix, 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;

storing data associated with two matrices in the memory of the computer based on at least a row-major order and 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 plurality of rules; and

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

20. The computing system of claim 19 , wherein the plurality of kernels includes a variable-K GEMM kernel, and wherein the method further comprises:

generating the variable-K GEMM kernel to perform GEMM operations in which the number of rows TB x of a matrix A that are processed by a thread block and the number of columns TB y of a matrix B that are processed by the thread block are not always the same value, TB x is equal to a multiple of a row-stop value, and TB y is equal to a multiple of a column-stop value.

Assignments (10)

Continuity (1)

Cited By (10)

US 12,260,213 US 12,282,526 US 12,282,773 US 12,314,717 US 12,346,403 US 12,475,191 US 12,536,020 US 12,585,726 US 12,650,839 US 12,651,037