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 .
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55.
Claim Objections
Claims 1-20 are objected to because of the following informalities:
Claim 1 line 12, 14-15, 18; claim 3 line 2-3; claim 4 line 3; claim 11 line 2, 7-8; claim 12 line 4; claim 18 line 12, 14-15, 18 utilize the terms “the spGEMM’s output matrix” and "the output matrix" interchangeably. For examination purposes, Examiner interprets such terms are the same and suggest amending the claims to refer to one term for consistency.
Claim 4 line 4-5; claim 16 line 5-6 “the row” should be “the row in the output matrix” as antecedently recited.
Claim 7 line 5 “a column index of the each non-zero data” should be “a column index of each non-zero data”.
Claim 13 line 1 “An sparse matrix-matrix” should be “A sparse matrix-matrix”.
Claim 13 line 14 "the output matrix" should be "an output matrix" because there is lack of antecedent basis for such limitation.
Claim 14 line 1 “the multiplication operations" should be "the symbolic multiplication operations" as antecedently recited.
Claim 18 line 3 "the storage medium" should be "the non-transitory computer-readable storage medium" as antecedently recited.
Dependent claims are also objected for inheriting the same deficiencies in which claims they depend on.
Appropriate correction is required.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
Claims 1-12 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 1 line 12, 18 and claims 4-5 line 2 recite "the spGEMM". It is unclear whether such limitation is referring the spGEMM recited in claim 1 line 2 or the spGEMM recited in claim 1 line 3. For examination purposes, Examiner interprets such limitation as the spGEMM recited in claim 1 line 3. Examiner suggests amending claim 1 line 3 to recite “performing the spGEMM”.
Dependent claims are also rejected for inheriting the same deficiencies in which claims they depend on.
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.
Claims 1-3, 5-15, and 17-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Claim 1 recites a method claim
Under Prong One of Step 2A of the USPTO current eligibility guidance (MPEP 2106), the claim recites a method comprising: obtaining a first sparse matrix and a second sparse matrix for performing spGEMM between the first sparse matrix and the second sparse matrix; sampling a plurality of first rows in the first sparse matrix; identifying, based on indices of non-zero data in the plurality of first rows, a plurality of second rows in a second sparse matrix; performing symbolic multiplication operations between the plurality of first rows and the plurality of second rows to obtain (1) an estimated number of non-zero output data (sampled NNZ) and (2) an estimated number of floating point multiplication operations (sampled FLOP) in a hypothetical product of the plurality of first rows and the plurality of second rows; determining an estimated compression ratio of the spGEMM's output matrix based on the sampled NNZ and the sampled FLOP; determining an estimated mean row size for storing non-zero data of each row in the output matrix based at least on the estimated compression ratio and an estimated total number of floating point multiplication operations (overall FLOP). Such limitations cover mathematical calculations, relationship, and/or formula (such as obtaining, sampling, identifying and performing mathematical operations, see at least the steps 610-650 in figure 6 and [0050] describes sampling a subset of rows of matrix, identifying rows with non-zero element, [0051] describes performing symbolic or simulated multiplication, [0057] describes mathematical equation for calculating the estimated mean row size). Therefore, the claim includes limitations that fall within the “Mathematical Concepts” grouping of abstract ideas. Accordingly, the claim recites an abstract idea.
Under Prong Two of Step 2A, this judicial exception is not integrated into a practical application. The claim additionally recites a computer implemented method for memory allocation in performing spGEMM and allocating, according to the estimated mean row size, a memory space in a hardware memory for storing the output matrix before performing the spGEMM. However, the additional elements are recited at a high level of generality, i.e., as a generic system performing a generic computer function of allocating memory space for storing output matrix of spGEMM based on the calculated mean row size. Furthermore, the concept of allocating memory space in a hardware memory for storing output before performing the computation is at most considered as insignificant extra solution activity. Moreover, the step of obtaining data, such as first and second sparse matrices may also be considered as insignificant extra solution activity since it is mere data gathering. Such additional elements fail to provide a meaningful limitation on the judicial exception, and amount to no more than mere instructions to apply the exception using generic computer element. Thus, the claim is directed to an abstract idea.
Under Step 2B, as discussed with respect to Prong Two of Step 2A, the additional elements in the claim amount no more than mere instructions to apply the exception using a generic component. The same conclusion is reached in step 2B, i.e., mere instructions to apply an exception on a generic element cannot integrate a judicial exception into a practical application at step 2A or provide an inventive concept that is furnished by an element or combination of elements that is recited in the claim in addition to (beyond) the judicial exception. The steps of obtaining data and allocating memory space for storing output matrix are considered to be insignificant extra-solution activities in step 2A, and are determined to be well-understood, routine, conventional activity in the field. Court decisions cited in MPEP 2106.05(d)(II) section (i), indicate that mere receiving or transmitting data over a network, is well-understood, routing, conventional function when it is claimed in a merely generic manner, and see at least Hennessy, John L., et al. Computer Architecture : A Quantitative Approach, Elsevier Science & Technology, 2014. ProQuest Ebook Central page 93 describes load, and store operations that store result C in register R3. Thus, register R3 must be allocated to store the value of C before the addition computation. Also see page 121 figure 2.24 describes global optimizer including register allocation happens before code generator that generate executable instructions. Thus, the additional element fails to ensure the claim as a whole amount to significantly more than the judicial exception itself. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 2 further recites wherein the performing symbolic multiplication operations between the non-zero data in the plurality of first rows and non-zero data in the plurality of second rows comprises: performing a first symbolic multiplication to obtain the sampled NNZ in the hypothetical product of the plurality of first rows and the plurality of second rows; and performing a second symbolic multiplication to obtain the sampled FLOP in the hypothetical product of the plurality of first rows and the plurality of second rows, wherein the first symbolic multiplication and the second symbolic multiplication are performed based on index information of the plurality of first rows and the plurality of second rows, and in comparison to the second symbolic multiplication, the first symbolic multiplication comprises an additional column index deduplication step, Such limitations cover mathematical calculations, relationship, and/or formula (describes details of the step of performing symbolic multiplication operations, which are mathematical operations). The claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 3 further recites comprising: allocating an array of pointers respectively corresponding to the rows of the output matrix. such limitation is recited at a high level of generality and as explained above, the concept of allocating memory for data, such as pointers respectively corresponding to the rows of a matrix is considered as insignificant extra solution activity under step 2A prong two and determined to be well-understood, routine, and conventional data (see at least Hennessy, John L., et al. Computer Architecture : A Quantitative Approach, Elsevier Science & Technology, 2014. ProQuest Ebook Central page 93 describes load, and store operations that store result C in register R3. Also see page 121 figure 2.24 describes global optimizer including memory allocation happens before code generator that generate executable instructions, and also see US 20180189234 figure 1, US 20150113031 figure 4 , US 20110307685 figure 7 illustrates compressed sparse column/row format having array of pointers that corresponding to rows of matrix. The claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 5 further recites limitation covers mathematical calculations, relationship, and/or formula, such as performing the spGEMM between non-zero data of the first sparse matrix and non-zero data of the second sparse matrix, wherein a multiplication between a first non-zero data from the first sparse matrix and a second non-zero data from the second sparse matrix generates one output value (merely performing sparse matrix multiplication). Moreover, the step of determining a memory location based on indices of the first non-zero data and the second non-zero data also covers limitation that can be performed using pen and paper, where one of ordinary skill in the art can determine output location based on indices of nonzero input when performing matrix multiplication. Thus, the claim recites limitations that cover the mathematical concept / mental processes groupings of the abstract idea. Furthermore, the claim the step of determining a memory location in the allocated memory space for storing the output value; and storing the output value in the allocated memory space at the determined memory location are recited at a high level of generality, e.g., merely performing computer function using computer components, and at most considered as insignificant extra solution activity (mere data gathering) under step 2A prong two and determined to be well-understood, routine, and conventional under step 2B (see at least Hennessy, John L., et al. Computer Architecture : A Quantitative Approach, Elsevier Science & Technology, 2014, page 92 figure 2.1 describe storing result in a specific location of the memory, and figure 2.2 describes instructions to store result C to R3. Thus, in other for result output to be stored, a memory location must be determined for storing. Accordingly, the claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 6 further recites the determining the memory location for storing the output value comprises: determining a row index of the output value based on a row index of the first non-zero data; determining a column index of the output value based on a column index of the second non-zero data; and determining the memory location based on the row index of the output value and the column index of the output value. The limitations of determining a row index of the output value based on a row index of the first non-zero data; determining a column index of the output value based on a column index of the second non-zero data cover mathematical calculations, relationship, and/or formula (identifying row index and column index based on the indices of the input matrices when performing sparse matrix multiplication to generate correct result). As explained above, the step of determining the memory location in the allocated memory space for storing the output value based on row index and column index of the output value is recited at a high level of generality, e.g., merely performing computer function using computer components, and at most considered as insignificant extra solution activity (mere data gathering) under step 2A prong two and determined to be well-understood, routine, and conventional under step 2B (see at least Hennessy, John L., et al. Computer Architecture : A Quantitative Approach, Elsevier Science & Technology, 2014, page 92 figure 2.1 describe storing result in a specific location of the memory, and figure 2.2 describes instructions to store result C to R3. Thus, in other for result output to be stored, a memory location must be determined for storing. Furthermore, the step of determining a memory location based on the indices of the first and second non-zero data is merely recited as a result of the mathematical concept of performing matrix multiplication, where indices of input matrices determine the location of elements of matrix result. Thus, the claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 7 further recites wherein the identifying the plurality of second rows in the second sparse matrix based on the indices of the non-zero data in the plurality of first rows comprises: for each of the non-zero data in the plurality of first rows, identifying a second row in the second sparse matrix with a row index equal to a column index of the each non-zero data. Such limitations cover mathematical calculations, relationship, and/or formula (merely describes identifying a second row in the second sparse matrix based on nonzero data in the first rows, which is mathematical operations). The claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 8 further recites wherein the obtaining the first sparse matrix and the second sparse matrix comprises: reading non-zero data of the first and second sparse matrix stored in a compressed sparse row (CSR) format. Such limitations cover mathematical calculations, relationship, and/or formula (e.g., obtaining data in a compressed format). Furthermore, the step of reading data, such as reading data from a memory, is at most considered as insignificant extra solution activity under step 2A prong two and determined to be well-understood, routine, and conventional under step 2B (see MPEP 2106.05(d)(II) iv. Storing and retrieving information in memory). Thus, the claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 9 further recites wherein the performing the first symbolic multiplication to obtain the sampled NNZ comprises: for each first row in the plurality of first rows, retrieving index information of non-zero data in one or more of the plurality of second rows that correspond to the first row; iterating column indices of the non-zero data in one or more second rows based on the retrieved index information; inputting the column indices into a data structure for detecting duplicated column indices and obtaining a number of unique column indices; and accumulating the number of unique column indices to obtain the sampled NNZ. Such limitations cover mathematical calculations, relationship, and/or formula (describes operations of the first symbolic multiplication to obtain the sampled NNZ that performs mathematical operations to obtain a number of unique column indices and accumulating). The claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 10 further recites wherein the performing the second symbolic multiplication to obtain the sampled FLOP comprises: for each first row in the plurality of first rows, retrieving index information of non-zero data in one or more of the plurality of second rows that correspond to the first row; determining a number of indices in the one or more second rows based on the index information, wherein each of the indices corresponds to a non-zero data; and accumulating the number of indices to obtain the sampled FLOP. Such limitations cover mathematical calculations, relationship, and/or formula (describes operations of the second symbolic multiplication to obtain the sampled FLOP that performs mathematical operations to obtain a number of indices each corresponds to non-zero data and accumulate the number of indices). The claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 11 further recites wherein the determining the estimated mean row size for storing each row of the output matrix comprises: performing a symbolic multiplication between the first sparse matrix and the second sparse matrix to obtain the overall FLOP based on index information of the first sparse matrix and the second sparse matrix; determining a number of rows of the output matrix; determining the estimated mean row size for storing each row of the output matrix based on (1) the overall FLOP, (2) the number of rows of the output matrix, and (3) the estimated compression ratio. Such limitations cover mathematical calculations, relationship, and/or formula (determining the estimated mean row size by performing mathematical operations, also see the formula in [0057]) The claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 12 further recites wherein the hardware memory comprises a random-access memory (RAM) of a computer system, and the allocating the memory space in a hardware memory according to the estimated mean row size and the total number of rows of the output matrix further comprises: scaling up the estimated mean row size by a factor that is greater than one; determining a size of the memory space based on the scaled-up estimated mean row size and the total number of rows of the output matrix; and allocating the memory space based on the determined size from the RAM. Such limitations of scaling up the estimated mean row size by a factor that is greater than one; determining a size of the memory space based on the scaled-up estimated mean row size and the total number of rows of the output matrix cover mathematical calculations, relationship, and/or formula (such as scaling or multiplication to determine a size of the memory space as a result of the mathematical calculations, see at least [0071] describes the calculations to obtain total memory space). The additional elements of the hardware memory comprises a RAM of a computer system, and the step of allocating memory space based on the determined size from the RAM are recited at a high level of generality, e.g., computer component performing computer functions of allocating memory space for storing data. Furthermore, as explained above, the step of allocating memory for storing data is considered as insignificant extra solution activity under step 2A prong two and determined to be well-understood, routine and conventional under step 2B (see at least Hennessy, John L., et al. Computer Architecture : A Quantitative Approach, Elsevier Science & Technology, 2014. ProQuest Ebook Central page 93 describes load, and store operations that store result C in register R3. Thus, register R3 must be allocated to store the value of C before the addition computation. Also see page 121 figure 2.24 describes global optimizer including memory allocation happens before code generator that generate executable instructions). Thus, the claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claims 13-15, 17 recite apparatus claims that would practice the method claims 1-3, 12. Thus, they are rejected for the same reasons. Furthermore, claim 13 recites an spGEMM accelerator, a sampling circuit, a memory-size estimation circuitry, and a memory management circuitry, such additional elements are recited at a high level of generality, e.g., computer component performing computer functions of processing data, and amount to no more than mere instructions to apply the judicial exception using computer components. Thus, The claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claims 18-20 recite product claims having similar limitations as method claims 1-3. Thus, they are rejected for the same reasons. claim 18 further recites a non-transitory computer-readable storage medium for memory allocation in executing sparse matrix-matrix multiplications (spGEMM) between a first sparse matrix and a second sparse matrix, the storage medium storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations. Such additional elements are recited at a high level of generality, e.g., computer component performing computer functions of storing and processing data, and amount to no more than mere instructions to apply the judicial exception using computer components. Thus, the claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Allowable Subject Matter
Claims 1-3, 5-15, and 17-20 would be allowable if rewritten or amended to overcome the claim objection, rejections under 35 U.S.C. 112(b) and 101, set forth in this Office action.
Claims 4 and 16 would be allowable if rewritten to overcome the claim objection and rejection under 35 U.S.C. 112(b) set forth in this Office action and to include all of the limitations of the base claim and any intervening claims.
The following is a statement of reasons for the indication of allowable subject matter:
Regarding claims 1, 13 and 18, the prior art of record does not teach or suggest a combination of limitations, such as performing symbolic multiplication operations between the plurality of first rows and the plurality of second rows to obtain (1) an estimated number of non-zero output data (sampled NNZ) and (2) an estimated number of floating point multiplication operations (sampled FLOP) in a hypothetical product of the plurality of first rows and the plurality of second rows; determining an estimated compression ratio of the spGEMM's output matrix based on the sampled NNZ and the sampled FLOP; determining an estimated mean row size for storing non-zero data of each row in the output matrix based at least on the estimated compression ratio and an estimated total number of floating point multiplication operations (overall FLOP); and allocating, according to the estimated mean row size, a memory space in a hardware memory for storing the output matrix before performing the spGEMM.
Liu - NPL An Efficient GPU General Sparse Matrix-Matrix Multiplication for Irregular Data teaches an approach for memory pre-allocation for the result matrix is organized by a hybrid method that saves a large amount of global memory space and efficiently utilizes the very limited on-chip scratchpad memory. Page 374 section VI describes the design algorithm that calculate upper bound, binning, computing result matrix, and arranging data. However, Liu does not teach or suggest the combination of limitations as required in the independent claims as described above.
Gu - NPL Bandwidth-Optimized Parallel Algorithms for Sparse Matrix-Matrix Multiplication using Propagation Blocking - teaches an approach to estimate the memory requirement for output matrix C in symbolic phase as described in algorithm 3, wherein algorithm describes the calculation of NNZ and flops for memory allocation. However, Gu does not teach or suggest the sampling of first matrix and the combination of limitations as required in the independent claims as described above.
Nagasaka - NPL High-performance and Memory-saving Sparse General Matrix-Matrix Multiplication for NVIDIA Pascal GPU teaches sparse matrix multiplication and realizes that the number and pattern of non-zero elements in the output matrix depend on the input matrices and are unknown before execution. This property makes it hard to allocate memory of the output matrix. Nagasaka also proposed two strategies, one is a two-pass strategy, which counts the number of non-zero elements of output matrix first, and then allocates memory and computes. The other is that we allocate enough large memory space for output matrix and compute. Section III describes the proposed algorithm that performs steps 1-7 as described in figure 1. However, Nagasaka does not teach or suggest the combination of limitations as required in the independent claims as described above.
Du - NPL Predicting the Output Structure of Sparse Matrix Multiplication with Sampled Compression Ratio teaches an approach that predicts the output structure of sparse matrix multiplication with sampling based method, wherein the proposed method first predicts the compression ratio of SpGEMM by leveraging the number of intermediate products (denoted as FLOP) and the number of nonzero elements (denoted as NNZ) of the same sampled result matrix. And then, the predicted output structure is obtained by dividing the FLOP per output row by the predicted compression ratio. Section IV(A) describes the sampling method includes random sampling samples from input matrix, IV(C)-(D) describes computation of NNZ of the sampled data and FLOP, and compression ratio.
Zhang - US 20240411834 teaches in spGEMM, the pattern and number of non-zero elements of the output matrix is unknown before computation. But the memory allocation of the output matrix should be decided ahead of time. One way is to allocate large enough memory space, which might be inefficient. The other way is to use a symbolic-numeric method (e.g., Algorithm 1 in FIG. 1) to analyze output computation patterns, which is time-consuming. Alternatively, recently developed hash-based SpGEMM algorithm uses symbolic analysis for tiling and uses hash tables within each tile to record and lookup partial sums. The purpose of symbolic analysis is to precisely control the hash table size to reduce hash probing overhead. However, the hash operations are still the performance bottleneck due to high branch mis-prediction rate and poor spatial locality. Zhang does not teach or suggest the combination of limitations as required in the independent claims as described above.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to HUY DUONG whose telephone number is (571)272-2764. The examiner can normally be reached Mon-Friday 7:30-5:30.
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, Andrew Caldwell can be reached at (571) 272-3702. 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.
/HUY DUONG/Examiner, Art Unit 2182 (571)272-2764
Prosecution Insights