DETAILED ACTION
This is in response to the request for continued examination filed on 2/6/2026.
Status of Claims
Claims 1 – 21 are pending, of which claims 1, 8, and 15 are in independent form.
Continued Examination Under 37 CFR 1.114
A request for continued examination under 37 CFR 1.114, including the fee set forth in 37 CFR 1.17(e), was filed in this application after final rejection. Since this application is eligible for continued examination under 37 CFR 1.114, and the fee set forth in 37 CFR 1.17(e) has been timely paid, the finality of the previous Office action has been withdrawn pursuant to 37 CFR 1.114. Applicant's submission filed on 2/6/2026 has been entered.
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.
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.
Claims 1 – 4, 6, 8 – 11, 13, and 15 – 19 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Merrill, III, U.S. Patent Application 2016/0179574 (hereinafter referred to as Merrill).
Referring to claim 1, Merrill discloses “One or more processors, comprising: circuitry” (Fig. 2 parallel processing unit (PPU) 200 with multiple general processing clusters (GPC) 250) “to use a data structure comprising one or more data elements indicating locations of non-zero values within one or more matrix operands” ([0021] storing all non-zero values of a matrix with the location of each value capable of being decoded, such as CSR. [0024] 'data structure' may be, in one embodiment, a compressed representation of a sparse matrix. 'data structure' may be, in another embodiment, a list of independent data sequences to be partitioned into smaller sequences for a divide-and-conquer sorting algorithm) “to assign equal portions of the non-zero values to different software threads to cause the different software threads to perform one or more operations in parallel using the one or more matrix operands” ([0022] assigning each segment of the matrix to a particular thread to multiply by the vector. [0023] a work-efficient parallelization technique. [0028] "the merge-based algorithm may be implemented such that each thread in a plurality of threads processes an equal number (or approximately equal number) of a combination of non-zero values of the sparse matrix combined with rows of the sparse matrix"), “wherein the one or more elements indicate a non-zero value and a row or column of the non-zero value within the one or more matrix operands” ([0021] storing all non-zero values of a matrix with the location of each value capable of being decoded, such as CSR. [0024] 'data structure' may be, in one embodiment, a compressed representation of a sparse matrix. 'data structure' may be, in another embodiment, a list of independent data sequences to be partitioned into smaller sequences for a divide-and-conquer sorting algorithm. Fig. 7B and [0084] a second array 720 (Column_idx[ ]) that stores the column indices for each of the non-zero values of the matrix 700. Also, Fig. 8A and [0094] a merged list that combines the offsets in the Row offsets array 730 with the indices into the Values array 710 and Column_idx array 720, in increasing order).
As per claim 2, Merrill discloses “the circuitry is to perform the one or more operations in parallel based, at least in part, on storing in an array variables representing the non-zero values and indications of one or more rows in which the non-zero values appear within the one or more matrix operands” (Fig. 2 parallel processing unit (PPU) 200 with multiple general processing clusters (GPC) 250. [0023] a work-efficient parallelization technique. [0028] "the merge-based algorithm may be implemented such that each thread in a plurality of threads processes an equal number (or approximately equal number) of a combination of non-zero values of the sparse matrix combined with rows of the sparse matrix." Fig. 7B and [0085] Row_offsets[3] is equal to 4 and indicates that the first non-zero entry in the fourth row of matrix 700 is stored in Values[4]).
As per claim 3, Merrill discloses “the locations of the non-zero values are based, at least in part, on where the non-zero values appear in another array of all the non-zero values arranged in order of appearance within the one or more matrix operands” (Fig. 7B and [0083] row major order).
As per claim 4, Merrill discloses “one or more of the non-zero values are positioned first among non-zero values that are located within one or more rows of the one or more matrix operands” (Fig. 7B and [0085] Row_offsets[3] is equal to 4 and indicates that the first non-zero entry in the fourth row of matrix 700 is stored in Values[4]).
As per claim 6, Merrill discloses “the circuitry is to perform the one or more operations in parallel based, at least in part, on information representing one or more of the matrix operands stored in a compressed sparse matrix format” ([0024] the data structure is a compressed representation of a sparse matrix. Fig. 2 parallel processing unit (PPU) 200 with multiple general processing clusters (GPC) 250. [0023] a work-efficient parallelization technique. [0028] "the merge-based algorithm may be implemented such that each thread in a plurality of threads processes an equal number (or approximately equal number) of a combination of non-zero values of the sparse matrix combined with rows of the sparse matrix").
Referring to claim 8, Merrill discloses “A computer-implemented method, comprising: storing, in positions of an array, one or more indications of locations of non-zero values of one or more operands” ([0021] generating matrix vector products having matrices as operands, [0024] the data structure may be stored in a memory, the data structure is a compressed representation of a sparse matrix), “wherein a position of the one or more indications corresponds to a particular non-zero value and a value of the one or more indications corresponds to a row or column of the particular non-zero value within the one or more operands” ([0021] storing all non-zero values of a matrix with the location of each value capable of being decoded, such as CSR. [0024] 'data structure' may be, in one embodiment, a compressed representation of a sparse matrix. 'data structure' may be, in another embodiment, a list of independent data sequences to be partitioned into smaller sequences for a divide-and-conquer sorting algorithm. Fig. 7B and [0084] a second array 720 (Column_idx[ ]) that stores the column indices for each of the non-zero values of the matrix 700. Also, Fig. 8A and [0094] a merged list that combines the offsets in the Row offsets array 730 with the indices into the Values array 710 and Column_idx array 720, in increasing order); “dividing the array into two or more equal portions, each of the equal portions corresponding to a different instruction of two or more instructions to be performed in parallel; identifying one or more non-zero values to be used by each of the two or more instructions based at least on the corresponding equal portions; and performing the two or more instructions” (Fig. 2 parallel processing unit (PPU) 200 with multiple general processing clusters (GPC) 250. [0023] a work-efficient parallelization technique. [0028] "the merge-based algorithm may be implemented such that each thread in a plurality of threads processes an equal number (or approximately equal number) of a combination of non-zero values of the sparse matrix combined with rows of the sparse matrix." [0030], [0039], [0046] threads and instructions. [0052] - [0053] scheduling instructions for execution via threads. [0024] - [0028] equally dividing the elements between the available processing elements).
Note, claim 9 recites the corresponding limitations of claim 2. Therefore, the rejection of claim 2 applies to claim 9.
Note, claim 10 recites the corresponding limitations of claim 6. Therefore, the rejection of claim 6 applies to claim 10.
As per claim 11, Merrill discloses “one or more of the non-zero values are all non-zero values located within a row of the one or more operands” (Fig. 7B and [0084] – [0085] compressed sparse row (CSR) format, row_offsets for each row).
As per claim 13, Merrill discloses “performing the two or more instructions in parallel is based, at least in part, on offset values representing the locations of the non-zero values” ([0083] and Fig. 7B row-offsets. Fig. 2 parallel processing unit (PPU) 200 with multiple general processing clusters (GPC) 250. [0023] a work-efficient parallelization technique. [0028] "the merge-based algorithm may be implemented such that each thread in a plurality of threads processes an equal number (or approximately equal number) of a combination of non-zero values of the sparse matrix combined with rows of the sparse matrix.").
Referring to claim 15, claim 1 recites the corresponding limitations as that of claim 15. Therefore, the rejection of claim 1 applies to claim 15.
As per claim 17, Merrill discloses “data included in the one or more matrix operands are stored in a compressed sparse matrix row format or compressed sparse matrix column format” ([0084] “the sparse matrix 700 of FIG. 7A encoded in the Compressed Sparse Row (CSR) format” and [0087] other formats, including CSC format).
As per claim 18, Merrill discloses “the one or more circuits are to store in an array variables that represent one or more of the non-zero values that are located first among one or more non-zero values within one or more rows of the one or more matrix operands” ([0021] - [0028] arrays of variables representing non-zero values. [0085] first entry in each row).
Note, claim 19 recites the corresponding limitations of claim 13. Therefore, the rejection of claim 13 applies to claim 19.
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 5 and 12 are rejected under 35 U.S.C. 103 as being unpatentable over Merrill in view of Busato et al., ‘On the Load Balancing Techniques for GPU Applications Based on Prefix-scan’ (hereinafter referred to as Busato) (from Applicant’s IDS).
As per claim 5, Merrill discloses “the circuitry is to assign an equal number of the non-zero values to one or more threads” ([0022] assigning each segment of the matrix to a particular thread to multiply by the vector. [0023] a work-efficient parallelization technique. [0028] "the merge-based algorithm may be implemented such that each thread in a plurality of threads processes an equal number (or approximately equal number) of a combination of non-zero values of the sparse matrix combined with rows of the sparse matrix").
Merrill does not appear to explicitly disclose “to assign an equal number of the non-zero values to one or more threads based, at least in part, on a prefix scan.”
However, Busato discloses “to assign an equal number of the non- zero values to one or more threads based, at least in part, on a prefix scan” (Abstract — prefix scan allows the GPU threads to efficiently find and access in parallel to the assigned data. Introduction “...sparse-matrix vector multiplication, and minimum spanning tree construction are some of the many algorithms that can be efficiently implemented in terms of scan operations.” Introduction “even though prefix-scan allows the threads to efficiently access in parallel to the corresponding data, they do not address the load balancing problem.” Section Il. B. 2) CTA+Warp+Scan ‘provides a perfect balancing among threads and warps' and section Il. C. teaches “the dynamic mapping approaches achieve perfect workload partition and balancing among threads”).
Merrill and Busato are analogous art because they are from the same field of endeavor, which is sparse matrix handling/processing.
Before the effective filing date of the claimed invention, it would have been obvious to one of ordinary skill in the art, having the teachings of Merrill and Busato before him or her, to modify the teachings of Merrill to include the teachings of Busato so that the system assigns an equal number of the non-zero values to one or more threads based, at least in part, on a prefix scan.
The motivation for doing so would have been to provide for perfect balancing among the threads (as taught by Busato at sections II. B. 2) CTA+Warp+Scan and section Il. C.) Perfect balancing among the threads would lead to more efficient processing.
Therefore, it would have been obvious to combine Busato with Merrill to obtain the invention as specified in the instant claim.
As per claim 12, Merrill discloses “performing the two or more instructions in parallel” (Fig. 2 parallel processing unit (PPU) 200 with multiple general processing clusters (GPC) 250. [0023] a work-efficient parallelization technique) and “to assign an equal number of variables representing the non-zero values to one or more software threads” ([0022] assigning each segment of the matrix to a particular thread to multiply by the vector. [0023] a work-efficient parallelization technique. [0028] "the merge-based algorithm may be implemented such that each thread in a plurality of threads processes an equal number (or approximately equal number) of a combination of non-zero values of the sparse matrix combined with rows of the sparse matrix").
Merrill does not appear to explicitly disclose “performing the two or more instructions in parallel is based, at least in part, on a prefix sum to assign an equal number of variables representing the non-zero values to one or more software threads.”
However, Busato discloses “performing the two or more instructions in parallel is based, at least in part, on a prefix sum to assign an equal number of variables representing the non-zero values to one or more software threads” (Abstract — prefix scan allows the GPU threads to efficiently find and access in parallel to the assigned data. Introduction “...sparse-matrix vector multiplication, and minimum spanning tree construction are some of the many algorithms that can be efficiently implemented in terms of scan operations.” Introduction “prefix-sum is useful when parallel threads must allocate dynamic data” and “map the workload to threads through the use of prefix-sum data structures.” Introduction “even though prefix-scan allows the threads to efficiently
access in parallel to the corresponding data, they do not address the load balancing problem.” Section Il. B. 2) CTA+Warp+Scan ‘provides a perfect balancing among threads and warps' and section Il. C. teaches “the dynamic mapping approaches achieve perfect workload partition and balancing among threads”).
Merrill and Busato are analogous art because they are from the same field of endeavor, which is sparse matrix handling/processing.
Before the effective filing date of the claimed invention, it would have been obvious to one of ordinary skill in the art, having the teachings of Merrill and Busato before him or her, to modify the teachings of Merrill to include the teachings of Busato so that performing two or more instructions in parallel is based, at least in part, on a prefix sum to assign an equal number of variables representing the non-zero values to one or more threads.
The motivation for doing so would have been to provide for perfect balancing among the threads (as taught by Busato at sections II. B. 2) CTA+Warp+Scan and section Il. C.) Perfect balancing among the threads would lead to more efficient processing.
Therefore, it would have been obvious to combine Busato with Merrill to obtain the invention as specified in the instant claim.
Claims 7, 14, 20, and 21 are rejected under 35 U.S.C. 103 as being unpatentable over Merrill in view of Blelloch, ‘Prefix Sums and Their Applications’ (hereinafter referred to as Blelloch) (from Applicant’s IDS).
As per claim 7, Merrill discloses “the circuitry is to perform the one or more operations in parallel” (Fig. 2 parallel processing unit (PPU) 200 with multiple general processing clusters (GPC) 250. [0023] a work-efficient parallelization technique) and “the data structure” ([0021] storing all non-zero values of a matrix with the location of each value capable of being decoded, such as CSR. [0024] 'data structure' may be, in one embodiment, a compressed representation of a sparse matrix. 'data structure' may be, in another embodiment, a list of independent data sequences to be partitioned into smaller sequences for a divide-and-conquer sorting algorithm).
Merrill does not appear to explicitly disclose “the circuitry is to perform the one or more operations in parallel based, at least in part, on one or more maximum values identified in the data structure.”
However, Blelloch discloses “to perform the one or more operations in parallel based, at least in part, on one or more maximum values” (Introduction - "This chapter introduces one of the simplest and most useful building blocks for parallel algorithms: the all-prefix-sums operation" and "The uses of the all-prefix-sums operation are extensive." "In fact, all-prefix-sums operations using addition, minimum and maximum are so useful in practice that they have been included as primitive instructions in some machines." Pages 38-39 all-prefix-sum scan and prescan. Section 1.2 calculating the scan in parallel, page 45 max-prescan).
Merrill and Blelloch are analogous art because they are from the same field of endeavor, which is parallel computing.
Before the effective filing date of the claimed invention, it would have been obvious to one of ordinary skill in the art, having the teachings of Merrill and Blelloch before him or her, to modify the teachings of Merrill to include the teachings of Blelloch so that the circuitry is to perform the one or more operations in parallel based, at least in part, on one or more maximum values identified in the data structure.
The motivation for doing so would have been to utilize one of the simplest and most useful building blocks for parallel algorithms: the all-prefix-sums operation (as taught by Blelloch in the Introduction).
Therefore, it would have been obvious to combine Blelloch with Merrill to obtain the invention as specified in the instant claim.
Note, claim 14 recites the corresponding limitations of claim 7. Therefore, the rejection of claim 7 applies to claim 14.
Note, claim 20 recites the corresponding limitations of claim 7. Therefore, the rejection of claim 7 applies to claim 20.
As per claim 21, Merrill discloses “the circuitry is to: divide an array into equal portions comprising an equal number of positions” ([0022] assigning segments of a matrix to threads, [0024] data structure of data sequences, [0028] each thread in a
plurality of threads processes an equal number ( or approximately equal number) of a combination of non-zero values of the sparse matrix); “store, in the positions of the array, indications that represent one or more of the non-zero values that are located first among one or more non-zero values within one or more rows of the one or more matrix operands” ([0021] - [0028] arrays of variables representing non-zero values. [0085] first entry in each row); “and store in remaining positions of each equal portion, indications that represent one or more of remaining non-zero values within the one or more rows” (Fig. 7B more than one non-zero value in a row).
Merrill does not appear to explicitly disclose storing in remaining positions of each equal portion, indications that represent one or more of remaining non-zero values within the one or more rows “based, at least in part, on identifying an indication with maximum value in a preceding equal portion.”
However, Blelloch discloses storing indications of non-zero values “based, at least in part, on identifying an indication with maximum value in a preceding equal portion” (Introduction - "This chapter introduces one of the simplest and most useful building blocks for parallel algorithms: the all-prefix-sums operation" and "The uses of the all-prefix-sums operation are extensive." "In fact, all-prefix-sums operations using addition, minimum and maximum are so useful in practice that they have been included as primitive instructions in some machines." Pages 38-39 all-prefix-sum scan and prescan. Section 1.2 calculating the scan in parallel, page 45 max-prescan).
Merrill and Blelloch are analogous art because they are from the same field of endeavor, which is parallel computing.
Before the effective filing date of the claimed invention, it would have been obvious to one of ordinary skill in the art, having the teachings of Merrill and Blelloch before him or her, to modify the teachings of Merrill to include the teachings of Blelloch so that the circuitry is to perform the one or more operations in parallel based, at least in part, on one or more maximum values identified in the data structure.
The motivation for doing so would have been to utilize one of the simplest and most useful building blocks for parallel algorithms: the all-prefix-sums operation (as taught by Blelloch in the Introduction).
Therefore, it would have been obvious to combine Blelloch with Merrill to obtain the invention as specified in the instant claim.
Claim 16 is rejected under 35 U.S.C. 103 as being unpatentable over Merrill in view of Nurvitadhi et al., U.S. Patent Application 2018/0189234 (hereinafter referred to as Nurvitadhi), further in view of Busato.
As per claim 16, Merrill discloses “the one or more circuits are to store in an array variables representing rows” “based, at least in part, on one or more of the non-zero values” ([0021] - [0028] arrays of variables representing non-zero values. Fig. 7B and [0085] Row_offsets[3] is equal to 4 and indicates that the first non-zero entry in the fourth row of matrix 700 is stored in Values[4]. [0084] “the sparse matrix 700 of FIG. 7A encoded in the Compressed Sparse Row (CSR) format”).
Merrill does not appear to explicitly disclose “the one or more circuits are to store in an array variables representing rows indicated by row pointer values.”
However, Nurvitadhi discloses “the one or more circuits are to store in an array variables representing rows indicated by row pointer values” (Fig. 19 and [0076] CSR format and rowptr structure of pointers to values of each of the rows).
Merrill and Nurvitadhi are analogous art because they are from the same field of endeavor, which is parallel computing and sparse matrix handling.
Before the effective filing date of the claimed invention, it would have been obvious to one of ordinary skill in the art, having the teachings of Merrill and Nurvitadhi before him or her, to modify the teachings of Merrill to include the teachings of Nurvitadhi so that the one or more circuits are to store in an array variables representing rows indicated by row pointer values based, at least in part, on one or more of the non-zero values.
The motivation for doing so would have been to provide a means for saving storage space for sparse matrices, while also allowing recovery of the original matrix in a truly lossless manner (as sated by Nurvitadhi at [0069]).
Neither Merrill nor Nurvitadhi appears to explicitly disclose “the one or more circuits are to store in an array variables representing rows indicated by row pointer values based, at least in part, on one or more of the non-zero values and a prefix sum.”
However, Busato discloses “the one or more circuits are to store in an array variables representing rows” “based, at least in part, on one or more of the non-zero values and a prefix sum” (Abstract — prefix scan allows the GPU threads to efficiently find and access in parallel to the assigned data. Introduction “...sparse-matrix vector multiplication, and minimum spanning tree construction are some of the many algorithms that can be efficiently implemented in terms of scan operations.” Introduction “prefix-sum is useful when parallel threads must allocate dynamic data” and “map the workload to threads through the use of prefix-sum data structures.” Introduction “even though prefix-scan allows the threads to efficiently access in parallel to the corresponding data, they do not address the load balancing problem.” Section Il. B. 2) CTA+Warp+Scan ‘provides a perfect balancing among threads and warps' and section Il. C. teaches “the dynamic mapping approaches achieve perfect workload partition and balancing among threads”).
Merrill, Nurvitadhi, and Busato are analogous art because they are from the same field of endeavor, which is parallel computing and sparse matrix handling.
Before the effective filing date of the claimed invention, it would have been obvious to one of ordinary skill in the art, having the teachings of Merrill, Nurvitadhi, and Busato before him or her, to modify the teachings of Merrill and Nurvitadhi to include the teachings of Busato so that performing two or more instructions in parallel is based, at least in part, on a prefix sum to assign an equal number of variables representing the non-zero values to one or more threads.
The motivation for doing so would have been to provide for perfect balancing among the threads (as taught by Busato at sections II. B. 2) CTA+Warp+Scan and section Il. C.) Perfect balancing among the threads would lead to more efficient processing.
Therefore, it would have been obvious to combine Busato with Merrill and Nurvitadhi to obtain the invention as specified in the instant claim.
Response to Arguments
Applicant's arguments filed 2/6/2026 have been fully considered but they are not persuasive.
Applicant argues, on page 7 section A., that
Applicant respectfully submits that the rejections are at least moot in view of the amendments. For example, Merrill describes work-efficient, load-balanced, merge-based parallelized consumption of sequences of sequences. See, e.g., Merrill at Title and Abstract. However, Merrill at least, among other aspects, fails to teach or suggest "wherein the one or more elements indicate a non-zero value and a row or column of the non-zero value within the one or more matrix operands," as claimed.
The examiner disagrees. As above, Merrill’s teachings meet the added claim language. Merrill’s Fig. 7B and [0084] teaches a second array 720 (Column_idx[ ]) that stores the column indices for each of the non-zero values of the matrix 700. Also, Merrill’s Fig. 8A and [0094] teaches a merged list that combines the offsets in the Row offsets array 730 with the indices into the Values array 710 and Column_idx array 720, in increasing order. Both of these are teachings of an array with elements that both indicate a non-zero value and indicate a row or column of the non-zero value.
Contact Information
Any inquiry concerning this communication or earlier communications from the examiner should be directed to STEVEN G SNYDER whose telephone number is (571)270-1971. The examiner can normally be reached on M-F 8:00am-4:30pm (flexible).
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, Henry Tsai can be reached on 571-272-4176. 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.
/STEVEN G SNYDER/Primary Examiner, Art Unit 2184