DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
The text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
Claims 21, 28, 35 and all the dependent claims thereof are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. The claims recite the limitations of "generate, for each non-zero element of a sparse matrix, an index identifying a row in a data structure into which a product from performing one or more matrix multiplication operations on a non-zero element of the sparse matrix is to be stored; perform one or more matrix multiply operations on each non-zero element of the sparse matrix and corresponding elements of a dense matrix". It is submitted that such claimed steps of "generate, for each non-zero element of a sparse matrix, an index identifying a row in a data structure into which a product from performing one or more matrix multiplication operations on a non-zero element of the sparse matrix is to be stored; perform one or more matrix multiply operations on each non-zero element of the sparse matrix and corresponding elements of a dense matrix" is/are based on matrix operations algorithm and storage of the results thereof.
The aforementioned limitations, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind depending on the complexity of the algorithm involved but for the recitation of generic computer-implementing device and its method. That is, other than reciting "generate, for each non-zero element of a sparse matrix, an index identifying a row in a data structure into which a product from performing one or more matrix multiplication operations on a non-zero element of the sparse matrix is to be stored; perform one or more matrix multiply operations on each non-zero element of the sparse matrix and corresponding elements of a dense matrix" nothing in the claim element precludes the step from practically being performed in the mind depending on the complexity of the algorithm involved. For example, but for the "generate, for each non-zero element of a sparse matrix, an index identifying a row in a data structure into which a product from performing one or more matrix multiplication operations on a non-zero element of the sparse matrix is to be stored; perform one or more matrix multiply operations on each non-zero element of the sparse matrix and corresponding elements of a dense matrix" in the context of this claim encompasses the user manually calculating the amount of use of each icon. Applicant attention is hereby directed to the fact that if a claim limitation, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of generic computer components, then it falls within the "Mental Processes" grouping of abstract ideas. Accordingly, the claim recites an abstract idea.
Moreover, this judicial exception is not integrated into a practical application. In particular, the claim only recites one additional element of: "computer-implemented device". The processor/(computer- implemented) in both steps is recited at a high-level of generality (i.e., machine computer system logic receiving a problem and solution the problem) such that it amounts no more than mere instructions to apply the exception using a generic computer component. Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. The claim is directed to an abstract idea.
Furthermore, the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the additional element of using a computer-implemented device to perform both the "matrix multiplication operations" and "sparse index map storage" steps amounts to no more than mere instructions to apply the exception using a generic computer component (i.e. logic). Mere instructions to apply an exception using a generic computer component cannot provide an inventive concept. Therefore, the claim is not patent eligible.
Finally, when considered separately and in combination, the additional elements of: "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" do not add significantly more (also known as an "inventive concept") to the judicial exception. For example, the additional elements limitations of: "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" are well-understood, routine, conventional computer functions as recognized by the court decisions listed in MPEP § 2106.05(d) (see the applied numerous prior art provided in the following rejections showing the well-understood routine character of such additional elements limitations).
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 21-25, 28-31, 35-37, 39 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Reinwald et al. (US 2015/0113031 A1 hereinafter referred to as “Reinwald”).
With respect to claim 21, Reinwald discloses, in Figs.1-6, One or more processors, comprising circuitry to: generate, for each non-zero element of a sparse matrix, an index identifying a row in a data structure into which a product from performing one or more matrix multiplication operations on a non-zero element of the sparse matrix is to be stored (see Par.[0027] wherein the estNNZs 408 may be set equal to the number of columns in the matrix times the sparsity of the matrix rounded up to the nearest integer, or round(n*p). estNNZs 408 is programmable and may be set to other values, such as round(2*n*p), or to a selected integer value; the columns array 410 may be a resizable array storing the ordered column indices of columns having non-zero entries, and the nonZeros array 412 may be a resizable array storing the non-zero values; as shown in FIG. 4, columns 3, 7, 20, 21, and 36 contain non-zero entries 1.5, 0.2, 2.5, 1.5, and 0.8 respectively; size value 414 is the current number of non-zero entries in the row, and capacity value 416 is the maximum number of non-zero entries that can be stored in the nonZeros array 412; see Par.[0019]- [0021] wherein for matrices X and Y, assume that SP(X)="p", SP(Y)="q", that there is a uniform distribution of non-zero values inside each matrix, and that all non-zero values are non-negative. When the contents of two matrices are cell-wise multiplied, ANDed (e.g., a logical AND operation is performed), added, and/or ORed (e.g., a logical OR operation is performed), it may be assumed that the two matrices (as well as the result matrix) have the same number of rows and the same number of columns); perform one or more matrix multiply operations on each non-zero element of the sparse matrix and corresponding elements of a dense matrix (see Par.[0015] wherein if the matrix has a relatively large number of non-zero entries then it may be determined to be a dense matrix, and a first type of data structure may be used to store the matrix; if the matrix has a relatively small number of non-zero entries, then it may be determined to be a sparse matrix, and a second type of data structure may be used to store the matrix; see Par.[0022] wherein the matrix may be stored in a data structure that supports a dense matrix, such as, but not limited to: a one-dimensional (1D) array (see FIG. 3 for an example 1D array data structure) that follows a row-wise order, a 1D array that follows column-wise order, or a two-dimensional (2D) array; this data structure stores the matrix in a format that allows for quick access to each entry in the matrix; block 108 may include two distinct processes, first the allocation of the memory space for a dense matrix, and second the storing of the contents of the matrix in the allocated memory space); and store one or more results of the matrix multiply operations in the data structure based at least on the index, the data structure comprising a product matrix corresponding to a transposed version of the sparse matrix and the dense matrix (see Par.[0020]-[0021] wherein the sparsity estimate of a result matrix for storing the result when the contents of matrices X and Y are cell-wise multiplied, SP(X*Y), or ANDed, SP(X&Y), may be calculated, at block 104, as the SP(X)*SP(Y) which is equal to p*q (where "*" is the symbol for multiply); the sparsity estimate of a result matrix for storing the result when the contents of matrices X and Y are added, SP(X+Y), or ORed, SP(X|Y), may be calculated as (1-(1-SP(X))*(1-SP(Y)) which is equal to (1-(1.times.p)*(1-q)); the sparsity estimate of a result matrix for storing the result when the contents of a matrix are transposed, SP(t(X)), is the same as the sparsity of the original matrix X; an estimate of the sparsity of the result matrix when the contents of matrices A and B are cell-wise multiplied or ANDed together may be calculated as: SP(A*B)=SP(A&B)=SP(A)*SP(B)=(0.0875)*(0.4)=0.35. An estimate of the sparsity of a result matrix when the contents of matrices A and B are added or ORed together may be calculated as: SP(A+B)=SP(A|B)=1-(1-SP(A))*(1-SP(B))=1-((1-0.0875)*(1-0.4))=1-((0.9125)*- (0.6))=1-0.5475=0.4525. An estimate of the sparsity of the result matrix when the contents of matrix A are transposed is SP(t(A))=0.0875. An estimate of the sparsity of a result matrix when matrix B is multiplied by matrix C may be calculated as: SP(B %*% C)=(1-(1-SP(B)*SP(C)).sup.k)=(1-(1-0.4*0.1125).sup.10) (1-0.955.sup.10) (1-0.631)=0.369).
With respect to claim 22, Reinwald discloses, in Figs.1-6, the one or more processors, wherein: the index comprises indices for columns (or rows) in the sparse matrix; and the row in the product matrix is determined based at least on the indices (see Par.[0027] wherein the estNNZs 408 may be set equal to the number of columns in the matrix times the sparsity of the matrix rounded up to the nearest integer, or round(n*p). estNNZs 408 is programmable and may be set to other values, such as round(2*n*p), or to a selected integer value. The columns array 410 may be a resizable array storing the ordered column indices of columns having non-zero entries, and the nonZeros array 412 may be a resizable array storing the non-zero values; as shown in FIG. 4, columns 3, 7, 20, 21, and 36 contain non-zero entries 1.5, 0.2, 2.5, 1.5, and 0.8 respectively. Size value 414 is the current number of non-zero entries in the row, and capacity value 416 is the maximum number of non-zero entries that can be stored in the nonZeros array 412).
With respect to claim 23, Reinwald discloses, in Figs.1-6, the one or more processors, wherein the index comprises a vector indicating elements of the product matrix (see Par.[0018]-[0020] wherein at block 104, the sparsity may be determined for an existing matrix X, having "Xm" rows, "Xn" columns, and "Xnnzs" non-zero values; the estimating may be based on the estimated sparsity of the input matrices and the type of operation being performed. For example, for matrices X and Y, assume that SP(X)="p", SP(Y)="q", that there is a uniform distribution of non-zero values inside each matrix, and that all non-zero values are non-negative; when the contents of two matrices are cell-wise multiplied, ANDed (e.g., a logical AND operation is performed), added, and/or ORed (e.g., a logical OR operation is performed), it may be assumed that the two matrices (as well as the result matrix) have the same number of rows and the same number of columns; thus, it is assumed that Xm=Ym and Xn=Yn; when calculating the product of two matrices X and Y (also referred to as multiplying matrix X by matrix Y or matrix multiplication), it may be assumed that Xn=Ym and that the number of rows in the result matrix is Xm and that the number of columns in the result matrix is Y; in this example, of matrix multiplication, matrix X has Xm rows and Xn columns and matrix Y has Ym rows and Yn columns, and k is the value of Xn which is the same as Ym; it is submitted that the index vector of a matrix refers to a way of representing or accessing elements of the matrix using their row and column positions (indices) rather than their linear position).
With respect to claim 24, Reinwald discloses, in Figs.1-6, the one or more processors, wherein the index comprises a vector indicating indices of columns of the sparse matrix (see Par.[0027] wherein the maxNNZs 406 may be set equal to the number of columns in the matrix, or n; the estNNZs 408 may be set equal to the number of columns in the matrix times the sparsity of the matrix rounded up to the nearest integer, or round(n*p). estNNZs 408 is programmable and may be set to other values, such as round(2*n*p), or to a selected integer value; the columns array 410 may be a resizable array storing the ordered column indices of columns having non-zero entries, and the nonZeros array 412 may be a resizable array storing the non-zero values).
With respect to claim 25, Reinwald discloses, in Figs.1-6, the one or more processors, wherein the one or more results comprise one or more accumulated product terms between the transposed version of the sparse matrix and the dense matrix (see Par.[0020] wherein the sparsity estimate of a result matrix for storing the result when the contents of a matrix are transposed, SP(t(X)), is the same as the sparsity of the original matrix X. In an embodiment, a sparsity estimate of a result matrix for storing the result when matrix X is multiplied by matrix Y, SP(X %*% Y) may be calculated as (1-(1-p*q).sup.k). In this example, of matrix multiplication, matrix X has Xm rows and Xn columns and matrix Y has Ym rows and Yn columns, and k is the value of Xn which is the same as Ym; see Par.[0021] wherein an estimate of the sparsity of the result matrix when the contents of matrix A are transposed is SP(t(A))=0.0875. An estimate of the sparsity of a result matrix when matrix B is multiplied by matrix C may be calculated as: SP(B %*% C)=(1-(1-SP(B)*SP(C)).sup.k)=(1-(1-0.4*0.1125).sup.10) (1-0.955.sup.10) (1-0.631)=0.369; see Par.[0015] wherein the matrix has a relatively large number of non-zero entries then it may be determined to be a dense matrix, and a first type of data structure may be used to store the matrix; if the matrix has a relatively small number of non-zero entries, then it may be determined to be a sparse matrix, and a second type of data structure may be used to store the matrix; see Par.[0022] wherein the matrix may be stored in a data structure that supports a dense matrix, such as, but not limited to: a one-dimensional (1D) array (see FIG. 3 for an example 1D array data structure) that follows a row-wise order, a 1D array that follows column-wise order, or a two-dimensional (2D) array; this data structure stores the matrix in a format that allows for quick access to each entry in the matrix. Block 108 may include two distinct processes, first the allocation of the memory space for a dense matrix, and second the storing of the contents of the matrix in the allocated memory space; see Par.[0025] wherein referring now to FIG. 3, a 1D array data structure 300 for storing a dense array is generally shown in accordance with an embodiment; FIG. 3 shows matrix A 202 from FIG. 2 stored in a 1D array data structure 300).
With respect to claim 28, Reinwald discloses, in Figs.1-6, a computer-implemented method, comprising: generating, for each non-zero element of a sparse matrix, an index identifying a row in a data structure into which a product from performing one or more matrix multiplication operations on a non-zero element of the sparse matrix is to be stored (see Par.[0027] wherein the estNNZs 408 may be set equal to the number of columns in the matrix times the sparsity of the matrix rounded up to the nearest integer, or round(n*p). estNNZs 408 is programmable and may be set to other values, such as round(2*n*p), or to a selected integer value; the columns array 410 may be a resizable array storing the ordered column indices of columns having non-zero entries, and the nonZeros array 412 may be a resizable array storing the non-zero values; as shown in FIG. 4, columns 3, 7, 20, 21, and 36 contain non-zero entries 1.5, 0.2, 2.5, 1.5, and 0.8 respectively; size value 414 is the current number of non-zero entries in the row, and capacity value 416 is the maximum number of non-zero entries that can be stored in the nonZeros array 412; see Par.[0019]- [0021] wherein for matrices X and Y, assume that SP(X)="p", SP(Y)="q", that there is a uniform distribution of non-zero values inside each matrix, and that all non-zero values are non-negative; when the contents of two matrices are cell-wise multiplied, ANDed (e.g., a logical AND operation is performed), added, and/or ORed (e.g., a logical OR operation is performed), it may be assumed that the two matrices (as well as the result matrix) have the same number of rows and the same number of columns); performing one or more matrix multiply operations on each non-zero element of the sparse matrix and corresponding elements of a dense matrix (see Par.[0015] wherein if the matrix has a relatively large number of non-zero entries then it may be determined to be a dense matrix, and a first type of data structure may be used to store the matrix; if the matrix has a relatively small number of non-zero entries, then it may be determined to be a sparse matrix, and a second type of data structure may be used to store the matrix; see Par.[0022] wherein the matrix may be stored in a data structure that supports a dense matrix, such as, but not limited to: a one-dimensional (1D) array (see FIG. 3 for an example 1D array data structure) that follows a row-wise order, a 1D array that follows column-wise order, or a two-dimensional (2D) array; this data structure stores the matrix in a format that allows for quick access to each entry in the matrix; block 108 may include two distinct processes, first the allocation of the memory space for a dense matrix, and second the storing of the contents of the matrix in the allocated memory space); and storing one or more results of the matrix multiply operations in the data structure based at least on the index, the data structure comprising a product matrix corresponding to a transposed version of the sparse matrix and the dense matrix (see Par.[0020]-[0021] wherein the sparsity estimate of a result matrix for storing the result when the contents of matrices X and Y are cell-wise multiplied, SP(X*Y), or ANDed, SP(X&Y), may be calculated, at block 104, as the SP(X)*SP(Y) which is equal to p*q (where "*" is the symbol for multiply); the sparsity estimate of a result matrix for storing the result when the contents of matrices X and Y are added, SP(X+Y), or ORed, SP(X|Y), may be calculated as (1-(1-SP(X))*(1-SP(Y)) which is equal to (1-(1.times.p)*(1-q)); the sparsity estimate of a result matrix for storing the result when the contents of a matrix are transposed, SP(t(X)), is the same as the sparsity of the original matrix X; an estimate of the sparsity of the result matrix when the contents of matrices A and B are cell-wise multiplied or ANDed together may be calculated as: SP(A*B)=SP(A&B)=SP(A)*SP(B)=(0.0875)*(0.4)=0.35. An estimate of the sparsity of a result matrix when the contents of matrices A and B are added or ORed together may be calculated as: SP(A+B)=SP(A|B)=1-(1-SP(A))*(1-SP(B))=1-((1-0.0875)*(1-0.4))=1-((0.9125)*- (0.6))=1-0.5475=0.4525. An estimate of the sparsity of the result matrix when the contents of matrix A are transposed is SP(t(A))=0.0875. An estimate of the sparsity of a result matrix when matrix B is multiplied by matrix C may be calculated as: SP(B %*% C)=(1-(1-SP(B)*SP(C)).sup.k)=(1-(1-0.4*0.1125).sup.10) (1-0.955.sup.10) (1-0.631)=0.369).
With respect to claim 29, Reinwald discloses, in Figs.1-6, the computer-implemented method, wherein: the index comprises indices of columns (or rows) of the sparse matrix containing at least one non-zero value; and the index identifies the row in the data structure based at least on the indices (see Par.[0027] wherein the estNNZs 408 may be set equal to the number of columns in the matrix times the sparsity of the matrix rounded up to the nearest integer, or round(n*p). estNNZs 408 is programmable and may be set to other values, such as round(2*n*p), or to a selected integer value. The columns array 410 may be a resizable array storing the ordered column indices of columns having non-zero entries, and the nonZeros array 412 may be a resizable array storing the non-zero values; as shown in FIG. 4, columns 3, 7, 20, 21, and 36 contain non-zero entries 1.5, 0.2, 2.5, 1.5, and 0.8 respectively. Size value 414 is the current number of non-zero entries in the row, and capacity value 416 is the maximum number of non-zero entries that can be stored in the nonZeros array 412).
With respect to claim 30, Reinwald discloses, in Figs.1-6, the computer-implemented method, wherein generating the index comprises generating a column to non-zero column vector indicating one or more storage locations in the product matrix into which product terms are to be accumulated (see Par.[0020] wherein the sparsity estimate of a result matrix for storing the result when the contents of a matrix are transposed, SP(t(X)), is the same as the sparsity of the original matrix X. In an embodiment, a sparsity estimate of a result matrix for storing the result when matrix X is multiplied by matrix Y, SP(X %*% Y) may be calculated as (1-(1-p*q).sup.k). In this example, of matrix multiplication, matrix X has Xm rows and Xn columns and matrix Y has Ym rows and Yn columns, and k is the value of Xn which is the same as Ym; see Par.[0021] wherein an estimate of the sparsity of the result matrix when the contents of matrix A are transposed is SP(t(A))=0.0875. An estimate of the sparsity of a result matrix when matrix B is multiplied by matrix C may be calculated as: SP(B %*% C)=(1-(1-SP(B)*SP(C)).sup.k)=(1-(1-0.4*0.1125).sup.10) (1-0.955.sup.10) (1-0.631)=0.369; see Par.[0015] wherein the matrix has a relatively large number of non-zero entries then it may be determined to be a dense matrix, and a first type of data structure may be used to store the matrix; if the matrix has a relatively small number of non-zero entries, then it may be determined to be a sparse matrix, and a second type of data structure may be used to store the matrix; see Par.[0022] wherein the matrix may be stored in a data structure that supports a dense matrix, such as, but not limited to: a one-dimensional (1D) array (see FIG. 3 for an example 1D array data structure) that follows a row-wise order, a 1D array that follows column-wise order, or a two-dimensional (2D) array; this data structure stores the matrix in a format that allows for quick access to each entry in the matrix. Block 108 may include two distinct processes, first the allocation of the memory space for a dense matrix, and second the storing of the contents of the matrix in the allocated memory space; see Par.[0025] wherein referring now to FIG. 3, a 1D array data structure 300 for storing a dense array is generally shown in accordance with an embodiment; FIG. 3 shows matrix A 202 from FIG. 2 stored in a 1D array data structure 300; see Par.[0041] wherein for example, the operations described herein can be performed in combination with different sparse matrix formats, such as a coordinate format, a compressed space row format, or other formats, such as a diagonal sparse matrix format or a bit-vector format).
With respect to claim 31, Reinwald discloses, in Figs.1-6, the computer-implemented method, wherein the index is based at least on one or more vectors of a compressed format representing the sparse matrix (see Par.[0004] wherein There are a variety of matrix representations in use today such as: compressed sparse row (CSR) which includes three fixed length arrays; compressed sparse column (CSC) which is similar to CSR but for columns; list of lists (LIL) which stores one list per row, where each entry stores a column index and value; and dictionary of keys (DOK) which represents non-zero values as a dictionary mapping).
With respect to claim 35, Reinwald discloses, in Figs.1-6, a system, comprising one or more processors to: generate, for each non-zero element of a sparse matrix, an index identifying a row in a data structure into which a product from performing one or more matrix multiplication operations on a non-zero element of the sparse matrix is to be stored(see Par.[0027] wherein the estNNZs 408 may be set equal to the number of columns in the matrix times the sparsity of the matrix rounded up to the nearest integer, or round(n*p). estNNZs 408 is programmable and may be set to other values, such as round(2*n*p), or to a selected integer value; the columns array 410 may be a resizable array storing the ordered column indices of columns having non-zero entries, and the nonZeros array 412 may be a resizable array storing the non-zero values; as shown in FIG. 4, columns 3, 7, 20, 21, and 36 contain non-zero entries 1.5, 0.2, 2.5, 1.5, and 0.8 respectively; size value 414 is the current number of non-zero entries in the row, and capacity value 416 is the maximum number of non-zero entries that can be stored in the nonZeros array 412; see Par.[0019]- [0021] wherein for matrices X and Y, assume that SP(X)="p", SP(Y)="q", that there is a uniform distribution of non-zero values inside each matrix, and that all non-zero values are non-negative; when the contents of two matrices are cell-wise multiplied, ANDed (e.g., a logical AND operation is performed), added, and/or ORed (e.g., a logical OR operation is performed), it may be assumed that the two matrices (as well as the result matrix) have the same number of rows and the same number of columns); perform one or more matrix multiply operations on each non-zero element of the sparse matrix and corresponding elements of a dense matrix (see Par.[0015] wherein if the matrix has a relatively large number of non-zero entries then it may be determined to be a dense matrix, and a first type of data structure may be used to store the matrix; if the matrix has a relatively small number of non-zero entries, then it may be determined to be a sparse matrix, and a second type of data structure may be used to store the matrix; see Par.[0022] wherein the matrix may be stored in a data structure that supports a dense matrix, such as, but not limited to: a one-dimensional (1D) array (see FIG. 3 for an example 1D array data structure) that follows a row-wise order, a 1D array that follows column-wise order, or a two-dimensional (2D) array; this data structure stores the matrix in a format that allows for quick access to each entry in the matrix; block 108 may include two distinct processes, first the allocation of the memory space for a dense matrix, and second the storing of the contents of the matrix in the allocated memory space); and store one or more results of the matrix multiply operations in the data structure based at least on the index, the data structure comprising a product matrix corresponding to a transposed version of the sparse matrix and the dense matrix (see Par.[0020]-[0021] wherein the sparsity estimate of a result matrix for storing the result when the contents of matrices X and Y are cell-wise multiplied, SP(X*Y), or ANDed, SP(X&Y), may be calculated, at block 104, as the SP(X)*SP(Y) which is equal to p*q (where "*" is the symbol for multiply); the sparsity estimate of a result matrix for storing the result when the contents of matrices X and Y are added, SP(X+Y), or ORed, SP(X|Y), may be calculated as (1-(1-SP(X))*(1-SP(Y)) which is equal to (1-(1.times.p)*(1-q)); the sparsity estimate of a result matrix for storing the result when the contents of a matrix are transposed, SP(t(X)), is the same as the sparsity of the original matrix X; an estimate of the sparsity of the result matrix when the contents of matrices A and B are cell-wise multiplied or ANDed together may be calculated as: SP(A*B)=SP(A&B)=SP(A)*SP(B)=(0.0875)*(0.4)=0.35. An estimate of the sparsity of a result matrix when the contents of matrices A and B are added or ORed together may be calculated as: SP(A+B)=SP(A|B)=1-(1-SP(A))*(1-SP(B))=1-((1-0.0875)*(1-0.4))=1-((0.9125)*- (0.6))=1-0.5475=0.4525. An estimate of the sparsity of the result matrix when the contents of matrix A are transposed is SP(t(A))=0.0875; an estimate of the sparsity of a result matrix when matrix B is multiplied by matrix C may be calculated as: SP(B %*% C)=(1-(1-SP(B)*SP(C)).sup.k)=(1-(1-0.4*0.1125).sup.10) (1-0.955.sup.10) (1-0.631)=0.369).
With respect to claim 36, Reinwald discloses, in Figs.1-6, the system, wherein the index comprises one or more vectors that supplement a compressed representation of the sparse matrix (see Par.[0004] wherein there are a variety of matrix representations in use today such as: compressed sparse row (CSR) which includes three fixed length arrays; compressed sparse column (CSC) which is similar to CSR but for columns; list of lists (LIL) which stores one list per row, where each entry stores a column index and value; and dictionary of keys (DOK) which represents non-zero values as a dictionary mapping).
With respect to claim 37, Reinwald discloses, in Figs.1-6, the system, wherein: the index comprises a vector indicating indices of columns (or rows) of the sparse matrix containing at least one non-zero value; and the one or more processors are further to decompress, based at least on the vector, a compressed format of the product matrix that includes only non-zero values to generate the product matrix (see Par.[0004] wherein there are a variety of matrix representations in use today such as: compressed sparse row (CSR) which includes three fixed length arrays; compressed sparse column (CSC) which is similar to CSR but for columns; list of lists (LIL) which stores one list per row, where each entry stores a column index and value; and dictionary of keys (DOK) which represents non-zero values as a dictionary mapping).
With respect to claim 39, Reinwald discloses, in Figs.1-6, the system, wherein performing the matrix multiply operations and storing the one or more results are carried out without performing an explicit matrix transpose operation on the sparse matrix (see Par.[0020]-[0021] wherein the sparsity estimate of a result matrix for storing the result when the contents of matrices X and Y are cell-wise multiplied, SP(X*Y), or ANDed, SP(X&Y), may be calculated, at block 104, as the SP(X)*SP(Y) which is equal to p*q (where "*" is the symbol for multiply); the sparsity estimate of a result matrix for storing the result when the contents of matrices X and Y are added, SP(X+Y), or ORed, SP(X|Y), may be calculated as (1-(1-SP(X))*(1-SP(Y)) which is equal to (1-(1.times.p)*(1-q)); the sparsity estimate of a result matrix for storing the result when the contents of a matrix are transposed, SP(t(X)), is the same as the sparsity of the original matrix X; an estimate of the sparsity of the result matrix when the contents of matrices A and B are cell-wise multiplied or ANDed together may be calculated as: SP(A*B)=SP(A&B)=SP(A)*SP(B)=(0.0875)*(0.4)=0.35. An estimate of the sparsity of a result matrix when the contents of matrices A and B are added or ORed together may be calculated as: SP(A+B)=SP(A|B)=1-(1-SP(A))*(1-SP(B))=1-((1-0.0875)*(1-0.4))=1-((0.9125)*- (0.6))=1-0.5475=0.4525. An estimate of the sparsity of the result matrix when the contents of matrix A are transposed is SP(t(A))=0.0875; an estimate of the sparsity of a result matrix when matrix B is multiplied by matrix C may be calculated as: SP(B %*% C)=(1-(1-SP(B)*SP(C)).sup.k)=(1-(1-0.4*0.1125).sup.10) (1-0.955.sup.10) (1-0.631)=0.369).
Claims 21-26, 28-33, 35-39 are rejected under 35 U.S.C. 102(a)(2) as being anticipated by Frumkin et al. (US 2019/0278600 A1 hereinafter referred to as “Frunkin”).
The applied reference has a common assignee: NVIDIA Corporation with the instant application. Based upon the earlier effectively filed date of the reference, it constitutes prior art under 35 U.S.C. 102(a)(2). This rejection under 35 U.S.C. 102(a)(2) might be overcome by: (1) a showing under 37 CFR 1.130(a) that the subject matter disclosed in the reference was obtained directly or indirectly from the inventor or a joint inventor of this application and is thus not prior art in accordance with 35 U.S.C. 102(b)(2)(A); (2) a showing under 37 CFR 1.130(b) of a prior public disclosure under 35 U.S.C. 102(b)(2)(B) if the same invention is not being claimed; or (3) a statement pursuant to 35 U.S.C. 102(b)(2)(C) establishing that, not later than the effective filing date of the claimed invention, the subject matter disclosed in the reference and the claimed invention were either owned by the same person or subject to an obligation of assignment to the same person or subject to a joint research agreement.
With respect to claim 21, Frumkin discloses, in Figs.1-8, One or more processors, comprising circuitry to: generate, for each non-zero element of a sparse matrix, an index identifying a row in a data structure into which a product from performing one or more matrix multiplication operations on a non-zero element of the sparse matrix is to be stored (see Par.[0027] wherein the propagation of activations for deep neural networks often use sparse weights, where the weightings themselves may be sparse matrices; such approaches can reduce the overhead of representing these sparse weights for machine learning, while improving the locality of accessing the sparse weights when needed for activation multiplication; see Par.[0028] wherein each tile can be a matrix, even potentially a sparse matrix, represented in an existing or conventional format; an advantage of such an approach is that each tile will have a small range of indices, allowing for an eight bit index representation in some embodiments; as an example, FIG. 3C illustrates an example of a sparse matrix 340 in a nested matrix format, including empty tiles (white), as well as sparse and dense tiles, where each of those tiles or submatrices is itself a sparse or dense matrix; such a nested CSR (or CSC) format can be used advantageously as discussed herein. In one embodiment each tile is a 256×256 matrix (i.e.; index 256 rows and 256 column); other dimensions are possible as well as discussed herein, such as 256×128, 128×512, etc; the indices can be reserved for entities with non-zero values); perform one or more matrix multiply operations on each non-zero element of the sparse matrix and corresponding elements of a dense matrix (see Par.[0013]-[0014] wherein various embodiments utilize a tiling approach that divides a sparse matrix into submatrices, many of which will include only zero-value entities; these empty tiles can be ignored for purposes of the computation, and only the tiles with non-zero entries processed, which reduces resource requirements for the processing; an indexing approach can be used for each entity that is a combination of the tile identifier and an offset value, which enables the values to be multiplied correctly against, for example, values of a dense matrix; see Par.[0021]-[0022] wherein machine learning networks such as deep neural networks can be sparse or involve sparse matrix operations in one or more layers of the networks. If a sparse matrix represents adjacency between objects, the multiplication of a sparse matrix by a vector (SpMV) is accumulating weights of the adjacent objects of each entry; in at least some embodiments it may be desirable to obtain a stable distribution of weights that does not change after redistribution, where finding such distributions may involve the iterative application of SpMV; if multiple independent fields are defined on the objects, like multiple species in combustion codes, then sparse by dense matrix multiplication (SpMM) can be used, as well as potentially batched sparse matrix-vector product algorithms); and store one or more results of the matrix multiply operations in the data structure based at least on the index, the data structure comprising a product matrix corresponding to a transposed version of the sparse matrix and the dense matrix (see Par.[0053] wherein the pruned, sparse weight matrices from this network are both smaller and denser than traditional sparse matrices from PDE or graphs applications which often have less than 1% density; this is an important point, as this sparsity regime has been the topic of optimization before, but algorithms are applied in various embodiments without considering the training process or recasting the sparse matrices; the non-zero distribution qualifies as random and uniform in average; the proportion of empty rows is 2% on average; finally, the top 2% largest rows are 30% larger than the median row size; the sparsity pattern of the transposed matrix was found to have similar properties; see Par.[0017] wherein the client device can include at least one processor 108 (e.g., a CPU or GPU) to execute the application and/or perform tasks on behalf of the application, and memory 110 for including non-transitory computer-readable instructions for execution by the processor; data provided to, or generated via, the ML application 106 can be stored locally to local storage 112, such as a hard drive or flash memory, among other such options; see Par.[0019]-[0020] wherein once a network is trained and successfully evaluated, the network can be stored to a model repository 126, for example, that may store different models or networks for different types of data or processing; see Par.[0023] wherein as illustrated in FIG. 2B, a majority of the data to be stored for a sparse matrix, which also includes a significant amount of corresponding metadata, corresponds to elements with zero value that do not impact the product of the matrix multiplication).
With respect to claim 22, Frumkin discloses, in Figs.1-8, the one or more processors, wherein: the index comprises indices for columns (or rows) in the sparse matrix; and the row in the product matrix is determined based at least on the indices (see Par.[0027] wherein the propagation of activations for deep neural networks often use sparse weights, where the weightings themselves may be sparse matrices; such approaches can reduce the overhead of representing these sparse weights for machine learning, while improving the locality of accessing the sparse weights when needed for activation multiplication; see Par.[0028] wherein each tile can be a matrix, even potentially a sparse matrix, represented in an existing or conventional format; an advantage of such an approach is that each tile will have a small range of indices, allowing for an eight bit index representation in some embodiments; as an example, FIG. 3C illustrates an example of a sparse matrix 340 in a nested matrix format, including empty tiles (white), as well as sparse and dense tiles, where each of those tiles or submatrices is itself a sparse or dense matrix; such a nested CSR (or CSC) format can be used advantageously as discussed herein. In one embodiment each tile is a 256×256 matrix (i.e.; index 256 rows and 256 column); other dimensions are possible as well as discussed herein, such as 256×128, 128×512, etc; the indices can be reserved for entities with non-zero values).
With respect to claim 23, Frumkin discloses, in Figs.1-8, the one or more processors, wherein the index comprises a vector indicating elements of the product matrix (see Par.[0022] wherein if multiple independent fields are defined on the objects, like multiple species in combustion codes, then sparse by dense matrix multiplication (SpMM) can be used, as well as potentially batched sparse matrix-vector product algorithms; see Par.[0030]-[0031] wherein Example algorithms can be represented in machine-independent form by directed graphs of basic blocks (“BB”). A BB representation of sparse matrix vector multiplication (SpMV) c=Ab can be specified by the following code: the standard CSR representation of A is used, with row_start indicating the start of rows and idx representing the index of elements of b).
With respect to claim 24, Frumkin discloses, in Figs.1-8, the one or more processors, wherein the index comprises a vector indicating indices of columns of the sparse matrix (see Par.[0027] wherein the propagation of activations for deep neural networks often use sparse weights, where the weightings themselves may be sparse matrices; such approaches can reduce the overhead of representing these sparse weights for machine learning, while improving the locality of accessing the sparse weights when needed for activation multiplication; see Par.[0028] wherein each tile can be a matrix, even potentially a sparse matrix, represented in an existing or conventional format; an advantage of such an approach is that each tile will have a small range of indices, allowing for an eight bit index representation in some embodiments; as an example, FIG. 3C illustrates an example of a sparse matrix 340 in a nested matrix format, including empty tiles (white), as well as sparse and dense tiles, where each of those tiles or submatrices is itself a sparse or dense matrix; such a nested CSR (or CSC) format can be used advantageously as discussed herein; in one embodiment each tile is a 256×256 matrix (i.e.; index 256 rows and 256 column); other dimensions are possible as well as discussed herein, such as 256×128, 128×512, etc; the indices can be reserved for entities with non-zero values).
With respect to claim 25, Frumkin discloses, in Figs.1-8, the one or more processors, wherein the one or more results comprise one or more accumulated product terms between the transposed version of the sparse matrix and the dense matrix (see Par.[0027] wherein the propagation of activations for deep neural networks often use sparse weights, where the weightings themselves may be sparse matrices; such approaches can reduce the overhead of representing these sparse weights for machine learning, while improving the locality of accessing the sparse weights when needed for activation multiplication; see Par.[0028] wherein each tile can be a matrix, even potentially a sparse matrix, represented in an existing or conventional format; an advantage of such an approach is that each tile will have a small range of indices, allowing for an eight bit index representation in some embodiments; as an example, FIG. 3C illustrates an example of a sparse matrix 340 in a nested matrix format, including empty tiles (white), as well as sparse and dense tiles, where each of those tiles or submatrices is itself a sparse or dense matrix; such a nested CSR (or CSC) format can be used advantageously as discussed herein; in one embodiment each tile is a 256×256 matrix (i.e.; index 256 rows and 256 column); other dimensions are possible as well as discussed herein, such as 256×128, 128×512, etc; the indices can be reserved for entities with non-zero values; see Par.[0053] wherein the pruned, sparse weight matrices from this network are both smaller and denser than traditional sparse matrices from PDE or graphs applications which often have less than 1% density; this is an important point, as this sparsity regime has been the topic of optimization before, but algorithms are applied in various embodiments without considering the training process or recasting the sparse matrices; the non-zero distribution qualifies as random and uniform in average; the proportion of empty rows is 2% on average; finally, the top 2% largest rows are 30% larger than the median row size; the sparsity pattern of the transposed matrix was found to have similar properties).
With respect to claim 26, Frumkin discloses, in Figs.1-8, the one or more processors, wherein a matrix transpose operation is avoided to generate a transposed version of the sparse matrix (see Par.[0072] wherein a model that has been over fit may perform well during evaluation but may fail to make accurate predictions on new or otherwise unclassified data; to avoid selecting an over fitted model as the best model, the training manager can reserve additional data to validate the performance of the model; see Par.[0079] wherein a robust workflow can be important to avoid overfitting of the hyperparameters as discussed elsewhere herein; cross-validation and adding Gaussian noise to the training dataset are techniques that can be useful for avoiding overfitting to any one dataset; for hyperparameter optimization it may be desirable in some embodiments to keep the training and validation sets fixed.; hyperparameters can be tuned in certain categories, as may include data preprocessing (in other words, translating words to vectors), CNN architecture definition (for example, filter sizes, number of filters), stochastic gradient descent parameters (for example, learning rate), and regularization (for example, dropout probability), among other such options).
With respect to claim 28, Frumkin discloses, in Figs.1-8, a computer-implemented method, comprising: generating, for each non-zero element of a sparse matrix, an index identifying a row in a data structure into which a product from performing one or more matrix multiplication operations on a non-zero element of the sparse matrix is to be stored (see Par.[0027] wherein the propagation of activations for deep neural networks often use sparse weights, where the weightings themselves may be sparse matrices; such approaches can reduce the overhead of representing these sparse weights for machine learning, while improving the locality of accessing the sparse weights when needed for activation multiplication; see Par.[0028] wherein each tile can be a matrix, even potentially a sparse matrix, represented in an existing or conventional format; an advantage of such an approach is that each tile will have a small range of indices, allowing for an eight bit index representation in some embodiments; as an example, FIG. 3C illustrates an example of a sparse matrix 340 in a nested matrix format, including empty tiles (white), as well as sparse and dense tiles, where each of those tiles or submatrices is itself a sparse or dense matrix; such a nested CSR (or CSC) format can be used advantageously as discussed herein. In one embodiment each tile is a 256×256 matrix (i.e.; index 256 rows and 256 column); other dimensions are possible as well as discussed herein, such as 256×128, 128×512, etc; the indices can be reserved for entities with non-zero values); performing one or more matrix multiply operations on each non-zero element of the sparse matrix and corresponding elements of a dense matrix (see Par.[0013]-[0014] wherein various embodiments utilize a tiling approach that divides a sparse matrix into submatrices, many of which will include only zero-value entities; these empty tiles can be ignored for purposes of the computation, and only the tiles with non-zero entries processed, which reduces resource requirements for the processing; an indexing approach can be used for each entity that is a combination of the tile identifier and an offset value, which enables the values to be multiplied correctly against, for example, values of a dense matrix; see Par.[0021]-[0022] wherein machine learning networks such as deep neural networks can be sparse or involve sparse matrix operations in one or more layers of the networks. If a sparse matrix represents adjacency between objects, the multiplication of a sparse matrix by a vector (SpMV) is accumulating weights of the adjacent objects of each entry; in at least some embodiments it may be desirable to obtain a stable distribution of weights that does not change after redistribution, where finding such distributions may involve the iterative application of SpMV; if multiple independent fields are defined on the objects, like multiple species in combustion codes, then sparse by dense matrix multiplication (SpMM) can be used, as well as potentially batched sparse matrix-vector product algorithms); and storing one or more results of the matrix multiply operations in the data structure based at least on the index, the data structure comprising a product matrix corresponding to a transposed version of the sparse matrix and the dense matrix (see Par.[0053] wherein the pruned, sparse weight matrices from this network are both smaller and denser than traditional sparse matrices from PDE or graphs applications which often have less than 1% density; this is an important point, as this sparsity regime has been the topic of optimization before, but algorithms are applied in various embodiments without considering the training process or recasting the sparse matrices; the non-zero distribution qualifies as random and uniform in average; the proportion of empty rows is 2% on average; finally, the top 2% largest rows are 30% larger than the median row size; the sparsity pattern of the transposed matrix was found to have similar properties; see Par.[0017] wherein the client device can include at least one processor 108 (e.g., a CPU or GPU) to execute the application and/or perform tasks on behalf of the application, and memory 110 for including non-transitory computer-readable instructions for execution by the processor; data provided to, or generated via, the ML application 106 can be stored locally to local storage 112, such as a hard drive or flash memory, among other such options; see Par.[0019]-[0020] wherein once a network is trained and successfully evaluated, the network can be stored to a model repository 126, for example, that may store different models or networks for different types of data or processing; see Par.[0023] wherein as illustrated in FIG. 2B, a majority of the data to be stored for a sparse matrix, which also includes a significant amount of corresponding metadata, corresponds to elements with zero value that do not impact the product of the matrix multiplication).
With respect to claim 29, Frumkin discloses, in Figs.1-8, the computer-implemented method, wherein: the index comprises indices of columns (or rows) of the sparse matrix containing at least one non-zero value; and the index identifies the row in the data structure based at least on the indices (see Par.[0027] wherein the propagation of activations for deep neural networks often use sparse weights, where the weightings themselves may be sparse matrices; such approaches can reduce the overhead of representing these sparse weights for machine learning, while improving the locality of accessing the sparse weights when needed for activation multiplication; see Par.[0028] wherein each tile can be a matrix, even potentially a sparse matrix, represented in an existing or conventional format; an advantage of such an approach is that each tile will have a small range of indices, allowing for an eight bit index representation in some embodiments; as an example, FIG. 3C illustrates an example of a sparse matrix 340 in a nested matrix format, including empty tiles (white), as well as sparse and dense tiles, where each of those tiles or submatrices is itself a sparse or dense matrix; such a nested CSR (or CSC) format can be used advantageously as discussed herein. In one embodiment each tile is a 256×256 matrix (i.e.; index 256 rows and 256 column); other dimensions are possible as well as discussed herein, such as 256×128, 128×512, etc; the indices can be reserved for entities with non-zero values).
With respect to claim 30, Frumkin discloses, in Figs.1-8, the computer-implemented method, wherein generating the index comprises generating a column to non-zero column vector indicating one or more storage locations in the product matrix into which product terms are to be accumulated (see Par.[0013] wherein these empty tiles can be ignored for purposes of the computation, and only the tiles with non-zero entries processed, which reduces resource requirements for the processing; an indexing approach can be used for each entity that is a combination of the tile identifier and an offset value, which enables the values to be multiplied correctly against, for example, values of a dense matrix; the tiles can be processed in parallel and the results accumulated to generate a matrix product; see Par.[0022] wherein machine learning networks such as deep neural networks can be sparse or involve sparse matrix operations in one or more layers of the networks; if a sparse matrix represents adjacency between objects, the multiplication of a sparse matrix by a vector (SpMV) is accumulating weights of the adjacent objects of each entry; see Par.[0054] wherein the elements of the individual tiles can then be multiplied 510 by the dense matrix; the multiplication of the various tiles can occur independently and at least partially in parallel or concurrently; the results of the various tile multiplications can then be accumulated 512 to generate a matrix product of the sparse matrix and the dense matrix).
With respect to claim 31, Frumkin discloses, in Figs.1-8, the computer-implemented method, wherein the index is based at least on one or more vectors of a compressed format representing the sparse matrix (see Par.[0025] wherein some formats, such as dictionary of keys (DOK) or list of lists (LIL) support efficient matrix modification, while other formats such as compressed sparse row (CSR) and compressed sparse column (CSC) support efficient access and matrix operations; see Par.[0029] wherein approaches in accordance with various embodiments can provide improved SpMM algorithms and can utilize a new compressed sparse format, referred to herein as “NestedCSR”).
With respect to claim 32, Frumkin discloses, in Figs.1-8, the computer-implemented method, wherein: the one or more results comprise accumulated product terms between the transposed version of the sparse matrix and the dense matrix; and storing the one or more results comprises accumulating the product terms into elements of the product matrix according to the index (see Par.[0013] wherein these empty tiles can be ignored for purposes of the computation, and only the tiles with non-zero entries processed, which reduces resource requirements for the processing; an indexing approach can be used for each entity that is a combination of the tile identifier and an offset value, which enables the values to be multiplied correctly against, for example, values of a dense matrix; the tiles can be processed in parallel and the results accumulated to generate a matrix product; see Par.[0022] wherein machine learning networks such as deep neural networks can be sparse or involve sparse matrix operations in one or more layers of the networks; if a sparse matrix represents adjacency between objects, the multiplication of a sparse matrix by a vector (SpMV) is accumulating weights of the adjacent objects of each entry; see Par.[0054] wherein the elements of the individual tiles can then be multiplied 510 by the dense matrix; the multiplication of the various tiles can occur independently and at least partially in parallel or concurrently; the results of the various tile multiplications can then be accumulated 512 to generate a matrix product of the sparse matrix and the dense matrix).
With respect to claim 33, Frumkin discloses, in Figs.1-8, the computer-implemented method of claim 28, wherein the performing and the storing are carried out without performing an explicit matrix transpose operation on the sparse matrix by using one or more vectors of the index to determine destination locations in the product matrix for accumulating product terms (see Par.[0013] wherein these empty tiles can be ignored for purposes of the computation, and only the tiles with non-zero entries processed, which reduces resource requirements for the processing; an indexing approach can be used for each entity that is a combination of the tile identifier and an offset value, which enables the values to be multiplied correctly against, for example, values of a dense matrix; the tiles can be processed in parallel and the results accumulated to generate a matrix product; see Par.[0022] wherein machine learning networks such as deep neural networks can be sparse or involve sparse matrix operations in one or more layers of the networks; if a sparse matrix represents adjacency between objects, the multiplication of a sparse matrix by a vector (SpMV) is accumulating weights of the adjacent objects of each entry; see Par.[0054] wherein the elements of the individual tiles can then be multiplied 510 by the dense matrix; the multiplication of the various tiles can occur independently and at least partially in parallel or concurrently; the results of the various tile multiplications can then be accumulated 512 to generate a matrix product of the sparse matrix and the dense matrix).
With respect to claim 35, Frumkin discloses, in Figs.1-8, a system, comprising one or more processors to: generate, for each non-zero element of a sparse matrix, an index identifying a row in a data structure into which a product from performing one or more matrix multiplication operations on a non-zero element of the sparse matrix is to be stored (see Par.[0027] wherein the propagation of activations for deep neural networks often use sparse weights, where the weightings themselves may be sparse matrices; such approaches can reduce the overhead of representing these sparse weights for machine learning, while improving the locality of accessing the sparse weights when needed for activation multiplication; see Par.[0028] wherein each tile can be a matrix, even potentially a sparse matrix, represented in an existing or conventional format; an advantage of such an approach is that each tile will have a small range of indices, allowing for an eight bit index representation in some embodiments; as an example, FIG. 3C illustrates an example of a sparse matrix 340 in a nested matrix format, including empty tiles (white), as well as sparse and dense tiles, where each of those tiles or submatrices is itself a sparse or dense matrix; such a nested CSR (or CSC) format can be used advantageously as discussed herein. In one embodiment each tile is a 256×256 matrix (i.e.; index 256 rows and 256 column); other dimensions are possible as well as discussed herein, such as 256×128, 128×512, etc; the indices can be reserved for entities with non-zero values); perform one or more matrix multiply operations on each non-zero element of the sparse matrix and corresponding elements of a dense matrix (see Par.[0013]-[0014] wherein various embodiments utilize a tiling approach that divides a sparse matrix into submatrices, many of which will include only zero-value entities; these empty tiles can be ignored for purposes of the computation, and only the tiles with non-zero entries processed, which reduces resource requirements for the processing; an indexing approach can be used for each entity that is a combination of the tile identifier and an offset value, which enables the values to be multiplied correctly against, for example, values of a dense matrix; see Par.[0021]-[0022] wherein machine learning networks such as deep neural networks can be sparse or involve sparse matrix operations in one or more layers of the networks. If a sparse matrix represents adjacency between objects, the multiplication of a sparse matrix by a vector (SpMV) is accumulating weights of the adjacent objects of each entry; in at least some embodiments it may be desirable to obtain a stable distribution of weights that does not change after redistribution, where finding such distributions may involve the iterative application of SpMV; if multiple independent fields are defined on the objects, like multiple species in combustion codes, then sparse by dense matrix multiplication (SpMM) can be used, as well as potentially batched sparse matrix-vector product algorithms); and store one or more results of the matrix multiply operations in the data structure based at least on the index, the data structure comprising a product matrix corresponding to a transposed version of the sparse matrix and the dense matrix (see Par.[0053] wherein the pruned, sparse weight matrices from this network are both smaller and denser than traditional sparse matrices from PDE or graphs applications which often have less than 1% density; this is an important point, as this sparsity regime has been the topic of optimization before, but algorithms are applied in various embodiments without considering the training process or recasting the sparse matrices; the non-zero distribution qualifies as random and uniform in average; the proportion of empty rows is 2% on average; finally, the top 2% largest rows are 30% larger than the median row size; the sparsity pattern of the transposed matrix was found to have similar properties; see Par.[0017] wherein the client device can include at least one processor 108 (e.g., a CPU or GPU) to execute the application and/or perform tasks on behalf of the application, and memory 110 for including non-transitory computer-readable instructions for execution by the processor; data provided to, or generated via, the ML application 106 can be stored locally to local storage 112, such as a hard drive or flash memory, among other such options; see Par.[0019]-[0020] wherein once a network is trained and successfully evaluated, the network can be stored to a model repository 126, for example, that may store different models or networks for different types of data or processing; see Par.[0023] wherein as illustrated in FIG. 2B, a majority of the data to be stored for a sparse matrix, which also includes a significant amount of corresponding metadata, corresponds to elements with zero value that do not impact the product of the matrix multiplication).
With respect to claim 36, Frumkin discloses, in Figs.1-8, the system, wherein the index comprises one or more vectors that supplement a compressed representation of the sparse matrix (see Par.[0025] wherein some formats, such as dictionary of keys (DOK) or list of lists (LIL) support efficient matrix modification, while other formats such as compressed sparse row (CSR) and compressed sparse column (CSC) support efficient access and matrix operations; see Par.[0029] wherein approaches in accordance with various embodiments can provide improved SpMM algorithms and can utilize a new compressed sparse format, referred to herein as “NestedCSR”).
With respect to claim 37, Frumkin discloses, in Figs.1-8, the system, wherein: the index comprises a vector indicating indices of columns (or rows) of the sparse matrix containing at least one non-zero value; and the one or more processors are further to decompress, based at least on the vector, a compressed format of the product matrix that includes only non-zero values to generate the product matrix (see Par.[0025] wherein some formats, such as dictionary of keys (DOK) or list of lists (LIL) support efficient matrix modification, while other formats such as compressed sparse row (CSR) and compressed sparse column (CSC) support efficient access and matrix operations; see Par.[0029] wherein approaches in accordance with various embodiments can provide improved SpMM algorithms and can utilize a new compressed sparse format, referred to herein as “NestedCSR”).
With respect to claim 38, Frumkin discloses, in Figs.1-8, the system, wherein storing the one or more results comprises accumulating product terms into storage locations that indicate elements in the product matrix (see Par.[0013] wherein these empty tiles can be ignored for purposes of the computation, and only the tiles with non-zero entries processed, which reduces resource requirements for the processing; an indexing approach can be used for each entity that is a combination of the tile identifier and an offset value, which enables the values to be multiplied correctly against, for example, values of a dense matrix; the tiles can be processed in parallel and the results accumulated to generate a matrix product; see Par.[0022] wherein machine learning networks such as deep neural networks can be sparse or involve sparse matrix operations in one or more layers of the networks; if a sparse matrix represents adjacency between objects, the multiplication of a sparse matrix by a vector (SpMV) is accumulating weights of the adjacent objects of each entry; see Par.[0054] wherein the elements of the individual tiles can then be multiplied 510 by the dense matrix; the multiplication of the various tiles can occur independently and at least partially in parallel or concurrently; the results of the various tile multiplications can then be accumulated 512 to generate a matrix product of the sparse matrix and the dense matrix).
With respect to claim 39, Frumkin discloses, in Figs.1-8, the system, wherein performing the matrix multiply operations and storing the one or more results are carried out without performing an explicit matrix transpose operation on the sparse matrix (see Par.[0014] wherein an analysis is performed with respect to a minimum number of cache misses that any Sparse Matrix by dense Matrix Multiplication algorithm (SpMM) must incur; the lower bound on cache misses can be expressed through properties of a graph represented by the sparse matrix; see Par.[0022]-[0023] wherein if a sparse matrix represents adjacency between objects, the multiplication of a sparse matrix by a vector (SpMV) is accumulating weights of the adjacent objects of each entry; in at least some embodiments it may be desirable to obtain a stable distribution of weights that does not change after redistribution, where finding such distributions may involve the iterative application of SpMV. If multiple independent fields are defined on the objects, like multiple species in combustion codes, then sparse by dense matrix multiplication (SpMM) can be used, as well as potentially batched sparse matrix-vector product algorithms).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 27, 34, 40 are rejected under 35 U.S.C. 103 as being unpatentable over Frumkin in view of Lo et al. (US 2019/0347553 A1 hereinafter referred to as “Lo”).
With respect to claim 27, Frumkin discloses all the claimed limitation of claim 21. However, Frumkin does not explicitly disclose the limitations of claim 27.
Lo discloses, in Figs.1-7, the one or more processors, wherein the circuitry is further to: apply, by a neural network, 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 is configured to reduce differences between the output and a ground truth output; and access non-zero values of the sparse matrix to compute the one or more results (see Par.[0027]-[0028] wherein the training data instance is labeled such that the ground truth output of the neural network is known; the difference or error between the observed output and the ground truth output is found and provides information about a loss function, which is passed back through the neural network layers in a back propagation or back pass; a search is made to try find a minimum of the loss function, which is a set of weights of the neural network that enable the output of the neural network to match the ground truth data; searching the loss function is achieved using gradient descent or stochastic gradient descent or in other ways, and as part of this process gradients are computed; see Par.[0035] wherein matrices are often used to represent linear transformations, that is, generalizations of linear functions such as f(x)=ax. As such, matrices can be used, for example, to project 3D images onto a two-dimensional (2D) screen or to perform calculations used to create realistic-seeming motion, among many other applications; it should be noted that the present disclosure can be applied to different matrices, such as a sparse matrix that is a matrix populated primarily with zeros, or a dense matrix that is a matrix where a significant number of elements (e.g. a majority) are not zeros; sparse matrices are useful in various application areas such as, for example, network theory where it is common to have a low density of significant data or connections represented by non-zero values interspersed throughout a far greater number of zero values; for example, the operations described herein can be performed in combination with different sparse matrix formats, such as a coordinate format, a compressed space row format, or other formats, such as a diagonal sparse matrix format or a bit-vector format).
Frumkin and Lo are analogous art because they are all directed to neural network processor, and one of ordinary skill in the art would have had a reasonable expectation of success by modifying Frumkin to include Lo because they are from the same field of endeavor.
Therefore, it would have been obvious to one of ordinary skill in the art at the time the invention was made to modify the algorithm of neural networking processor using sparse matrix in Frumkin by including a process the output according to a loss function to produce the dense matrix, wherein the dense matrix is configured to reduce differences between the output and a ground truth output as taught by Lo in order to utilize a process the output according to a loss function to produce the dense matrix, wherein the dense matrix is configured to reduce differences between the output and a ground truth output so as to obliviate problems associated to more complex large data sets in machine learning and other computing operations thereby to utilize a tiling approach that divides a sparse matrix into submatrices, many of which will include only zero-value entities whereby these empty tiles can be ignored for purposes of the computation, and only the tiles with non-zero entries processed, which reduces resource requirements for the processing.
With respect to claim 34, Frumkin discloses all the claimed limitation of claim 28. However, Frumkin does not explicitly disclose the limitations of claim 34.
Lo discloses, in Figs.1-7, the computer-implemented method, 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 as a correction matrix configured to reduce differences between the output and a ground truth output; and accessing non-zero values from the sparse matrix to compute the one or more results as a sparse parameter update matrix (see Par.[0027]-[0028] wherein the training data instance is labeled such that the ground truth output of the neural network is known; the difference or error between the observed output and the ground truth output is found and provides information about a loss function, which is passed back through the neural network layers in a back propagation or back pass; a search is made to try find a minimum of the loss function, which is a set of weights of the neural network that enable the output of the neural network to match the ground truth data; searching the loss function is achieved using gradient descent or stochastic gradient descent or in other ways, and as part of this process gradients are computed; see Par.[0035] wherein matrices are often used to represent linear transformations, that is, generalizations of linear functions such as f(x)=ax. As such, matrices can be used, for example, to project 3D images onto a two-dimensional (2D) screen or to perform calculations used to create realistic-seeming motion, among many other applications; it should be noted that the present disclosure can be applied to different matrices, such as a sparse matrix that is a matrix populated primarily with zeros, or a dense matrix that is a matrix where a significant number of elements (e.g. a majority) are not zeros; sparse matrices are useful in various application areas such as, for example, network theory where it is common to have a low density of significant data or connections represented by non-zero values interspersed throughout a far greater number of zero values; for example, the operations described herein can be performed in combination with different sparse matrix formats, such as a coordinate format, a compressed space row format, or other formats, such as a diagonal sparse matrix format or a bit-vector format).
Frumkin and Lo are analogous art because they are all directed to neural network processor, and one of ordinary skill in the art would have had a reasonable expectation of success by modifying Frumkin to include Lo because they are from the same field of endeavor.
Therefore, it would have been obvious to one of ordinary skill in the art at the time the invention was made to modify the algorithm of neural networking processor using sparse matrix in Frumkin by including a process the output according to a loss function to produce the dense matrix, wherein the dense matrix is configured to reduce differences between the output and a ground truth output as taught by Lo in order to utilize a process the output according to a loss function to produce the dense matrix, wherein the dense matrix is configured to reduce differences between the output and a ground truth output so as to obliviate problems associated to more complex large data sets in machine learning and other computing operations thereby to utilize a tiling approach that divides a sparse matrix into submatrices, many of which will include only zero-value entities whereby these empty tiles can be ignored for purposes of the computation, and only the tiles with non-zero entries processed, which reduces resource requirements for the processing.
With respect to claim 40, Frumkin discloses all the claimed limitation of claim 28. However, Frumkin does not explicitly disclose the limitations of claim 34.
Lo discloses, in Figs.1-7, the system of claim 35, wherein the one or more processors are further to: perform a neural network 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 as a correction matrix; compute the product matrix as a sparse parameter update matrix; and update the parameter matrix by combining the parameter matrix and a product of a learning rate and the sparse parameter update matrix, wherein the product is subtracted from the parameter matrix (see Par.[0027]-[0028] wherein the training data instance is labeled such that the ground truth output of the neural network is known; the difference or error between the observed output and the ground truth output is found and provides information about a loss function, which is passed back through the neural network layers in a back propagation or back pass; a search is made to try find a minimum of the loss function, which is a set of weights of the neural network that enable the output of the neural network to match the ground truth data; searching the loss function is achieved using gradient descent or stochastic gradient descent or in other ways, and as part of this process gradients are computed; see Par.[0035] wherein matrices are often used to represent linear transformations, that is, generalizations of linear functions such as f(x)=ax. As such, matrices can be used, for example, to project 3D images onto a two-dimensional (2D) screen or to perform calculations used to create realistic-seeming motion, among many other applications; it should be noted that the present disclosure can be applied to different matrices, such as a sparse matrix that is a matrix populated primarily with zeros, or a dense matrix that is a matrix where a significant number of elements (e.g. a majority) are not zeros; sparse matrices are useful in various application areas such as, for example, network theory where it is common to have a low density of significant data or connections represented by non-zero values interspersed throughout a far greater number of zero values; for example, the operations described herein can be performed in combination with different sparse matrix formats, such as a coordinate format, a compressed space row format, or other formats, such as a diagonal sparse matrix format or a bit-vector format; see Par.[0023]-[0024] wherein calculations to update weights in the neural network are performed using the second precision as part of the neural network training. Output data 212 is then generated as a final output, which in some examples are updated weights for the neural network. For example, the neural network is modified (trained) using the updated weights; see Par.[0027]-[0028], [0032]-[0034], [0038] wherein searching the loss function is achieved using gradient descent or stochastic gradient descent or in other ways, and as part of this process gradients are computed. The gradient data is used to update weights of the neural network; the computations performed during the forward pass and back propagation are less precise than the computations performed during the computations that result in the updated weights).
Frumkin and Lo are analogous art because they are all directed to neural network processor, and one of ordinary skill in the art would have had a reasonable expectation of success by modifying Frumkin to include Lo because they are from the same field of endeavor.
Therefore, it would have been obvious to one of ordinary skill in the art at the time the invention was made to modify the algorithm of neural networking processor using sparse matrix in Frumkin by including a process the output according to a loss function to produce the dense matrix, wherein the dense matrix is configured to reduce differences between the output and a ground truth output as taught by Lo in order to utilize a process the output according to a loss function to produce the dense matrix, wherein the dense matrix is configured to reduce differences between the output and a ground truth output so as to obliviate problems associated to more complex large data sets in machine learning and other computing operations thereby to utilize a tiling approach that divides a sparse matrix into submatrices, many of which will include only zero-value entities whereby these empty tiles can be ignored for purposes of the computation, and only the tiles with non-zero entries processed, which reduces resource requirements for the processing.
Citation of Pertinent Prior Art
The prior art made of record (e.g.; see PTO-892) and not relied upon is considered pertinent to applicant's disclosure.
Examiner’s Telephone/Fax Contacts
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MOULOUCOULAYE INOUSSA whose telephone number is (571)272-0596. The examiner can normally be reached Monday-Friday (10-18).
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, JEFF W NATALINI can be reached at 571-272-2266. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/Mouloucoulaye Inoussa/ Primary Examiner, Art Unit 2818
Prosecution Insights