DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Objections
Claims 13-20 are objected to because of the following informalities.
Claim 13 line 25 recites “memoriesas”. This appears to be a typographical error and should possible recite “memories as”. Claims 14-17 inherit the same deficiency as claim 13 based on dependence. Claim 18 recites substantially the same element and is objected to for the same reason. Claims 19-20 inherit the same deficiency as claim 18 based on dependence.
Claim 17 lines 3-4 recite what appears to be an extraneous artifact “—FIG. 1” and should be deleted.
Appropriate correction is required.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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.
Claims 1-9, and 11-20 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Z. Du et al., Accelerating CPU0Based Sparse General Matrix Multiplication with Binary Row Merging, arXiv:2206.06611v1 [cs.DC], 14 Jun 2022, et al., (hereinafter “Du”).
Regarding claim 1, Du teaches the following:
a computer-implemented method for memory-efficient accumulation in executing sparse matrix-matrix multiplications (SpGEMM) (abstract), comprising:
obtaining, by a processor associated with a memory, a first sparse matrix and a second sparse matrix for performing SpGEMM (Algorithm 1,Require A, Bin CSR format, line 10, line 11, Section 4.1, Table 2);
allocating, by the processor from the memory, a pair of buffers that are respectively pointed by a first pointer and a second pointer (Algorithm 1 line 2, line 3, line 7, line 8, p. 6 least paragraph, thru end of paragraph p. 7);
for each first row in the first sparse matrix that comprises a plurality of non-zero elements, identifying, by the processor, a plurality of second rows in the second sparse matrix that correspond to the plurality of non-zero elements (section 2.1.3);
obtaining, by the processor, a plurality of intermediate lists computed based on each of the plurality of non-zero elements in the first row and one of the plurality of second rows that corresponds to the non-zero element of the first row (fig 1 left most lists);
storing, by the processor, the plurality of intermediate lists into the buffer pointed by the first pointer (Alg 1 line 7, line 12, section 3.1);
executing, by the processor, an iterative process comprising:
merging the plurality of intermediate lists from the buffer pointed by the first pointer into a smaller number of intermediate lists (fig 2, section 3.1);
storing the smaller number of intermediate lists into the buffer pointed by the second pointer (fig 2, Alg 1, lines 21-36);
swapping the first pointer and the second pointer (Alg 1 line 7, line 19, line 33, line 34); and
determining whether an exit condition to exit the iterative process is met, wherein the exit condition comprises whether the smaller number of intermediate lists comprises one final merged list (Alg 1 line 30); and
migrating, by the processor, the one final merged list from the buffer pointed by the first pointer to a system memory as a row of an output matrix of the SpGEMM (Alg 1 line 36).
Regarding claim 2, in addition to the teachings addressed in the claim 1 analysis, Du teaches the following:
allocating an offset buffer comprising a plurality of offsets respectively corresponding to the plurality of intermediate lists, wherein each offset points to a first unmerged element in the corresponding intermediate list (Alg 1, line 14, lines 21-31).
Regarding claim 3, in addition to the teachings addressed in the claim 2 analysis, Du teaches the following:
in response to merging the plurality of intermediate lists into the smaller number of intermediate lists, updating the offset buffer so that each offset points to an offset of a first unmerged element in one of the smaller number of intermediate lists (Alg 1 line 34).
Regarding claim 4, in addition to the teachings addressed in the claim 1 analysis, Du teaches the following:
wherein the merging the plurality of intermediate lists from the buffer pointed by the first pointer into the smaller number of intermediate lists and storing the smaller number of intermediate lists into the buffer pointed by the second pointer comprises:
for two adjacent intermediate lists of the plurality of intermediate lists:
(1) determining two memory offsets in the buffer pointed by the first pointer, the two memory offsets pointing to the two intermediate lists respectively;
(2) determining a destination memory offset in the buffer pointed by the second pointer;
(3) retrieving, at the memory offsets of the buffer pointed by the first pointer, column indices of two elements;
(4) in response to the column indices of the two elements being same, aggregating values of the two unmerged elements to obtain an aggregated value, storing the aggregated value into a merged list starting at the destination memory offset in the buffer pointed by the second pointer;
(5) in response to the column indices of the two elements being different, storing one of the two unmerged elements that comprises a smaller value into the merged list starting at the destination memory offset in the buffer pointed by the second pointer; and
repeating steps (1)-(5) until the two intermediate lists are merged into the merged list in the buffer pointed by the second pointer (Section 3.1, image and description of figure 2 describes steps 1-5, Alg 1 with the repeating).
Regarding claim 5, in addition to the teachings addressed in the claim 1 analysis, Du teaches the following:
wherein the first sparse matrix and the second sparse matrix are stored in a compact data format, wherein the compact data format excludes zero-value data in the first sparse matrix and the second sparse matrix (Alg 1 Require A, B in CSR format, section 2.1.3).
Regarding claim 6, in addition to the teachings addressed in the claim 1 analysis, Du teaches the following:
determining a buffer size for the pair of buffers by performing a symbolic computation based on indices of non-zero elements in the first sparse matrix and row sizes of the second sparse matrix, wherein the symbolic computation estimates a maximum number of floating-point multiplication operations (FLOP) in a hypothetical multiplication between each of the plurality of first rows and the second sparse matrix (Al 1 line 1),
wherein the allocating the pair of buffers comprises:
allocating each of the pair of buffers with the buffer size (Alg 1 line 2-3, section 3.2).
Regarding claim 7, in addition to the teachings addressed in the claim 6 analysis, Du teaches the following:
wherein the symbolic computation comprises: for each of the plurality of first rows that comprises one or more non-zero elements, identifying one or more corresponding second rows from the second sparse matrix; determining a number of FLOP for the each first row based on a number of non-zero elements in the one or more corresponding second rows from the second sparse matrix; and determining the maximum number of FLOP of the plurality of first rows as the buffer size (section 3.2 2nd to last paragraph).
Regarding claim 8, in addition to the teachings addressed in the claim 1 analysis, Du teaches the following:
wherein the processor comprises a multi-core processor (Abstract first paragraph), and the method further comprises:
segmenting rows of the first sparse matrix into multiple groups of first rows according to a number of cores in the multi-core processor (section 2.1.2 last two paragraphs); and
assigning the multiple groups of first rows into the number of cores for parallel processing, wherein each core allocates a corresponding pair of buffers (section 2.1.2 last two paragraphs).
Regarding claim 9, in addition to the teachings addressed in the claim 8 analysis, Du teaches the following:
wherein the multi-core processor comprises a multi-core CPU (abstract first paragraph).
Regarding claim 11, in addition to the teachings addressed in the claim 2 analysis, Du teaches the following:
wherein the offset buffer comprises a pair of index lists respectively corresponding to the pair of buffers (Alg 1 lines 4-5).
Regarding claim 12, in addition to the teachings addressed in the claim 2 analysis, Du teaches the following:
Determining a buffer size for the offset buffer based on a maximum number of non-zero data in each row of the first sparse matrix (Alg 1 lines 4-5).
Regarding claim 13, Du teaches the following:
a system for memory-efficient accumulation to accelerate SpGEMM computations, comprising one or more processors and one or more non-transitory computer-readable memories coupled to the one or more processors and configured with instructions executable by the one or more processors to cause the system to perform operations (abstract) comprising:
obtaining a first sparse matrix and a second sparse matrix for performing SpGEMM (Algorithm 1,Require A, Bin CSR format, line 10, line 11, Section 4.1, Table 2);
allocating a pair of buffers in a cache associated with the one or more processors, the pair of buffers respectively pointed by a first pointer and a second pointer (Algorithm 1 line 2, line 3, line 7, line 8, p. 6 least paragraph, thru end of paragraph p. 7, abstract second paragraph, section 3.3, 3.3.1);
for each first row in the first sparse matrix that comprises a plurality of non-zero elements, identifying, by the processor, a plurality of second rows in the second sparse matrix that correspond to the plurality of non-zero elements (section 2.1.3);
obtaining a plurality of intermediate lists computed based on each of the plurality of non-zero elements in the first row and one of the plurality of second rows that corresponds to the non-zero element of the first row (fig 1 left most lists);
storing the plurality of intermediate lists into the buffer pointed by the first pointer (Alg 1 line 7, line 12, section 3.1);
executing an iterative process comprising:
merging the plurality of intermediate lists from the buffer pointed by the first pointer into a smaller number of intermediate lists (fig 2, section 3.1);
storing the smaller number of intermediate lists into the buffer pointed by the second pointer (fig 2, Alg 1, lines 21-36);
swapping the first pointer and the second pointer (Alg 1 line 7, line 19, line 33, line 34); and
determining whether an exit condition to exit the iterative process is met, wherein the exit condition comprises whether the smaller number of intermediate lists comprises one final merged list (Alg 1 line 30); and
migrating the one final merged list from the cache to the one or more non-transitory memoriesas a row of an output matrix of the SpGEMM (Alg 1 line 36).
Regarding claim 14, in addition to the teachings addressed in the claim 13 analysis, Du teaches the following:
determining a buffer size for the pair of buffers by performing a symbolic computation based on indices of non-zero elements in the first sparse matrix and row sizes of the second sparse matrix, wherein the symbolic computation estimates a maximum number of floating-point multiplication operations (FLOP) in a hypothetical multiplication between each of the plurality of first rows and the second sparse matrix (Al 1 line 1),
wherein the allocating the pair of buffers comprises:
allocating each of the pair of buffers with the buffer size (Alf 1 line 2-3, section 3.2).
Regarding claim 15, in addition to the teachings addressed in the claim 14 analysis, Du teaches the following:
wherein the symbolic computation comprises: for each of the plurality of first rows that comprises one or more non-zero elements, identifying one or more corresponding second rows from the second sparse matrix; determining a number of FLOP for the each first row based on a number of non-zero elements in the one or more corresponding second rows from the second sparse matrix; and determining the maximum number of FLOP of the plurality of first rows as the buffer size (section 3.2 2nd to last paragraph).
Regarding claim 16, in addition to the teachings addressed in the claim 13 analysis, Du teaches the following:
allocating an offset buffer comprising a plurality of offsets respectively corresponding to the plurality of intermediate lists, wherein each offset points to a first unmerged element in the corresponding intermediate list (Alg 1, line 14, lines 21-31).
Regarding claim 17, in addition to the teachings addressed in the claim 13 analysis, Du teaches the following:
wherein the merging the plurality of intermediate lists from the buffer pointed by the first pointer into the smaller number of intermediate lists and storing the smaller number of intermediate lists into the buffer pointed by the second pointer comprises: -- FIG 1
for two adjacent intermediate lists of the plurality of intermediate lists:
(1) determining two memory offsets in the buffer pointed by the first pointer, the two memory offsets pointing to the two intermediate lists respectively;
(2) determining a destination memory offset in the buffer pointed by the second pointer;
(3) retrieving, at the memory offsets of the buffer pointed by the first pointer, column indices of two elements;
(4) in response to the column indices of the two elements being same, aggregating values of the two unmerged elements to obtain an aggregated value, storing the aggregated value into a merged list starting at the destination memory offset in the buffer pointed by the second pointer;
(5) in response to the column indices of the two elements being different, storing one of the two unmerged elements that comprises a smaller value into the merged list starting at the destination memory offset in the buffer pointed by the second pointer; and
repeating steps (1)-(5) until the two intermediate lists are merged into the merged list in the buffer pointed by the second pointer (Section 3.1, image and description of figure 2 describes steps 1-5, Alg 1 with the repeating).
Regarding claim 18, Du teaches the following:
a non-transitory computer-readable storage medium for memory-efficient accumulation to accelerate SpGEMM computations 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 (abstract) comprising:
obtaining a first sparse matrix and a second sparse matrix for performing SpGEMM (Algorithm 1,Require A, Bin CSR format, line 10, line 11, Section 4.1, Table 2);
allocating a pair of buffers in a cache associated with the one or more processors, the pair of buffers pointed by a first pointer and a second pointer (Algorithm 1 line 2, line 3, line 7, line 8, p. 6 least paragraph, thru end of paragraph p. 7, Abstract second paragraph, section 3.3 second paragraph, section 3.3.1);
for each first row in the first sparse matrix that comprises a plurality of non-zero elements, identifying, by the processor, a plurality of second rows in the second sparse matrix that correspond to the plurality of non-zero elements (section 2.1.3);
obtaining a plurality of intermediate lists computed based on each of the plurality of non-zero elements in the first row and one of the plurality of second rows that corresponds to the non-zero element of the first row (fig 1 left most lists);
storing the plurality of intermediate lists into the buffer pointed by the first pointer (Alg 1 line 7, line 12, section 3.1);
executing an iterative process comprising:
merging the plurality of intermediate lists from the buffer pointed by the first pointer into a smaller number of intermediate lists (fig 2, section 3.1);
storing the smaller number of intermediate lists into the buffer pointed by the second pointer (fig 2, Alg 1, lines 21-36);
swapping the first pointer and the second pointer (Alg 1 line 7, line 19, line 33, line 34); and
determining whether an exit condition to exit the iterative process is met, wherein the exit condition comprises whether the smaller number of intermediate lists comprises one final merged list (Alg 1 line 30); and
migrating the one final merged list to the one or more non-transitory memoriesas a row of an output matrix of the SpGEMM (Alg 1 line 36).
Regarding claim 19, in addition to the teachings addressed in the claim 18 analysis, Du teaches the following:
determining a buffer size for the pair of buffers by performing a symbolic computation based on indices of non-zero elements in the first sparse matrix and row sizes of the second sparse matrix, wherein the symbolic computation estimates a maximum number of floating-point multiplication operations (FLOP) in a hypothetical multiplication between each of the plurality of first rows and the second sparse matrix (Al 1 line 1),
wherein the allocating the pair of buffers comprises:
allocating each of the pair of buffers with the buffer size (Alf 1 line 2-3, section 3.2).
Regarding claim 20, in addition to the teachings addressed in the claim 19 analysis, Du teaches the following:
wherein the symbolic computation comprises: for each of the plurality of first rows that comprises one or more non-zero elements, identifying one or more corresponding second rows from the second sparse matrix; determining a number of FLOP for the each first row based on a number of non-zero elements in the one or more corresponding second rows from the second sparse matrix; and determining the maximum number of FLOP of the plurality of first rows as the buffer size (section 3.2 2nd to last paragraph).
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.
Claim 10 is rejected under 35 U.S.C. 103 as being unpatentable over Du.
Regarding claim 10, in addition to the teachings addressed in the claim 8 analysis, Du teaches:
Wherein the multi-core processor comprises a CPU, and the number of cores comprise a plurality of Streaming Multiprocessors (SMs) of the CPU (abstract, Introduction p. 2 middle, section 3.3.1). Du discloses SpGEMM row-wise dataflow executed on GPU, with disclosure of numerous methods cited (section 2.1.2 second to last paragraph). It would have been obvious to one of ordinary skill in the art before the effective filing date to implement Du’s algorithm on a multi-core processor comprising a plurality of SMs on a GPU. It is obvious to apply a known technique to a known device ready for improvement to yield predictable results. MPEP 2141.III.(D).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
H. Li et al., Merge-based Parallel Sparse Matrix-Sparse Vector Multiplication with a Vector Architecture, 2018 IEEE 20th International Conference on High Performance Computing and Communications, IEEE 16th International Conference on Smart City, IEEE 4th Intl. Conference on Data Science Systems, 2018 (hereinafter “Li”) discloses a merge-based method to accelerate sparse matrix, dense vector multiplication (abstract). Li further discloses a parallel merge in a horizontal direction by comparing index of pointers for vector pairs (fig 2, alg 2, alg 3).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to EMILY E LAROCQUE whose telephone number is (469)295-9289. The examiner can normally be reached on 10:00am - 1200pm, 2:00pm - 8pm ET M-F.
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 on 571-272-3701. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/EMILY E LAROCQUE/Examiner, Art Unit 2182
Prosecution Insights