# US 12,008,475 B2 · Transposed sparse matrix multiply by dense matrix for neural network training > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,008,475 B2 - Document ID: US12008475B2 - Status: Granted - Kind: B2 - Application number: 16/191,201 - Filed: 2018-11-14 - Published: 2020-05-14 - Granted: 2024-06-11 - Earliest claimed: 2018-11-14 - Assignees: NVIDIA Corporation - Applicants: NVIDIA Corporation - Inventors: Hao Wu - Web page: https://patentgrep.com/patent/US12008475B2 ## CPC - G06N 3/084: Backpropagation, e.g. using gradient descent - G06N 3/045: Combinations of networks - G06N 3/048: Activation functions - G06N 3/0495: Quantised networks; Sparse networks; Compressed networks - G06N 3/0499: Feedforward networks - G06N 3/09: Supervised learning - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract Machine learning systems that implement neural networks typically operate in an inference mode or a training mode. In the training mode, inference operations are performed to help guide the training process. Inference mode operation typically involves forward propagation and intensive access to certain sparse matrices, encoded as a set of vectors. Back propagation and intensive access to transposed versions of the same sparse matrices provide training refinements. Generating a transposed version of a sparse matrix can consume significant additional memory and computation resources. In one embodiment, two additional encoding vectors are generated, providing efficient operations on sparse matrices and also on transposed representations of the same sparse matrices. In a neural network the efficient operations can reduce the amount of memory needed for backpropagation and reduce power consumption. ## Claims ### Claim 1 A computer-implemented method, comprising: causing one or more multiply operations to be performed on elements of a sparse matrix and a dense matrix based, at least in part, on a sparse matrix index map identifying the elements, on which the one or more multiply operations are to be performed; and causing results of the one or more multiply operations to be accumulated in one or more corresponding storage locations according to the sparse matrix index map. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, wherein the sparse index map includes transpose indices for columns or rows in the sparse matrix and the storage locations are determined, at least in part, using the transpose indices. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein the results comprise elements of a product matrix that is equivalent to a product of a transposed version of the sparse matrix and the dense matrix. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, further comprising: applying, by a neural network, a parameter matrix to the sparse matrix to produce an output; processing the output according to a loss function to produce the dense matrix, wherein the dense matrix reduces differences between the output and a ground truth output; and accessing non-zero values of the sparse matrix to compute the results. ### Claim 5 (depends on 4) The computer implemented method of claim 4, further comprising updating the parameter matrix by combining the parameter matrix and a product of a learning rate and the product matrix. ### Claim 6 (depends on 5) The computer implemented method of claim 5, wherein the product is subtracted from the parameter matrix. ### Claim 7 (depends on 4) The computer implemented method of claim 4, wherein the loss function comprises a sum of distance functions. ### Claim 8 (depends on 4) The computer implemented method of claim 4, wherein the differences between the output and the ground truth output are computed by a correction function. ### Claim 9 (depends on 4) The computer implemented method of claim 4, wherein the neural network comprises an input layer and an output layer, and the input layer receives the parameter matrix and the sparse matrix and the output layer generates the output. ### Claim 10 (depends on 1) The computer-implemented method of claim 1, wherein the sparse matrix index map comprises a second vector indicating a indices of columns in the sparse matrix containing at least one non-zero value. ### Claim 11 (depends on 10) The computer-implemented method of claim 10, further comprising accessing, based on the second vector, the storage locations to update parameters of a neural network using the product matrix. ### Claim 12 (depends on 1) The computer-implemented method of claim 1, wherein a matrix transpose operation is avoided to accumulate the results. ### Claim 13 (depends on 1) The computer-implemented method of claim 1, wherein the results comprise elements of a product matrix and the sparse matrix index map comprises a first vector indicating elements in the product matrix. ### Claim 14 (depends on 1) The computer-implemented method of claim 1, wherein the results comprise elements of a product matrix and a compressed format of the product matrix includes only non-zero values. ### Claim 15 (depends on 1) The computer-implemented method of claim 1, wherein each product term in the results is calculated from a different entry of a data vector within the sparse matrix index map, and each storage location is identified by a corresponding entry in a column to non-zero column vector within the sparse matrix index map. ### Claim 16 A system, comprising: a parallel processing unit configured to: perform multiply operations on elements of a sparse matrix and a dense matrix based, at least in part, on a sparse matrix index map identifying the elements, on which the one or more multiply operations are to be performed; and accumulate results of the one or more multiply operations in one or more corresponding storage locations according to the sparse matrix index map. ### Claim 17 (depends on 16) The system of claim 16, wherein the results comprise elements of a product matrix and the sparse matrix index map comprises a first vector indicating the storage locations. ### Claim 18 (depends on 16) The system of claim 16, wherein the sparse matrix index map comprises a second vector indicating a number of columns in the sparse matrix containing at least one non-zero value. ### Claim 19 (depends on 16) The system of claim 16, wherein the sparse index map includes transpose indices for columns or rows in the sparse matrix and the storage locations are determined, at least in part, using the transpose indices. ### Claim 20 (depends on 16) The system of claim 16, wherein the results comprise elements of a product matrix that is equivalent to a product of a transposed version of the sparse matrix and the dense matrix. ### Claim 21 (depends on 16) The system of claim 16, wherein the parallel processing unit implements a neural network. ### Claim 22 (depends on 21) The system of claim 21, wherein the neural network is configured to: apply a parameter matrix to the sparse matrix to produce an output; process the output according to a loss function to produce the dense matrix, wherein the dense matrix reduces differences between the output and a ground truth output; and access non-zero values from the sparse matrix to compute the results. ### Claim 23 (depends on 16) The system of claim 16, wherein each product term in the results is calculated from a different entry of a data vector within the sparse matrix index map, and each storage location is identified by a corresponding entry in a column to non-zero column vector within the sparse matrix index map. ### Claim 24 A non-transitory computer-readable media storing computer instructions that, when executed by one or more processors, cause the one or more processors to perform the steps of: performing multiply operations on elements of a sparse matrix and a dense matrix based, at least in part, on a sparse matrix index map identifying the elements, on which the one or more multiply operations are to be performed; and accumulating results of the one or more multiply operations in one or more corresponding storage locations according to the sparse matrix index map. ### Claim 25 (depends on 24) The non-transitory computer-readable media of claim 24, wherein the sparse index map includes transpose indices for columns or rows in the sparse matrix and the storage locations are determined, at least in part, using the transpose indices. ### Claim 26 (depends on 24) The non-transitory computer-readable media of claim 24, wherein the results comprise elements of a product matrix that is equivalent to a product of a transposed version of the sparse matrix and the dense matrix. ### Claim 27 (depends on 24) The non-transitory computer-readable media of claim 24, wherein the results comprise elements of a product matrix and the sparse matrix index map comprises a first vector indicating elements in the product matrix. ### Claim 28 (depends on 24) The non-transitory computer-readable media of claim 24, wherein the sparse matrix index map comprises a second vector indicating a indices of columns in the sparse matrix containing at least one non-zero value. ### Claim 29 (depends on 28) The non-transitory computer-readable media of claim 28, further comprising accessing, based on the second vector, the storage locations to update parameters of a neural network using the product matrix. ### Claim 30 (depends on 24) The non-transitory computer-readable media of claim 24, wherein the results comprise elements of a product matrix and the sparse matrix index map comprises a first vector indicating elements in the product matrix. ### Claim 31 (depends on 1) The computer-implemented method of claim 1, wherein the sparse matrix index map is based, at least in part, on one or more indices of a compressed matrix format. ### Claim 32 (depends on 1) The computer-implemented method of claim 1, further comprising causing the one or more multiply operations to be performed on elements of a non-transposed sparse matrix and the dense matrix based, at least in part, on the sparse matrix index map indicating one or more locations of the elements as if the non-transposed sparse matrix were transposed.