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 .
Drawings
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(4) because reference character “240” has been used to designate both the buffer on Fig.2 and the input processing on Fig.6.
The drawings are objected to under 37 CFR 1.83(a). The drawings must show every feature of the invention specified in the claims. Therefore, the controlling circuitry must be shown or the feature canceled from the claims. No new matter should be entered.
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Specification
The specification is objected to as failing to provide proper antecedent basis for the claimed subject matter. See 37 CFR 1.75(d)(1) and MPEP § 608.01(o). Correction of the following is required: there are no clear antecedent basis for Controlling circuitry. See Claim Rejections - 35 USC § 112 below for more details.
Claim Objections
Claims 1, 5-6, 14, and 17 objected to as failing to comply with 37 CFR 1.75(a) because of the following informalities:
In claim 1, ll.4, “computer storage media” should read as “an computer storage media”
In claim 5, ll.2, “an N x M grid of ALUs” should read as “an N x M grid of the ALUs”
In claim 6, ll.4, “the N x M grid of ALUs” should read as “the N x M grid of the ALUs”
In claim 8, ll.14, “the corresponding column vector or corresponding column vector” should read as “the corresponding row vector or corresponding column vector”
In claim 8, ll.15, “to corresponding ALUs” should read as “to the corresponding ALUs”
In claim 14, ll.2, “an N x M grid of ALUs” should read as “an N x M grid of the ALUs”
In claim 17, ll.2, “an N x M grid of ALUs” should read as “an N x M grid of the ALUs”
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.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-20 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 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite in that it fails to point out what is included or excluded by the claim language.
The claim recites “controlling circuitry in the TPU”. This limitation is unclear because “controlling circuitry” can be considered an additional structural element i.e. a circuitry for controlling, or it can be considered as language to merely “controlling the circuitry”.
For purposes of examination, the controlling circuitry will be considered an additional structural element of the system.
Examiner notes that “controlling the circuitry” may also be unclear to which or what “circuitry” is being controlled.
The claim recites the following: “at least one computer processing unit of a tensor processing unit (TPU)” (for computer processing unit, hereinafter “CPU”), “dot product operations configured to be performed by a plurality of arithmetic logic units (ALUs) of a matrix computation unit (MCU) of the TPU”, and “controlling circuitry in the TPU” (for controlling circuitry, hereinafter “CC”). It is unclear if the structural elements of the TPU, ALUs, MCU, and CC are part of the system, as it would normally be recited in a more formal structure with the system. As such, it is unclear if the TPU, ALUs, MCU, and CC are part of the claim language.
The claim recites “the system to perform operations comprising:”. This limitation is unclear because it merely states a function without providing any indication about how the function is performed. The recited function does not follow from the structure recited in the claim, i.e., the CPU, Computer storage media, and TPU (and ALUs, MCU, CC), so it is also unclear whether the function requires some other structure or is simply a result of operating the system in a certain manner.
Claims 2-10 effectively depends on claim 1 and are rejected for the reasons given above.
Claim 11 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite in that it fails to point out what is included or excluded by the claim language.
The claim recites “controlling circuitry in the TPU”. This limitation is unclear because “controlling circuitry” can be considered an additional structural element i.e. a circuitry for controlling, or it can be considered as language to merely “controlling the circuitry”.
For purposes of examination, the controlling circuitry will be considered an additional structural element of the system. However, this makes the claim unclear because the method would comprise of an structural element.
Examiner notes that “controlling the circuitry” may also be unclear to which or what “circuitry” is being controlled.
The claim recites the following: “dot product operations configured to be performed by a plurality of arithmetic logic units (ALUs) of the TPU”, and “controlling circuitry in the TPU” (for controlling circuitry, hereinafter “CC”). It is unclear if the structural elements of the TPU, ALUs, and CC are part of the method, as it would normally be recited in a more formal structure with the method. As such, it is unclear if the ALUs, and CC are part of the claim language.
Claims 12-15 effectively depends on claim 11 and are rejected for the reasons given above.
Claim 16 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite in that it fails to point out what is included or excluded by the claim language.
The claim recites “controlling circuitry in the TPU”. This limitation is unclear because “controlling circuitry” can be considered an additional structural element i.e. a circuitry for controlling, or it can be considered as language to merely “controlling the circuitry”.
The claim recites the following: “one or more processors of a tensor processing unit (TPU)”, “dot product operations configured to be performed by a plurality of arithmetic logic units (ALUs) of the TPU”, and “controlling circuitry in the TPU” (for controlling circuitry, hereinafter “CC”). It is unclear if the structural elements of the TPU, ALUs, and CC are part of the claim, as it would normally be recited in a more formal structure. As such, it is unclear if the TPU, ALUs, and CC are part of the claim language.
Claims 17-20 effectively depends on claim 16 and are rejected for the reasons given above.
Claim Rejections - 35 USC § 103
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 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.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1-2, 5-7, 10, and 16-18 are rejected under 35 U.S.C. 103 as being unpatentable over Ross et al. (US 11,361,051 B1), hereinafter Ross.
Regarding claim 1, Ross discloses
A system, comprising:
at least one computer processing unit [Fig.2, Host interface 202] of a tensor processing unit (TPU) [Fig.2, special-purpose integrated circuit 200]; and computer-useable instructions that, when used by the at least one computer processing unit, cause the system to perform operations comprising:
receiving an input indicative of a computer operation to be performed [See fig,2; "The host interface 202 can receive instructions that include parameters for a neural network computation." Col.6,ll.21-23; “[202] send the instructions to a sequencer 206… that control the circuit to perform the neural network computations” Col.6,ll.32-35]:
determining that an aspect of the computer operation comprises a matrix-matrix operation of at least two matrices, wherein the matrix-matrix operation corresponds to a plurality of dot product operations configured to be performed by a plurality of arithmetic logic units (ALUs) [Fig.3, cells 304] of a matrix computation unit (MCU) [Fig.2, Matrix Computation unit] of the TPU ["a matrix computation unit may contain a systolic array of 256x256 cells, in which each cell is configured to perform a mathematical operation... can efficiently perform a matrix multiplication operation between two matrices" Col.7,ll.23-30; "accumulated values are dot products of the sets of weight inputs and the sets of activation inputs." Col.6,ll.1-8];
determining that the plurality of dot product operations are configured to be performed by the plurality of ALUs over a plurality of clock cycles and that a subset of ALUs of the plurality of ALUs do not perform a dot product operation of the plurality of dot product operations during a first clock cycle of the plurality of clock cycles ["the matrix computation unit may perform at least some calculations in which less than all the cells of the of the matrix computation unit are needed… to address the foregoing operating inefficiency, a matrix computation unit may be designed so that it can be dynamically partitioned." Col.7,ll.31-42]; and
based at least on the determination that the plurality of dot product operations are configured to be performed over the plurality of clock cycles ["On each clock cycle, each cell may process the received weight input and a selected one of the multiple received activation inputs to generate an accumulated output." Col.9,ll.57-59; “],
controlling circuitry [Fig.2, sequencer 206] in the TPU to repurpose the plurality of ALUs to cause at least a portion of the subset of ALUs to perform, during the first clock cycle, at least one dot product operation of the plurality of dot product operations [“[206] converts the instructions into low level control signals… to perform the neural network computation… send the control signals to… a matrix computation unit 212” Col.6, ll. 32-48; "specific partitioning of the matrix computation unit can be updated upon the occurrence of a clock cycle." Col.7,ll.65-67; "the systolic array 306 may be dynamically reconfigured to include multiple... partitions, each of which operates simultaneously and independently on different pairs of matrices" Col.8,ll.17-21].
While Ross does not explicitly disclose computer storage media storing computer-useable instructions used by the at least one computer processing unit.
It would have been obvious to one of ordinary skill in the art, given that the host interface 202 receives instructions for the special-purpose integrated circuit 200, that there is a gap on where the instructions come from. As such, a person of ordinary skill in the art would look within the patent to find a solution to the gap. Ross discloses “a computer readable media suitable for storing computer program instructions” and “Computers suitable for the execution of a computer program include, by way of example, can be based on general or special purpose microprocessors or both, or any other kind of central processing unit. Generally, a central processing unit will receive instructions and data from a read only memory or a random access memory or both” on column 20, lines 34 to 61.
As a result, it would have been obvious to one of ordinary skill in the art, having the teaching of Ross before him before the effective filing date of the claimed invention to include a computer readable media suitable for storing computer program instructions with the special-purpose integrated circuit 200 in the system as disclosed by Ross, in order to implement a memory for the instructions to be used to control the operations of the circuit [Ross: Col.19-20, ll.40-61]. Thus, Ross discloses the limitation of a computer storage media storing computer-useable instructions that, when used by the at least one computer processing unit, cause the system to perform operations.
Regarding claim 2, Ross disclose the invention substantially as claimed. See the discussion of claim 1 above.
Ross discloses wherein repurposing the portion of the subset of ALUs causes more dot product operations to be performed during the first clock cycle than without repurposing the portion of the subset of ALUs [Col.7,ll.31-40, discloses the MCU may perform operations that uses less than all the cells of the MCU, called unused cells; “partitions formed from the … partitioning may operate independently from and simultaneously with other… partitions of the [MCU]…” Col.41-67, discloses using partitioned MCU to use the unused cells simultaneously with the operation performed in another partition].
Regarding claim 5, Ross disclose the invention substantially as claimed. See the discussion of claim 1 above.
Ross discloses wherein the TPU comprises a systolic array comprising of an N x M grid of ALUs, wherein N and M comprises respective values comprising any integer greater than 8. [“For instance, a matrix computation unit may contain a systolic array of 256x256 cells” Col.7, ll.23-24; “The systolic array 306 can have more rows than columns, more columns than rows, or an equal number of columns and rows” Col.8, ll.5-14]
Regarding claim 6, Ross disclose the invention substantially as claimed. See the discussion of claim 5 above.
wherein the plurality of dot product operations are determined to be performed over the plurality of clock cycles based on at least one dimension of a first matrix of the at least two matrices or a second matrix of the at least two matrices being less than a value of N or M of the N x M grid of ALUs. [“matrices having different sizes, such as between a 256x256 matrix and a 256x257 matrix, the matrix computation unit may perform at least some calculations in which less than all the cells of the matrix computation unit are needed” Col.7,ll.31-36, discloses that there are instances wherein the MCU performs some calculations less than all the cells, as such, there are instances to perform operations on smaller matrices than the systolic array; “On each clock cycle, each cell may process the received weight input and a selected one of the multiple received activation inputs to generate an accumulated output.” Col.9,ll.57-59, wherein accumulated values are dot products, see Col.6,ll.1-3; see col.9 for input steps]
Regarding claim 7, Ross disclose the invention substantially as claimed. See the discussion of claim 6 above.
Ross discloses wherein the at least one dimension comprises a column of the first matrix and a column of the second matrix. [“each cell is configured to perform a mathematical operation (e.g., multiplication and summation) between input values from a first matrix and input values from a second matrix.” Col.7.ll.23-27; See fig.4, for the directional flow]
Regarding claim 10, Ross disclose the invention substantially as claimed. See the discussion of claim 1 above.
Ross discloses wherein repurposing the plurality of ALUs comprises causing the subset of ALUs to add intermediate results associated with the at least one dot product operation performed during the first clock cycle. [“each cell may process the received weight input and a selected one of the multiple received activation inputs to generate an accumulated output.” Col.9,ll.57-62; “The accumulated outputs can be passed along the same column as the weight inputs, e.g., towards the bottom of the column in the array 406...” Col.10,ll.15-35, discloses accumulated outputs]
Regarding claim 16, it is directed to claim 1. A mere change in statutory class is obvious. As such, claim 16 is rejected for the reasons given above.
Regarding claim 17, it is directed to claim 5. A mere change in statutory class is obvious. As such, claim 17 is rejected for the reasons given above.
Regarding claim 18, it is directed to claim 6. A mere change in statutory class is obvious. As such, claim 18 is rejected for the reasons given above.
Claims 3 is rejected under 35 U.S.C. 103 as being unpatentable over Ross, and in view of Abuazab et al. (NPL: “Sub Tasks Matrix Multiplication Algorithm (STMMA)”), hereinafter Abuazab.
Regarding claim 3, Ross disclose the invention substantially as claimed. See the discussion of claim 1 above.
Ross discloses herein the matrix-matrix operation comprises multiplication of a first matrix and a second matrix having inner dimensions of equal size [“matrix multiplication operation between matrices having different sizes, such as between a 256x256 matrix and a 256x257 matrix” Col.7,ll.31-33]
Ross also discloses that the systolic array is broken up into independent partitions that operate simultaneously [“vertical and horizontal partitioning may operate independently from and simultaneously with the other sub-units or partitions of the [MCU]” Col.7,ll.56-58]
However, Ross does not explicitly disclose dividing a row or a column of the first matrix or the second matrix along the inner dimension to create a vector; and mapping at least one corresponding dot product operation associated with the vector to the subset of ALUs.
In the analogous art of Parallel matrix multiplications and task management, Abuazab teaches:
For matrix-matrix multiplication, generating separate independent sub-tasks of matrix-vector multiplications of the matrix-matrix multiplication by using the inner dimension and mapping the subtasks onto different processors [Fig.1, discloses a matrix-vector multiplication operation for each processor; page 1457, discloses various codes for performing the tasks which comprises of a vector-matrix multiplication operation].
It would have been obvious to one of ordinary skill in the art, having the teachings of Ross and Abuazab before him before the effective filing date of the claimed invention to utilize the separate partitions of Ross by incorporating the subtask vector-matrix multiplication operation taught by Abuazab, in order to, minimize exchanging of intermediate results, improve load balance of idle/unused processing elements, and improve efficiency by allowing the parallel processing [Abuazab: See, p.1457-1459, Subsection of STMMA Efficiency, figs. 1 and 5].
Claim 4 is rejected under 35 U.S.C. 103 as being unpatentable over Ross, and in view of Higham et al. (NPL: “Mixed precision algorithms in numerical linear algebra”), hereinafter Higham.
Regarding claim 4, Ross disclose the invention substantially as claimed. See the discussion of claim 1 above.
Ross discloses a plurality of ALUs [Fig.2 MCU]
However, Ross does not explicitly disclose wherein at least one ALU of the plurality of ALUs employs a floating point precision (FP) data format comprising at least one of: FP16, FP 32, or FP64.
In the analogous art of various architectures and implementations for matrix multiplication and acceleration, Higham teaches:
Various devices that computes matrix multiply accumulate operations employs a floating point precision (FP) data format comprising at least one of: FP16, FP 32, or FP64 [Table 2.2, shows at least one device that can support FP16, FP 32, or FP64]
It would have been obvious to one of ordinary skill in the art, having the teachings of Ross and Higham before him before the effective filing date of the claimed invention to modify the system of Ross, to utilize various different number formats as taught by Higham, in order to be compliant with IEEE, and allow for simulation of different precisions to allow for more accurate results [Higham: p.6-18, see at least p.14
Claims 8 and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Ross, and in view of Yuzuguler et al. (NPL: “Scale-out Systolic Arrays”), hereinafter Yuzuguler, and further in view of Ross et al. (US 11,586,920 B2), hereinafter Ross2.
Regarding claim 8, Ross disclose the invention substantially as claimed. See the discussion of claim 1 above.
Ross discloses partitioning unused cells in vertical, horizontal, or both partitioning based on inputs and mathematical operations performed [Col.7,ll.21-67]
While Ross does not explicitly disclose determining that an inner dimension of a first matrix of the at least two matrices does not match or is less than a number of available rows or columns of a systolic array comprising the plurality of ALUs; It would have been obvious to one of ordinary skill in the art, that given an large systolic array and a smaller matrix input it will still handle matrices of lesser size and allow partitioning as disclosed.
Additionally, Ross does not explicitly disclose dividing the first matrix along an external dimension into a plurality of submatrices, wherein the plurality of submatrices correspond to a row vector or a column vector of a second matrix, wherein each submatrix of the plurality of submatrices has a dimension substantially equal to a number of ALUs of the ALUs of the available row or column of the plurality of ALUs; assigning each submatrix of the plurality of submatrices and a corresponding row vector or a corresponding column vector to a corresponding ALU of the plurality of ALUs; and performing the matrix-matrix operation based on the plurality of submatrices and the corresponding column vectors or corresponding column vectors of the second matrix being assigned to corresponding ALUs of the plurality of ALUs.
In the analogous art of Systolic array architectures and optimization, Yuzuguler teaches:
Rows and columns mismatch of the inputs and systolic array leads to underutilization [Fig.2 shows idle rows and columns due to inner dimension mismatch of the inputs and the systolic array; “larger arrays also increase the likelihood that the workload’s layer dimensions are smaller than the number of array’s rows or columns, resulting in idle processing elements and wasted throughput/Watt” p.4]
Matching the data size to the systolic array allows better utilization [“layers are first partitioned into tile operations of sizes that match a pod’s array dimensions … Utilization within a pod highly depends on the pod’s systolic array granularity and the layer dimensions of a DNN workload… minimizing the array dimensions per pod reduces the mismatch between the workloads and the array, resulting in improved utilization.” P.4]
having multiple systolic arrays allows for more parallel operations [“The resulting tile operations can be performed on a single array sequentially, or they can be distributed among multiple arrays and performed in parallel” p.10]
It would have been obvious to one of ordinary skill in the art, having the teachings of Ross and Yuzuguler before him before the effective filing date of the claimed invention to use Ross partitioning of the systolic array, to minimize underutilization of the array as taught by Yuzuguler, reducing underutilization, and improving overall performance [Yuzuguler: p.3-7 and 10-11]. As such the combination of Ross and Yuzuguler discloses determining that an inner dimension of a first matrix of the at least two matrices does not match or is less than a number of available rows or columns of a systolic array comprising the plurality of ALUs;
However, Ross and Yuzuguler does not explicitly disclose dividing the first matrix along an external dimension into a plurality of submatrices, wherein the plurality of submatrices correspond to a row vector or a column vector of a second matrix, wherein each submatrix of the plurality of submatrices has a dimension substantially equal to a number of ALUs of the ALUs of the available row or column of the plurality of ALUs; assigning each submatrix of the plurality of submatrices and a corresponding row vector or a corresponding column vector to a corresponding ALU of the plurality of ALUs; and performing the matrix-matrix operation based on the plurality of submatrices and the corresponding column vectors or corresponding column vectors of the second matrix being assigned to corresponding ALUs of the plurality of ALUs.
In the analogous art of matrix computation architectures and methodology, Ross2 teaches:
dividing the first matrix along an external dimension into a plurality of submatrices, wherein the plurality of submatrices correspond to a row vector or a column vector of a second matrix, wherein each submatrix of the plurality of submatrices has a dimension substantially equal to a number of ALUs of the ALUs of the available row or column of the plurality of ALUs [“more sets of activation inputs to be processed than there are rows in the array the system can divide the sets of activation inputs into portions so that each portion has a size less than or equal to a number of rows in the array” Col.8,ll.16-20];
assigning each submatrix of the plurality of submatrices and a corresponding row vector or a corresponding column vector to a corresponding ALU of the plurality of ALUs [“The system then can generate, for each portion of activation inputs, a portion of accumulated values” Col.8,ll.21-29]; and
performing the matrix-matrix operation based on the plurality of submatrices and the corresponding column vectors or corresponding column vectors of the second matrix being assigned to corresponding ALUs of the plurality of ALUs [“The system can then combine all portions of accumulated values into a vector of accumulated values” Col.8,ll.30-38; “an example process for performing, using a systolic array, the computation for a given neural network layer having more activation inputs than rows in the systolic array” Col.7,ll.55-57; “The system generates accumulated values from the weight inputs and the activation inputs using a matrix multiplication…” Col.3,ll.66-67].
It would have been obvious to one of ordinary skill in the art, having the teachings of Ross, Yuzuguler, and Ross2 before him before the effective filing date of the claimed invention to divide the input data of Ross and Yuzuguler along the external dimension as taught by Ross2, in order to process data that is larger than the systolic array in terms of the external dimension, to compute the final matrix multiplication result allowing reduction in power and cost, and additionally Ross2 is directed to the same product and would be obvious to combine the teachings of Ross and Ross2 [Ross2: Col.2,ll.51-65, and col.8]
Regarding claim 19, it is directed to claim 8. A mere change in statutory class if obvious. Claim 19 is rejected for the reasons given above.
Claim 9 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Ross, and in view of Yuzuguler, and further in view of Bodwin (US 12,001,508 B1).
Regarding claim 9, Ross disclose the invention substantially as claimed. See the discussion of claim 1 above.
Ross discloses partitioning unused cells in vertical, horizontal, or both partitioning based on inputs and mathematical operations performed [Col.7,ll.21-67]
While Ross does not explicitly disclose determining that an inner dimension of a first matrix of the at least two matrices does not match or is less than a number of available rows or columns of a systolic array comprising the plurality of ALUs; It would have been obvious to one of ordinary skill in the art, that given an large systolic array and a smaller matrix input it will still handle matrices of lesser size and allow partitioning as disclosed.
Additionally, Ross does not explicitly disclose dividing the first matrix along the inner dimension into a plurality of vectors, wherein the plurality of vectors correspond to one row or one column of the first matrix, wherein the plurality of vectors have a dimension substantially equal to a number of ALUs of the ALUs of the available row or column of the plurality of ALUs; assigning each of the plurality of vectors and a corresponding submatrix of a second matrix to a corresponding ALU of the plurality of ALUs; and performing the matrix-matrix operation based on the plurality of vectors and a corresponding submatrix of a second matrix to a corresponding ALU of the plurality of ALUs being assigned to corresponding ALUs of the plurality of ALUs.
In the analogous art of Systolic array architectures and optimization, Yuzuguler teaches:
Rows and columns mismatch of the inputs and systolic array leads to underutilization [Fig.2 shows idle rows and columns due to inner dimension mismatch of the inputs and the systolic array; “larger arrays also increase the likelihood that the workload’s layer dimensions are smaller than the number of array’s rows or columns, resulting in idle processing elements and wasted throughput/Watt” p.4]
Matching the data size to the systolic array allows better utilization [“layers are first partitioned into tile operations of sizes that match a pod’s array dimensions … Utilization within a pod highly depends on the pod’s systolic array granularity and the layer dimensions of a DNN workload… minimizing the array dimensions per pod reduces the mismatch between the workloads and the array, resulting in improved utilization.” P.4]
having multiple systolic arrays allows for more parallel operations [“The resulting tile operations can be performed on a single array sequentially, or they can be distributed among multiple arrays and performed in parallel” p.10]
It would have been obvious to one of ordinary skill in the art, having the teachings of Ross and Yuzuguler before him before the effective filing date of the claimed invention to use Ross partitioning of the systolic array, to minimize underutilization of the array as taught by Yuzuguler, reducing underutilization, and improving overall performance [Yuzuguler: p.3-7 and 10-11]. As such the combination of Ross and Yuzuguler discloses determining that an inner dimension of a first matrix of the at least two matrices does not match or is less than a number of available rows or columns of a systolic array comprising the plurality of ALUs;
However, Ross and Yuzuguler does not explicitly disclose dividing the first matrix along the inner dimension into a plurality of vectors, wherein the plurality of vectors correspond to one row or one column of the first matrix, wherein the plurality of vectors have a dimension substantially equal to a number of ALUs of the ALUs of the available row or column of the plurality of ALUs; assigning each of the plurality of vectors and a corresponding submatrix of a second matrix to a corresponding ALU of the plurality of ALUs; and performing the matrix-matrix operation based on the plurality of vectors and a corresponding submatrix of a second matrix to a corresponding ALU of the plurality of ALUs being assigned to corresponding ALUs of the plurality of ALUs.
In the analogous art of matrix multiplication architectures and methodology, Bodwin teaches:
dividing the first matrix along the inner dimension into a plurality of vectors, wherein the plurality of vectors correspond to one row or one column of the first matrix, wherein the plurality of vectors have a dimension substantially equal to a number of ALUs of the ALUs of the available row or column of the plurality of ALUs [Figures.2-3, shows that the matrices can be sliced along an external dimension into vectors or sub matrices and used in the systolic array; “A multiply accumulate (MAC) unit 10 may be disposed at the intersection of each horizontal input line and vertical input line, which computes the dot product ( or also called an "inner product") of a row (or row vector) of the horizontal stripe with a column ( or column vector) of the vertical stripe” Col.7,ll.54-58];
assigning each of the plurality of vectors and a corresponding submatrix of a second matrix to a corresponding ALU of the plurality of ALUs [Fig.3, shows the inputs into the corresponding MAC units; “computes the dot product ( or also called an "inner product") of a row (or row vector) of the horizontal stripe with a column ( or column vector) of the vertical stripe” Col.7,ll.54-58]; and
performing the matrix-matrix operation based on the plurality of vectors and a corresponding submatrix of a second matrix to a corresponding ALU of the plurality of ALUs being assigned to corresponding ALUs of the plurality of ALUs. [Fig.3, shows matrix multiplication; see col.7-8 “Matrix C can be computed by multiplying each of the horizontal stripes... with each of the vertical stripes,”].
It would have been obvious to one of ordinary skill in the art, having the teachings of Ross, Yuzuguler, and Bodwin before him before the effective filing date of the claimed invention to modify the input data of Ross and Yuzuguler, by slicing the input data into stripes as taught by Bodwin, in order to further improve utilization of idle components, and reduce the time taken [Bodwin: See col.6-8, 19-20, and 24]
Regarding claim 20, it is directed to claim 9. A mere change in statutory class if obvious. Claim 20 is rejected for the reasons given above.
Claims 11-15 are rejected under 35 U.S.C. 103 as being unpatentable over Ross, and in view of Abuazab, and further in view of Bodwin.
Regarding claim 11, Ross discloses:
A computer-implemented method, comprising:
receiving, via a tensor processing unit (TPU) [Fig.2, special-purpose integrated circuit 200], an input indicative of a neural network computer operation to be performed [See fig,2; "The host interface 202 can receive instructions that include parameters for a neural network computation." Col.6,ll.21-23; “[202] send the instructions to a sequencer 206… that control the circuit to perform the neural network computations” Col.6,ll.32-35]:
determining that an aspect of the computer operation comprises at least one matrix-matrix operation between a first matrix and a second matrix, wherein the matrix-matrix operation comprises a plurality of dot product operations performed by a plurality of arithmetic logic units (ALUs) [Fig.3, cells 304] of the TPU ["a matrix computation unit may contain a systolic array of 256x256 cells, in which each cell is configured to perform a mathematical operation... can efficiently perform a matrix multiplication operation between two matrices" Col.7,ll.23-30; "accumulated values are dot products of the sets of weight inputs and the sets of activation inputs." Col.6,ll.1-8];
determining that the plurality of dot product operations are configured to be performed by the plurality of ALUs over a plurality of clock cycles and that a subset of ALUs of the plurality of ALUs do not perform a dot product operation of the plurality of dot product operations during a first clock cycle of the plurality of clock cycles ["the matrix computation unit may perform at least some calculations in which less than all the cells of the of the matrix computation unit are needed… to address the foregoing operating inefficiency, a matrix computation unit may be designed so that it can be dynamically partitioned." Col.7,ll.31-42]; and
based at least on the determination that the plurality of dot product operations are configured to be performed over the plurality of clock cycles ["On each clock cycle, each cell may process the received weight input and a selected one of the multiple received activation inputs to generate an accumulated output." Col.9,ll.57-59; “],
controlling circuitry [Fig.2, sequencer 206] in the TPU to cause at least a portion of the subset of ALUs to perform, during the first clock cycle, at least one dot product operation of the plurality of dot product operations [“[206] converts the instructions into low level control signals… to perform the neural network computation… send the control signals to… a matrix computation unit 212” Col.6, ll. 32-48; "specific partitioning of the matrix computation unit can be updated upon the occurrence of a clock cycle." Col.7,ll.65-67; "the systolic array 306 may be dynamically reconfigured to include multiple... partitions, each of which operates simultaneously and independently on different pairs of matrices" Col.8,ll.17-21].
While Ross does not explicitly disclose computer storage media storing computer-useable instructions used by the at least one computer processing unit.
It would have been obvious to one of ordinary skill in the art, given that the host interface 202 receives instructions for the special-purpose integrated circuit 200, that there is a gap on where the instructions come from. As such, a person of ordinary skill in the art would look within the patent to find a solution to the gap. Ross discloses “a computer readable media suitable for storing computer program instructions” and “Computers suitable for the execution of a computer program include, by way of example, can be based on general or special purpose microprocessors or both, or any other kind of central processing unit. Generally, a central processing unit will receive instructions and data from a read only memory or a random access memory or both” on column 20, lines 34 to 61.
As a result, it would have been obvious to one of ordinary skill in the art, having the teaching of Ross before him before the effective filing date of the claimed invention to include a computer readable media suitable for storing computer program instructions with the special-purpose integrated circuit 200 in the system as disclosed by Ross, in order to implement a memory for the instructions to be used to control the operations of the circuit [Ross: Col.19-20, ll.40-61]. Thus, Ross discloses the limitation of a computer storage media storing computer-useable instructions that, when used by the at least one computer processing unit, cause the system to perform operations.
However, Ross does not explicitly disclose dividing the at least one matrix-matrix operation into a plurality of vector-matrix operations or matrix-vector operations by converting the first matrix into a plurality of vectors and converting the second matrix into a plurality of submatrices with a dimensionality equal in size to that of a number of vectors of the plurality of vectors; and controlling circuitry in the TPU to cause at least a portion of the subset of ALUs to perform, during the first clock cycle, at least one dot product operation of the plurality of dot product operations using the plurality of vectors and the plurality of submatrices.
In the analogous art of Parallel matrix multiplications and task management, Abuazab teaches:
dividing the at least one matrix-matrix operation into a plurality of vector-matrix operations or matrix-vector operations with a matrix having a dimensionality equal in size to that of a number of vectors of a plurality of vectors of another matrix [Fig.1, discloses a matrix-vector multiplication operation for each processor; page 1457, discloses various codes for performing the tasks which comprises of a vector-matrix multiplication operation].
It would have been obvious to one of ordinary skill in the art, having the teachings of Ross, and Abuazab before him before the effective filing date of the claimed invention to utilize the separate partitions of Ross by incorporating the subtask vector-matrix multiplication operation taught by Abuazab, in order to, minimize exchanging of intermediate results, improve load balance of idle/unused processing elements, and improve efficiency by allowing the parallel processing [Abuazab: See, p.1457-1459, Subsection of STMMA Efficiency, figs. 1 and 5].
In the analogous art of matrix multiplication architectures and methodology, Bodwin teaches:
dividing the matrices by converting the first matrix into a plurality of vectors and converting the second matrix into a plurality of submatrices with a dimensionality equal in size to that of a number of vectors of the plurality of vectors [Figures.2-3, shows that the matrices can be sliced along an external dimension into vectors or sub matrices and used in the systolic array with equal inner dimension; “A multiply accumulate (MAC) unit 10 may be disposed at the intersection of each horizontal input line and vertical input line, which computes the dot product ( or also called an "inner product") of a row (or row vector) of the horizontal stripe with a column ( or column vector) of the vertical stripe” Col.7,ll.54-58];
performing at least one dot product operation of the plurality of dot product operations using the plurality of vectors and the plurality of submatrices. [Fig.3, shows the inputs into the corresponding MAC units; “computes the dot product ( or also called an "inner product") of a row (or row vector) of the horizontal stripe with a column ( or column vector) of the vertical stripe” Col.7,ll.54-58; Fig.3, shows matrix multiplication; see col.7-8 “Matrix C can be computed by multiplying each of the horizontal stripes... with each of the vertical stripes,”].
It would have been obvious to one of ordinary skill in the art, having the teachings of Ross, Abuazab, and Bodwin before him before the effective filing date of the claimed invention to modify the input data of Ross and Abuazab, by slicing the input data into stripes as taught by Bodwin, in order to further improve utilization of idle components, and reduce the time taken [Bodwin: See col.6-8, 19-20, and 24]. The combination of Ross, Abuazab, and Bodwin discloses dividing the at least one matrix-matrix operation into a plurality of vector-matrix operations or matrix-vector operations by converting the first matrix into a plurality of vectors and converting the second matrix into a plurality of submatrices with a dimensionality equal in size to that of a number of vectors of the plurality of vectors; and controlling circuitry in the TPU to cause at least a portion of the subset of ALUs to perform, during the first clock cycle, at least one dot product operation of the plurality of dot product operations using the plurality of vectors and the plurality of submatrices.
Regarding claim 12, Ross, Abuazab, and Bodwin disclose the invention substantially as claimed. See the discussion of claim 11 above.
Ross discloses wherein the circuity is controlled to maintain a MAC operation performed by the plurality of ALUs, wherein the MAC operation comprises an addition operation [“The matrix computation unit 212 can process the weight inputs and the activation inputs and provide a vector of outputs” Col.7,ll.4-6; “accumulated values are dot products of the sets of weight inputs and the sets of activation inputs.” Col.6,ll.1-3; “each cell is configured to perform a mathematical operation (e.g., multiplication and summation)” Col.7,ll.24-26].
Regarding claim 13, Ross, Abuazab, and Bodwin disclose the invention substantially as claimed. See the discussion of claim 11 above.
Ross discloses wherein the computer operation comprises an AI-based operation comprising a neural network inference operation [“host interface 202 can receive instructions that include parameters for a neural network computation… the input to the neural network from which the inference is to be computed” Col.6,ll.19-31]
Regarding claim 14, Ross, Abuazab, and Bodwin disclose the invention substantially as claimed. See the discussion of claim 11 above.
Ross discloses wherein the TPU comprises a systolic array comprising an N x M grid of ALUs, [“The systolic array 306 can have more rows than columns, more columns than rows, or an equal number of columns and rows” Col.8, ll.5-14]
wherein determining that the plurality of dot product operations are configured to be performed by the plurality of ALUs over the plurality of clock cycles comprises determining that a dimension of a row or column of the first matrix or the second matrix is less than a value of N or M of the N x M grid of ALUs. [“matrices having different sizes, such as between a 256x256 matrix and a 256x257 matrix, the matrix computation unit may perform at least some calculations in which less than all the cells of the matrix computation unit are needed” Col.7,ll.31-36, discloses that there are instances wherein the MCU performs some calculations less than all the cells, as such, there are instances to perform operations on smaller matrices than the systolic array; “On each clock cycle, each cell may process the received weight input and a selected one of the multiple received activation inputs to generate an accumulated output.” Col.9,ll.57-59, wherein accumulated values are dot products, see Col.6,ll.1-3; see col.9 for input steps]
Regarding claim 15, Ross, Abuazab, and Bodwin disclose the invention substantially as claimed. See the discussion of claim 11 above.
Ross discloses wherein repurposing the portion of the subset of ALUs causes more dot product operations to be performed during the first clock cycle than without repurposing the portion of the subset of ALUs [Col.7,ll.31-40, discloses the MCU may perform operations that uses less than all the cells of the MCU, called unused cells; “partitions formed from the … partitioning may operate independently from and simultaneously with other… partitions of the [MCU]…” Col.41-67, discloses using partitioned MCU to use the unused cells simultaneously with the operation performed in another partition].
Ross discloses herein the matrix-matrix operation comprises multiplication of a first matrix and a second matrix having inner dimensions of equal size [“matrix multiplication operation between matrices having different sizes, such as between a 256x256 matrix and a 256x257 matrix” Col.7,ll.31-33]
Ross also discloses that the systolic array is broken up into independent partitions that operate simultaneously [“vertical and horizontal partitioning may operate independently from and simultaneously with the other sub-units or partitions of the [MCU]” Col.7,ll.56-58]
However, Ross and Bodwin does not explicitly disclose wherein dividing the at least one matrix-matrix operation into the plurality of vector-matrix operations or vector-matrix operations causes the plurality of ALUs to perform more dot product operations of the plurality of dot product operations than performing the matrix-matrix operation without dividing the at least one matrix-matrix operation.
In the analogous art of Parallel matrix multiplications and task management, Abuazab teaches:
For matrix-matrix multiplication, generating separate independent sub-tasks of matrix-vector multiplications of the matrix-matrix multiplication by using the inner dimension and mapping the subtasks onto different processors [Fig.1, discloses a matrix-vector multiplication operation for each processor; page 1457, discloses various codes for performing the tasks which comprises of a vector-matrix multiplication operation].
It would have been obvious to one of ordinary skill in the art, having the teachings of Ross, and Abuazab before him before the effective filing date of the claimed invention to utilize the separate partitions of Ross by incorporating the subtask vector-matrix multiplication operation taught by Abuazab, in order to, minimize exchanging of intermediate results, improve load balance of idle/unused processing elements, and improve efficiency by allowing the parallel processing [Abuazab: See, p.1457-1459, Subsection of STMMA Efficiency, figs. 1 and 5]. The combination of Ross and Abuazab discloses wherein dividing the at least one matrix-matrix operation into the plurality of vector-matrix operations or vector-matrix operations causes the plurality of ALUs to perform more dot product operations of the plurality of dot product operations than performing the matrix-matrix operation without dividing the at least one matrix-matrix operation.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Jouppi et al. (NPL: “Ten Lessons From Three Generations Shaped Google’s TPUv4i”) discloses TPU v4i. See figures 5 and 6.
Nisa et al. (NPL: “Sampled Dense Matrix Multiplication for High-Performance Machine Learning”) discloses different types of streaming/tiling for small matrices, see figures 2 and 3.
Muller et al. (US 2024/0028665 A1) discloses sub-matrix/sub-vector decompositions for matrix multiplication see par.71-77.
Maiyuran et al. (US 11,640,297 B2) discloses parallel dot product operations, see fig.17 and 20, see columns 29-32.
Ross et al. (US 9,697,463 B2) discloses replication of the inputs into adjacent cells, see Figures 7-9 and Columns 2, 4, 9, and 11.
Huang et al. (US 12,007,937 B1) discloses decomposing matrix multiplication into a plurality of dot products, see figures 10-11 and column 8.
Khaddam-Aljameh et al. (US 2025/0130771 a1) discloses decomposing matrix operations into matrix vector calculations, see figure 5 and par.14, 21, and 25
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Kenny K. Bui whose telephone number is (571)270-0604. The examiner can normally be reached 8:00 am to 3:00 pm on Monday, 8:00 am to 4:00 pm on Tuesday to Friday ET.
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 T 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.
/KENNY K. BUI/Patent Examiner, Art Unit 2182 (571)270-0604
/ANDREW CALDWELL/Supervisory Patent Examiner, Art Unit 2182
Prosecution Insights