DETAILED ACTION
Status of Claims
Claim(s) 1-17 and 29-31 are pending and are examined herein.
Claim(s) 18-28 and 32-46 are Canceled.
Claim(s) 1-17 and 29-31 are rejected under 35 U.S.C. §§§ 101, 102, and 103.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Priority
Acknowledgment is made of the applicant’s claim for priority to foreign application (Korean Patent Application No. 10-2022-0169096), filed on Dec. 6, 2022.
Information Disclosure Statement
The information disclosure statement IDS(s) submitted on December 04, 2023 and May 30, 2024 are in compliance with the provisions of 37 CFR 1.97 and have been considered by the examiner.
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.
Claim(s) 7 and 11 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor, for pre-AIA the applicant regards as the invention.
Regarding Claim 7, the claim recites the limitation “wherein the cost function corresponds to a ratio of a skewness of the candidate point to a skewness of a boundary between the first area and the second area in the three-dimensional space.” without clearly defining the claimed terms “a skewness of the candidate point” and “a skewness of a boundary.” The skewness recited in the claims from which claim 7 depends defined as the calculated element of “a matrix operation.” Claim 7 uses this term for two other types of elements or objectives (a point and boundary) without clearly defining the meaning of these elements or the relationship to the previously defined element (skewness). The specification (e.g., paragraphs [0079]-[0084]) does not provide clear definition of the claimed terms. Accordingly, a person of ordinary skill in the art cannot determine with reasonable certainty what ratio the cost function computes, and therefore cannot determine the metes and bounds of the claim scope.
Regarding Claim 11, the claim recites the limitation “providing at least one value corresponding to the tiled feature map and the tiled kernel to the hardware executing the neural network” without a clear antecedent basis for the claimed terms “the tiled feature map and the tiled kernel.” The recited elements “the tiled feature map and the tiled kernel” were not defined or introduced in the earlier claims from which claim 11 depends. Thus, it is unclear whether these terms refer to the sizes of the tiles recited in claim 10, the operation of tiling the feature map and kernel recited in claim 1, or defines new elements. Because the claim fails to provide a proper antecedent basis for these terms, a person of ordinary skill in the art cannot determine the metes and bounds of the claim scope.
In view of the above, the Examiner respectfully requests that Applicant thoroughly review the claims for compliance with the requirements set forth under 35 U.S.C. § 112. Appropriate correction is required.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
When considering subject matter eligibility under 35 U.S.C. 101, it must be determined whether the claim is directed to one of the four statutory categories of invention, i.e., process, machine, manufacture, or composition of matter (Step 1). If the claim does fall within one of the statutory categories, the second step in the analysis is to determine whether the claim is directed to a judicial exception (Step 2A). The Step 2A analysis is broken into two prongs. In the first prong (Step 2A, Prong 1), it is determined whether or not the claims recite a judicial exception (e.g., mathematical concepts, mental processes, certain methods of organizing human activity). If it is determined in Step 2A, Prong 1 that the claims recite a judicial exception, the analysis proceeds to the second prong (Step 2A, Prong 2), where it is determined whether or not the claims integrate the judicial exception into a practical application. If it is determined at step 2A, Prong 2 that the claims do not integrate the judicial exception into a practical application, the analysis proceeds to determining whether the claim is a patent-eligible application of the exception (Step 2B). If an abstract idea is present in the claim, any element or combination of elements in the claim must be sufficient to ensure that the claim integrates the judicial exception into a practical application, or else amounts to significantly more than the abstract idea itself. Applicant is advised to consult MPEP 2106 for more details of the analysis.
Under Step 1 analysis,
Claims 1-14 recite a method (representing a process);
Claims 15-17 recite an apparatus (representing a machine); and
Claims 29-31 recite a non-transitory storage medium (representing an article of manufacture).
Therefore, each set of the claims falls into one of the four statutory categories (i.e., process, machine, article of manufacture, or composition of matter).
Claim(s)
1-17 and 29-31 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more, and hence is not patent-eligible subject matter.
Regarding Claim 1,
Step 2A Prong 1: The claim recites an abstract idea enumerated in the 2019 PEG.
calculating a skewness of a matrix operation between a feature map and a kernel of the neural network based on the neural network information; (An abstract idea of a mental process and/or a mathematical concept. Examiner’s note: the “calculating” step, as drafted, and under its broadest reasonable interpretation (BRI), covers concepts that can be practically performed in the human mind and/or with physical aid pen and paper. See MPEP § 2106.04(a)(2)(III). The calculation of skewness is defined as the ratio of the size of a larger matrix to the size of a smaller matrix from a pair of two matrices (see spec para. [0045] Eq 1). It is noted that “a step of "determining" a variable or number using mathematical methods or "performing" a mathematical operation may also be considered mathematical calculations when the broadest reasonable interpretation of the claim in light of the specification encompasses a mathematical calculation.” MPEP § 2106.04(a)(2)(I).)
determining that the matrix operation comprises a memory bounded operation based on the skewness of the matrix operation; (An abstract idea of a mental process. Examiner’s note: the “determining” step, as drafted, and under its broadest reasonable interpretation (BRI), covers concepts that can be practically performed in the human mind. See MPEP § 2106.04(a)(2)(III). The process of deciding whether the matrix operation falls into the memory bounded category (i.e., memory bandwidth limits). This is falls under evaluation and decision-making process that can be practically performed in the human mind.)
tiling the feature map and the kernel based on the determination. (An abstract idea of a mental process. Examiner’s note: the “tiling” step, as drafted, and under its broadest reasonable interpretation (BRI), covers concepts that can be practically performed in the human mind. The process of “tiling” refers to partitioning or dividing the matrices (i.e., feature map / kernel) involved in the matrix operation based on the early determination whether the operation is either memory bounded or computation bounded. Accordingly, this is a mental process that can be practically performed in the human mind with physical aid (e.g., pen and paper). See MPEP § 2106.04(a)(2)(I) & (III).)
Step 2A Prong 2: Under this prong, we evaluate whether the claim recites additional elements that integrate the abstract idea into a practical application by considering the claim as a whole. The judicial exception is not integrated into a practical application.
Additional Elements Analysis:
The claim recite the additional element such as:
obtaining input data including neural network information of the neural network; (This amounts to adding insignificant extra-solution activity to the judicial exception, as discussed in MPEP § 2106.05(g). The “receiving” step merely defines a received request to perform an abstract idea on the obtained transaction. This merely defines a generic computer function (i.e., data gathering in conjunction with the abstract idea.)
The recitation of “neural network data” amounts to linking the use of a judicial exception to a particular technological environment or field of use, as discussed in MPEP § 2106.05(h). The claim limitation merely defines the intended use or filed of use of the claimed method. The domain/application in which the abstract idea is used does not meaningfully limit the abstract idea because it merely links the use of the abstract idea to a particular technological environment. See MPEP § 2106.05(e).)
Step 2B: Under this prong, the claim must include additional elements that amount to significantly more than the judicial exception. These elements must not be well-understood, routine, or conventional in the relevant field. When viewed individually and as an ordered combination, the claim does not include any such additional elements that are sufficient to amount to significantly more (i.e., inventive concept).
Additional Elements Analysis:
As explained above, the recitation of “tiling a neural network” merely defines the intended use of field of use of the claimed method. The domain/application in which the abstract idea is used does not meaningfully limit the abstract idea as it merely links the use of the abstract idea for a particular technological environment.
Additionally, the “obtaining” step remains insignificant extra-solution activity to the judicial exception. This step merely defines a computer function of receiving information to implement the abstract idea on a computer. This amounts to either a data gathering and/or routine data access function. Courts have recognized computer functions such as “receiving or transmitting data over a network” and “storing and retrieving information in memory” as well‐understood, routine, and conventional functions. Accordingly, This additional element remains insignificant extra-solution activity and does not provide an inventive concept. See MPEP § 2106.05(d).
Therefore, claim 1 does not recite patent-eligible subject matter.
Regarding Claim 2,
Step 2A Prong 1: Claim 2, which incorporates the rejection of claim 1, recites further limitation such as:
wherein the calculating of the skewness comprises calculating a ratio of a size of a larger matrix to a size of a smaller matrix from the feature map and the kernel. (That is part of the abstract idea recited in claim 1. This limitation merely defines the mathematical equation and calculation for calculating the skewness. This falls within the abstract ideas mathematical concept and mental process. See MPEP § 2106.04(a)(2)(I) & (III).)
Step 2A Prong 2: The claim does not recite additional element that integrates the judicial exception into a practical application.
Step 2B: The claim does not recite additional elements that amount to significantly more than the judicial exception.
Therefore, claim 2 is ineligible.
Regarding Claim 3,
Step 2A Prong 1: Claim 3, which incorporates the rejection of claim 1, recites further limitation such as:
identifying a size of a tile corresponding to the feature map and the kernel; identifying a size of an input channel corresponding to the kernel; identifying, in a three-dimensional space, a point corresponding to the skewness, the size of the tile, and the size of the input channel; and identifying a first area including the identified point based on reference data defining the first area and a second area, wherein the first area comprises a memory bounded area and the second area comprises a computation bounded area. (The claim recites steps that are part of the abstract idea recited in claim 1. These steps fall within the mental process and mathematical concept grouping of abstract idea. The process of identifying and measuring the size of data (i.e., feature map, kernel, and input channel) and checking if the calculated point from skewness, tile size, input channel falls above or below the boundary curve on the reference chart. In other words, checking which side of the curve (from reference data) the calculated point lies on, to identify whether the operation is memory bounded or computation bounded. This process covers mathematical calculation, evaluation, and decision-making process that can be practically performed in the human mind with physical aid (e.g., pen and paper). See MPEP § 2106.04(a)(2)(I) & (III).)
Step 2A Prong 2: The claim does not recite additional element that integrates the judicial exception into a practical application.
Step 2B: The claim does not recite additional elements that amount to significantly more than the judicial exception.
Therefore, claim 3 is ineligible.
Regarding Claim 4,
Step 2A Prong 1: Claim 4, which incorporates the rejection of claim 3, recites further limitation such as:
wherein a boundary between the first area and the second area in the three-dimensional space is based on a size of a memory. (That is part of the abstract idea recited in claim 3. The claim limitation merely defines the boundary line between two areas based on the size of the memory. This is part of the analysis for identifying the memory bounded area and computation bounded area.)
Step 2A Prong 2: The claim does not recite additional element that integrates the judicial exception into a practical application.
Step 2B: The claim does not recite additional elements that amount to significantly more than the judicial exception.
Therefore, claim 4 is ineligible.
Regarding Claim 5,
Step 2A Prong 1: Claim 5, which incorporates the rejection of claim 3, recites further limitation such as:
identifying, in the three-dimensional space, a first candidate point corresponding to a first case in which the kernel is divided in a kernel row direction and the feature map is divided in a feature map column direction; identifying, in the three-dimensional space, a second candidate point corresponding to a second case in which the kernel is divided in a kernel column direction and the feature map is divided in a feature map row direction; selecting a candidate point from among the first candidate point and the second candidate point; and dividing the kernel and the feature map respectively in a manner corresponding to the selected candidate point. (That is part of the abstract idea recited in claim 4. Examiner’s note: the claim recites steps that would fall under the mental process and mathematical concepts grouping. The claim involves proposing two possible ways to partition data matrix by rows/columns, representing each partition as a point in the 3D space (i.e., plotting points in the 3D representing values), selecting candidate points (e.g., based on comparison and/or cost function), and partitioning the matrix data (i.e., kernel or feature map into smaller sub-matrices) accordingly. This process covers concept that can be practically performed in the human mind with the aid of pen and paper. See MPEP § 2106.04(a)(2)(I) & (III).)
Step 2A Prong 2: The claim does not recite additional element that integrates the judicial exception into a practical application.
Step 2B: The claim does not recite additional elements that amount to significantly more than the judicial exception.
Therefore, claim 5 is ineligible.
Regarding Claim 6,
Step 2A Prong 1: Claim 6, which incorporates the rejection of claim 5, recites further limitation such as:
wherein the selecting of the candidate point comprises: calculating a first cost of the first candidate point based on a cost function; calculating a second cost of the second candidate point based on the cost function; and identifying a lower cost from among the first cost and the second cost, wherein the candidate point is selected based on the lower cost. (That is part of the abstract idea recited in claim 5. Examiner’s note: as discussed above under claim 5, the selecting step involves calculation and evaluation which falls within the mathematical concept and mental process. For example, the process of calculating a cost function for each candidate point (the two points identified/plotted in the 3D space), determining which one has lower cost, and selecting the lower-cost point, covers mental process that can be practically performed in the human mind with the aid of pen and paper. The claim defines mathematical relationship, equation, and calculations. See MPEP § 2106.04(a)(2)(I) & (III).)
Step 2A Prong 2: The claim does not recite additional element that integrates the judicial exception into a practical application.
Step 2B: The claim does not recite additional elements that amount to significantly more than the judicial exception.
Therefore, claim 6 is ineligible.
Regarding Claim 7,
Step 2A Prong 1: Claim 6, which incorporates the rejection of claim 6, recites further limitation such as:
wherein the cost function corresponds to a ratio of a skewness of the candidate point to a skewness of a boundary between the first area and the second area in the three-dimensional space. (That is part of the abstract idea of claim 6. The claim limitation merely defines the abstract idea of using the cost function to measure how far a candidate point is from the boundary, where the measurement is by determining the ratio of the candidate skewness (i.e., the ratio of larger matrix size to smaller matrix size). This is part of the mathematical concept and mental process. The claim limitation in light of the specification (e.g., para. [0084]-[0086]) explicitly define mathematical relationship, equation, and calculations. See MPEP § 2106.04(a)(2)(I) & (III).)
Step 2A Prong 2: The claim does not recite additional element that integrates the judicial exception into a practical application.
Step 2B: the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
Therefore, claim 7 is ineligible.
Regarding Claim 8,
Step 2A Prong 1: Claim 8, which incorporates the rejection of claim 1, recites further limitation such as:
calculating a skewness of a subsequent matrix operation based on the tiling; and performing a subsequent tiling based on the skewness of the subsequent matrix operation. (That is part of the abstract idea of claim 1. The claim merely defines the mathematical calculation of skewness and partitioning operation for subsequent matrices. This is part of the mathematical concept and mental process. See MPEP § 2106.04(a)(2)(I) & (III).)
Step 2A Prong 2: The claim does not recite additional element that integrates the judicial exception into a practical application.
Step 2B: the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
Therefore, claim 8 is ineligible.
Regarding Claim 9,
Step 2A Prong 1: Claim 9, which incorporates the rejection of claim 8, recites further limitation such as:
determining whether an end condition is not satisfied, wherein the subsequent tiling is performed based on the end condition. (That is part of the abstract idea of claim 8. The claim merely defines a conditional step which involves evaluation and decision-making process. This is part of the mathematical concept and mental process. See MPEP § 2106.04(a)(2)(I) & (III).)
Step 2A Prong 2: The claim does not recite additional element that integrates the judicial exception into a practical application.
Step 2B: the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
Therefore, claim 9 is ineligible.
Regarding Claim 10,
Step 2A Prong 1: Claim 10, which incorporates the rejection of claim 9, recites further limitation such as:
wherein the end condition is satisfied when a size of a tile corresponding to the feature map and the kernel is less than or equal to a memory budget in a hardware. (That is part of the abstract idea of claim 9. The claim merely defines the condition under which the conditional step is evaluated. This involves comparison that can be practically performed in the human mind. See MPEP § 2106.04(a)(2)(I) & (III). The recitation of “memory budget in a hardware” broadly defines a numerical value or threshold that represents the memory budget (e.g., number of bytes or KB).)
Step 2A Prong 2: The claim does not recite additional element that integrates the judicial exception into a practical application.
Step 2B: the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
Therefore, claim 10 is ineligible.
Regarding Claim 11,
Step 2A Prong 1: Claim 11, which incorporates the rejection of claim 10, doesn’t recite an abstract idea.
Step 2A Prong 2: The judicial exception is not integrated into a practical application.
providing at least one value corresponding to the tiled feature map and the tiled kernel to the hardware executing the neural network. (This amounts to adding insignificant extra-solution activity to the judicial exception, as discussed in MPEP § 2106.05(g). This limitation merely defines a generic data transmission step in conjunction with the aforementioned abstract idea. This does not integrate the abstract idea into a practical application; it is a routine data transmission step.)
Step 2B: the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
As explained above, the additional element identified above does not provide significantly more than the abstract idea. Transmitting data for execution represents a generic computer function that has been recognized by the courts as well-understood, routine, conventional activity. See MPEP § 2106.05(d).
Therefore, claim 11 is ineligible.
Regarding Claim 12,
Step 2A Prong 1: Claim 12, which incorporates the rejection of claim 1, recites further limitation such as:
wherein the tiling is completed sequentially from a lowest level memory to a highest level memory of the memory hierarchy. (That is part of the abstract idea (i.e., tiling operation) identified in claim 1. The claim limitation merely defines the tiling operation as being sequential from lowest level memory to highest level memory. The claim is part of partitioning matrix into smaller sub-matrices sequentially based on the lowest boundary memory level to highest boundary memory level. Accordingly, this is part of the abstract idea of mental process and mathematical concept. See MPEP § 2106.04(a)(2)(I) & (III).)
Step 2A Prong 2: The judicial exception is not integrated into a practical application.
wherein a hardware executing the neural network comprises a memory hierarchy, (This amounts to no more than merely reciting the words "apply it" (or an equivalent) with the judicial exception, or merely including instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea, as discussed in MPEP § 2106.05(f). In other words, the claim invokes computer to execute the aforementioned abstract idea. The recitation of neural network merely defines the intended use or field of use limitation that does not meaningful limit the judicial exception.)
Step 2B: the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
As explained above in step 2A, prong Two, the additional element reciting “a hardware executing the neural network comprises a memory hierarchy” merely represents generic computer component configured to perform the abstract ideas and generally linking the judicial exception to a particular technological environment or field of use. See MPEP § 2106.05(f) & (h). Accordingly, this limitation cannot provide an inventive concept.
Therefore, claim 12 is ineligible.
Regarding Claim 13,
Step 2A Prong 1: Claim 13, which incorporates the rejection of claim 12, doesn’t recite an abstract idea.
Step 2A Prong 2: The judicial exception is not integrated into a practical application.
wherein the hardware comprises a plurality of cores, and wherein the lowest level memory is shared by at least two of the plurality of cores. (This amounts to no more than merely reciting the words "apply it" (or an equivalent) with the judicial exception, or merely including instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea, as discussed in MPEP § 2106.05(f). Examiner’s Note: high-level recitation of generic computer components.)
Step 2B: the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
As explained above, the additional elements identified above do not provide significantly more than the abstract idea. As described in MPEP § 2106.05(f), additional elements that invoke computers or other machinery merely as a tool to perform an existing process will generally not amount to significantly more than a judicial exception. See MPEP § 2106.05(d).
Therefore, claim 14 is ineligible.
Regarding Claim 14,
Step 2A Prong 1: Claim 14, which incorporates the rejection of claim 1, doesn’t recite an abstract idea.
Step 2A Prong 2: The judicial exception is not integrated into a practical application.
wherein a hardware executing the neural network comprises a plurality of processing units, wherein each of the plurality of processing units includes at least one core and a controller, and wherein the controller is configured to schedule the neural network based on the tiling. (This amounts to no more than merely reciting the words "apply it" (or an equivalent) with the judicial exception, or merely including instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea, as discussed in MPEP § 2106.05(f). Examiner’s Note: the claim merely defines generic computer component configured to execute computer program (i.e., neural network) using the abstract idea. The high-level recitation of executing neural network on generic computer component does not integrate the abstract idea into a practical application as this merely serves as tools to execute or apply the abstract idea and/or technological enjoinment in which the abstract idea is used. (see MPEP 2106.05(f) & (h)).)
Step 2B: the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception.
As explained above, the additional elements identified above do not provide significantly more than the abstract idea. As described in MPEP § 2106.05(f), additional elements that invoke computers or other machinery merely as a tool to perform an existing process will generally not amount to significantly more than a judicial exception. See MPEP § 2106.05(d).
Therefore, claim 14 is ineligible.
Regarding Claim 15,
The claim recites similar limitations as corresponding claim 1. Therefore, the same analysis (subject matter eligibility analysis) that was utilized for claim 1, as described above, is equally applicable to claim 15. The only difference is that claim 1 is drawn to a method, and claim 15 is drawn to an apparatus. The recitation of “an apparatus comprising: at least one processor; and a non-transitory storage medium storing instructions that cause the at least one processor to perform a method for tiling a neural network including a plurality of layers to be executed in hardware,...” merely defines computer component and instructions to implement a judicial exception, and hence the claimed additional elements listed above are merely generic elements and the implementation of the elements merely amount to no more than instructions to apply the abstract idea using generic computer components. Therefore, the additional elements do not integrate the judicial exception into a practical application or amount to significantly more. See MPEP 2106.05(f).
Therefore, claim 15 is ineligible.
Regarding Claim 16,
The claim recites similar limitations as corresponding claim 2. Therefore, the same subject matter eligibility analysis (including the abstract idea) that was utilized for claim 2, as described above, is equally applicable to claim 16.
Therefore, claim 16 is ineligible.
Regarding Claim 17,
The claim recites similar limitations as corresponding claim 3. Therefore, the same subject matter eligibility analysis (including the abstract idea) that was utilized for claim 3, as described above, is equally applicable to claim 17.
Therefore, claim 17 is ineligible.
Regarding Claim 29,
The claim recites similar limitations as corresponding claim 1. Therefore, the same analysis (subject matter eligibility analysis) that was utilized for claim 1, as described above, is equally applicable to claim 29. The only difference is that claim 1 is drawn to a method, and claim 15 is drawn to a non-transitory storage medium. The recitation of “a non-transitory storage medium storing instructions that cause at least one processor to perform a method for tiling a neural network including a plurality of layers to be executed in hardware,...” merely defines computer component and instructions to implement a judicial exception, and hence the claimed additional elements listed above are merely generic elements and the implementation of the elements merely amount to no more than instructions to apply the abstract idea using generic computer components. Therefore, the additional elements do not integrate the judicial exception into a practical application or amount to significantly more. See MPEP 2106.05(f).
Therefore, claim 29 is ineligible.
Regarding Claim 30,
The claim recites similar limitations as corresponding claim 2. Therefore, the same subject matter eligibility analysis (including the abstract idea) that was utilized for claim 2, as described above, is equally applicable to claim 30.
Therefore, claim 30 is ineligible.
Regarding Claim 31,
The claim recites similar limitations as corresponding claim 3. Therefore, the same subject matter eligibility analysis (including the abstract idea) that was utilized for claim 3, as described above, is equally applicable to claim 31.
Therefore, claim 31 is ineligible.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claim(s) 1, 12-15, and 29 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Kung et al., (IDS: “CAKE: Matrix Multiplication Using Constant-Bandwidth Blocks.” (2021)).
Regarding Claim 1,
Kung discloses the following:
A method for tiling a neural network, the method comprising: (Kung, [Abstract] “We offer a novel approach to matrix-matrix multiplication computation on computing platforms with memory hierarchies. Constant bandwidth (CB) blocks improve computation throughput for architectures limited by external memory bandwidth. Configuring the shape and size of CB blocks operating from within any memory hierarchy level (e.g., internal SRAM), we achieve high throughput while holding external bandwidth (e.g., with DRAM) constant. We explain how, surprisingly, CB blocks can maintain constant external bandwidth as computation throughput increases. Analogous to partitioning a cake into pieces, we dub our CB-partitioned system CAKE... CAKE achieves superior performance by directly using theoretically optimal CB-partitioned blocks in tiling and scheduling, obviating the need for extensive design search.” [P. 1, Section: 1] “Matrix-matrix multiplication (MM) underlies many computational workloads in scientific computing and machine learning. For example, most computations in the forward pass of a convolutional neural network consist of one matrix multiplication per convolutional layer between the inputs to and the weights of a layer (see, e.g., [26]).”)
obtaining input data including neural network information of the neural network; (Kung, [P. 1, Section: 1] “Matrix-matrix multiplication (MM) underlies many computational workloads in scientific computing and machine learning. For ex ample, most computations in the forward pass of a convolutional neural network consist of one matrix multiplication per convolutional layer between the inputs to and the weights of a layer (see, e.g., [26]).” [P. 2, Section: 2] “Consider an MM between matrices 𝐴 and 𝐵, where 𝐴 is size 𝑀×𝐾 and𝐵 is size 𝐾 ×𝑁... Figure2:(a) 𝐶 = 𝐴×𝐵 matrix multiplication.(b)Computation space represented as an 𝑀 × 𝐾 × 𝑁 3D volume of multiply accumulate (MAC) operations as defined by Algorithm 1. (c) Computation space as an accumulation of outer products.”) [Examiner’s Note: Kung describes the CAKE’s methodology that performs matrix multiplication for neural network layers (i.e., input activations and weights per convolutional layer).]
calculating a skewness of a matrix operation between a feature map and a kernel of the neural network based on the neural network information; (Kung, [P. 1, Section: 1] “The intuition behind CAKE is that, by adjusting the shape (i.e., aspect ratios) and size of CB blocks, we can control the ratio of computations to external memory accesses, i.e., arithmetic intensity (see Figure 4).” [P. 3, Section: 3] “CB block shaping provides control over arithmetic intensity (AI), allowing us to match external IO time with computation time. AI is defined as the ratio of computation volume to data transferred, which is equivalent to the ratio of computation throughput (CT) to external memory bandwidth (BW): 𝐴𝐼 = 𝐶𝑇/𝐵𝑊.” [P. 8, Section: 5.2.3] “CAKE’s Performance for Different Matrix Shapes. As depicted in Figure 8, we use all 10 cores for the Intel CPU and vary 𝑀 and 𝐾 from 1 to8000. Each plot shows a different 𝑀 : 𝑁 aspect ratio, and shaded regions represent input matrix dimensions where CAKE outperforms MKL by at least some factor. As the matrix size decreases in any dimension, CAKE’s through put, relative to MKL, increases. For a general MM between square 𝑁 ×𝑁 matrices, arithmetic intensity is 𝑂(𝑁). Hence, as the problem size 𝑁 decreases, arithmetic intensity also decreases and the MM becomes more memory-bound. CAKE increases arithmetic intensity, and thus MM throughput, by analytically blocking the computation to minimize external IO.”) [Examiner’s Note: the aspect ratio (i.e., measuring the shape of the matrix operation operands). The matrix computation including matrix A (i.e., feature map) and matrix B (kernel/weights).)
determining that the matrix operation comprises a memory bounded operation based on the skewness of the matrix operation; (Kung, [Pp. 3-4, Section: 3] “A constant bandwidth(CB) block is a block (described in Section2.1) with dimensions (𝑛,𝑚,𝑘) shaped and sized according to external bandwidth (as seen in Figure 4). CB block shaping provides control over arithmetic intensity (AI), allowing us to match external IO time with computation time. AI is defined as the ratio of computation volume to data transferred, which is equivalent to the ratio of computation throughput (CT) to external memory bandwidth (BW): 𝐴𝐼 = 𝐶𝑇/𝐵𝑊. Therefore, we can, for example, increase CT or decrease required BW by using CB blocks to control AI.” [P. , Section: 4] “Algorithms that reuse data to different degrees will differ in system resource requirements including external memory bandwidth, internal memory bandwidth, and size of local memories (caches). To increase computation throughput via utilizing additional cores, algorithms must mitigate the constraints imposed by cache size bottlenecks.” [P. 8, Section: 5.2.3] “As the matrix size decreases in any dimension, CAKE’s through put, relative to MKL, increases. For a general MM between square 𝑁 ×𝑁 matrices, arithmetic intensity is 𝑂(𝑁). Hence, as the problem size 𝑁 decreases, arithmetic intensity also decreases and the MM becomes more memory-bound. CAKE increases arithmetic intensity, and thus MM throughput, by analytically blocking the computation to minimize external IO.” Further see section 4.4 and Fig. 4.) [Examiner’s Note: CAKE determines whether the matrix operation is memory bounded using the aspect ratio and arithmetic intensity, where low AI represents memory bound (e.g., cache size).]) and
tiling the feature map and the kernel based on the determination. (Kung, [P. 1, Section: 1] “The intuition behind CAKE is that, by adjusting the shape (i.e., aspect ratios) and size of CB blocks, we can control the ratio of computations to external memory accesses, i.e., arithmetic intensity (see Figure 4). As a result, we can use CB blocks to increase the use of available computing power without requiring a comparable increase in IO bandwidth to external DRAM. We analytically determine the shape and size of a CB block from available DRAM bandwidth and computing resources (Section 3).” [0047] “CB block shaping provides control over arithmetic intensity (AI), allowing us to match external IO time with computation time. AI is defined as the ratio of computation volume to data transferred, which is equivalent to the ratio of computation throughput (CT) to external memory bandwidth (BW): 𝐴𝐼 = 𝐶𝑇/𝐵𝑊.” [P. 6, Section: 4.2] “Figure6 shows CAKE’s block shaping on our CPU with the multilevel memory hierarchy. The computation space of 𝐶=𝐴×𝐵 is partitioned into a 3D grid of CB blocks, as described in Section 2.2. Box(a) shows the schedule of entire CB blocks within the input matrices.” [P. 7, Section: 4.4] “CAKE and GOTO employ similar techniques for reusing data within a memory hierarchy, as seen in Figures 5 and Figures 6. Both use outer products to compute blocks of 𝐶 by multiplying column sub matrices of 𝐴 with row sub-matrices of 𝐵 and summing each partial product in the𝐾 dimension. Furthermore, both partition the column sub-matrix of 𝐴 into square𝑚𝑐 ×𝑘𝑐 sub-matrices and reuse these square sub-matrices in the L2 cache of each core. However, by using CB block shaping and sizing, CAKE is able to account for available external bandwidth constraints. To accommodate additional cores, both CAKE and GOTO increase the size of the sub-matrices reused in local memory.” [Examiner’s Note: CAKE describes the process of partitioning or blocking matrices into smaller-submatrices (i.e., tiling) based on the cache size / bandwidth (i.e., memory bound limit).])
Regarding Claim 12, Kung teaches the elements of claim 1 as outlined above, and further teaches:
wherein a hardware executing the neural network comprises a memory hierarchy, (Kung, [Abstract] “We offer a novel approach to matrix-matrix multiplication computation on computing platforms with memory hierarchies. Constant bandwidth (CB) blocks improve computation throughput for architectures limited by external memory bandwidth. Configuring the shape and size of CB blocks operating from within any memory hierarchy level (e.g., internal SRAM), we achieve high throughput while holding external bandwidth (e.g., with DRAM) constant.” [P. 5, Section: 4] “Modern CPUs contain a multilevel memory hierarchy consisting of external memory, a shared cache for all cores, and local caches on each core (Figure 1). We compare CAKE and Goto’s algorithm [13] (hereafter referred to as GOTO) by adapting our computation throughput and memory bandwidth analysis from Section 3 to CPUs with a multilevel memory hierarchy. In our analysis, we assume the memory hierarchy comprises a local L1 and L2 cache per core, a shared L3 cache for all cores, and external DRAM.” Figure 6: CAKE data reuse in the CPU memory hierarchy. (a) Schedule of CB blocks. (b) Each 𝑝 sub-matrix from 𝐴 is reused in the L2 cache of a core while data from 𝐵 and partial results for 𝐶 are reused in the L3 cache. (c,d) Computation of a single 𝑚𝑐×𝛼𝑝𝑚𝑐 sub-matrix of 𝐶 on a core, similar to Figure 5c and d.(e) Tile-level MM, performed identically to Figure 5e.) and wherein the tiling is completed sequentially from a lowest level memory to a highest level memory of the memory hierarchy. (Kung, [P. 3, Section: 2.2] “To minimize IO, blocks in the MM computation space are scheduled so adjacent blocks are computed in sequence... The partitioning (Figure 3b) is then used to generate a sequence of blocks, which are sequentially executed on the grid of cores... The algorithm defines the 𝐾-first computation order of blocks, which sweeps the space of computation space by first traversing the 𝐾-dimension to maximize partial result reuse, then the 𝑀-dimension to reuse 𝐴, and lastly the 𝑁-dimension to reuse 𝐵.” [P. 4, Section: 3] “To compute a CB block in the 𝑁-dimension, each core is first loaded with one 𝐴 tile. 𝐵 tiles are then streamed to each core from local memory (e.g., L3 cache).”) [Examiner’s Note: The neural network matrix operation performed on hardware with a multi-level memory hierarchy, and performing sequential block scheduling traverses blocks hierarchically (i.e., tiling performed sequentially from lowest to highest memory level).]
Regarding Claim 13, Kung teaches the elements of claim 12 as outlined above, and further teaches:
wherein the hardware comprises a plurality of cores, and wherein the lowest level memory is shared by at least two of the plurality of cores. (Kung, [P. 3, Section: 2.1] “All cores in the processing grid work (Figure 3b) in parallel, on input tiles at the rate of one tile result per unit time for each core, to compute a block by performing 𝑘 outer products.” [P. 4, Section: 3] “Consider a computing architecture with a number of cores, each performing one tile multiplication per unit time. As seen in Section 2.1, each core handles one tile from 𝐴, so the number of tiles in the 𝐴 surface (size𝑚 ×𝑘) of a CB block is equal to the number of cores.” [P. 5, Section: 4] “Modern CPUs contain a multilevel memory hierarchy consisting of external memory, a shared cache for all cores, and local caches on each core (Figure 1). We compare CAKE and Goto’s algorithm [13] (hereafter referred to as GOTO) by adapting our computation throughput and memory bandwidth analysis from Section 3 to CPUs with a multilevel memory hierarchy. In our analysis, we assume the memory hierarchy comprises a local L1 and L2 cache per core, a shared L3 cache for all cores, and external DRAM.” [Pp. 7-8, Section: 5.2] “CAKE’s theoretically optimal DRAM bandwidth usage (calculated in Section 4.2) is shown as a dashed curve. Internal bandwidths between the last level cache (LLC) and CPU cores were measured using the parallel memory bandwidth benchmark tool (pmbw) [5]. Local memory refers to the LLC shared among all cores, and may be the L2 or L3 cache de pending on architecture (i.e., L2 for ARM and L3 for Intel).”) [Examiner’s Note: CAKE design utilize a shared cache (LLC/L3) accessed by all processing cores.]
Regarding Claim 14, Kung teaches the elements of claim 1 as outlined above, and further teaches:
wherein a hardware executing the neural network comprises a plurality of processing units, wherein each of the plurality of processing units includes at least one core and a controller, (Kung, [P. 3, Section: 2.1] “All cores in the processing grid work (Figure 3b) in parallel, on input tiles at the rate of one tile result per unit time for each core, to compute a block by performing 𝑘 outer products.” [P. 11, Section: 6.2] “We developed a SystemC architecture simulator [3] using MatchLib [19] connections to validate the correctness of the CB block design and execution schedule. The simulator models timings between external memory, local memory, and cores under various system characteristics (e.g., low external memory bandwidth). This flexibility helps verify the correctness of the CAKE algorithm for corner cases that are difficult to analyze... Packets originate from external memory and contain headers to control routing (i.e., source routing) as well as fields containing the packet’s tile index into the computation space and CB block. Packet-based scheduling allows us to easily modify the architecture and computation schedule. For example, to double the number of cores, we simply instantiate new mod ules to represent the added cores, and adjust the packet headers accordingly.”) and wherein the controller is configured to schedule the neural network based on the tiling. (Kung, [P. 1, Section: 1] “This paper proposes the CAKE system that utilizes constant bandwidth (CB) blocks in computation partitioning and block scheduling. CAKE offers a theory for optimal partitioning and substantially reduces the search space for an optimal schedule. A CB block is a block of computation with the property that, when computing the block from within a local memory, the required external bandwidth is constant. We can design a CB block capable of achieving a target computation throughput by controlling its shape and size (Section 3). With sufficient local memory resources, the CAKE algorithm can improve MM computation throughput without having to increase external DRAM bandwidth... In CAKE, we partition the MM computation space, a 3D volume of multiply-accumulate (MAC) operations, into a grid of 3D CB blocks. The blocks are scheduled and then sequentially executed on a computing platform comprising multiple computing cores (see Figure 1).” [P. 3, Section: 2.2 Scheduling Blocks for MM Computation] “The algorithm defines the 𝐾-first computation order of blocks, which sweeps the space of computation space by first traversing the 𝐾-dimension to maximize partial result reuse, then the 𝑀-dimension to reuse 𝐴, and lastly the 𝑁-dimension to reuse 𝐵.” Figure 3: (a) Block defined by an𝑘 ×𝑚,𝑛 ×𝑘 input surfaces and an𝑚×𝑛 output surface. (b) Grid of 16 processing cores. (c) Block-partitioned computation space for an MM between 𝑀×𝐾 and𝐾 ×𝑁 matrices. (d) Rotated view of a slice of the computation space. The numbers represent the order of execution for blocks in a 𝐾-first schedule. [Algorithm 2: 𝐾-first block partitioning algorithm, defines the K-first computation order of blocks.])
Regarding Claim 15,
The claim recites substantially similar limitations as corresponding claim 1 and is rejected for similar reasons as claim 1 using similar teachings and rationale. Claim 1 is directed to a method, and claim 15 is directed to an apparatus.
Kung also discloses An apparatus comprising: at least one processor; and a non-transitory storage medium storing instructions that cause the at least one processor to perform a method for tiling a neural network including a plurality of layers to be executed in hardware, when executed by the at least one processor, ... (Kung, See CAKE system and CAKE Architecture Section: 6.2.)
Regarding Claim 29,
The claim recites substantially similar limitations as corresponding claim 1 and is rejected for similar reasons as claim 1 using similar teachings and rationale. Claim 1 is directed to a method, and claim 29 is directed to a non-transitory storage medium.
Kung also discloses A non-transitory storage medium storing instructions that cause at least one processor to perform a method for tiling a neural network... (Kung, See CAKE Implementation and CPU Experiments Section: 5.2.)
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.
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.
Claim(s) 2, 12, and 30 are rejected under 35 U.S.C. 103 as being unpatentable over Kung et al., (IDS: “CAKE: Matrix Multiplication Using Constant-Bandwidth Blocks.” (2021)) in view of Son et al. (Pub. No.: US 20200372276 A1).
Regarding Claim 2,
Kung teaches the elements of claim 1 as outlined above:
While Kung teaches the aspect ratio for adjusting the shape and size of CB blocks of the matrix operation (i.e., skewness of a matrix operation), Kung does not appear to explicitly suggest:
wherein the calculating of the skewness comprises calculating a ratio of a size of a larger matrix to a size of a smaller matrix from the feature map and the kernel.
However, it would have been obvious in view of Son. Hereinafter, Kung in view of Son teaches the limitation:
wherein the calculating of the skewness comprises calculating a ratio of a size of a larger matrix to a size of a smaller matrix from the feature map and the kernel. (Son, [0009] “The selecting of the one operation mode may include selecting the one operation mode based on a ratio between a size of the input and a size of the at least one kernel.” [0112]-[0113] “the CNN processing apparatus may select the operation mode of the convolution layer based on which one of the ratio Iz and the ratio Kz is greater. If Iz and Kz are equal, then CNN processing apparatus may be configured to automatically select the first operation mode... the CNN processing apparatus may select the operation mode based on a ratio between a size of the input and an overall size of the kernels or a size of each or a select kernel. For example, the CNN processing apparatus may obtain a ratio between a size of a frame or channel included in the input and a size of a weight map included in or of a kernel, i.e., of a select channel of the kernel, and select the operation mode by comparing the obtained ratio to a predefined ratio.” [0079] “An input of a convolution layer is data to be employed as an input to the convolution layer, e.g., data that is input to the CNN with one or more channels of information or data that is output by a previous layer of the CNN as one or more feature maps or channels.” Further see [0087]-[0088].)
Kung and Son are from the same field of endeavor and their disclosure generally relates to (Neural Network Matrix Operations).
Accordingly, at the effective filing date, it would have been prima facie obvious to one ordinarily skilled in the art to modify Kung’s CAKE computing architecture to incorporate the method for performing convolution operation as taught by Son. One would have been motivated to make such a combination in order to reduce a number of times data needed for a convolution operation is loaded. Doing so would reduce use of a memory and enable high-speed CNN processing (Son [0082]).
Regarding Claim 16,
The claim recites substantially similar limitations as corresponding claim 2 and is rejected for similar reasons as claim 2 using similar teachings and rationale.
Regarding Claim 30,
The claim recites substantially similar limitations as corresponding claim 2 and is rejected for similar reasons as claim 2 using similar teachings and rationale.
Claim(s) 8 is rejected under 35 U.S.C. 103 as being unpatentable over Kung as outlined above, and further in view of Moon et al., (NPL: "Evaluating spatial accelerator architectures with tiled matrix-matrix multiplication." (2021)).
Regarding Claim 8, Kung teaches the elements of claim 1 as outlined above:
While Kung discloses the CAKE approach which involves computing an aspect ratio and size of CB blocks for MM computation and iteratively partitioning the matrix into sub-matrices (i.e., changing the shape and size of blocks. Kung further teaches: performing a subsequent tiling based on the skewness of the subsequent matrix operation. (Kung, [P. 4, Section: 3] “the CB block shape is defined by 𝑚 = 𝑝𝑘 and 𝑛 = 𝛼𝑝𝑘 where 𝛼 ≥ 1 and 𝑘 are unitless constants calculated from available external memory bandwidth (see Section 3.2). When external memory bandwidth is low, raising 𝛼 increases block computation time, thereby decreasing the CB block’s external bandwidth requirement (BW)... Alternatively, we can compute a CB block in the 𝑀 or𝐾-dimension, resulting in a CB block computation time of 𝑘 or 𝑚 unit times, respectively.”)
Kung does not appear to explicitly teach:
calculating a skewness of a subsequent matrix operation based on the tiling;
However, Kung in view of Moon teaches the limitation:
calculating a skewness of a subsequent matrix operation based on the tiling; (Moon, [P. 2, Section: 2.1] “The primary difference between all these use cases is the size and shape of input matrices for GEMM. Experiments in this paper vary the size and shape of matrices, tile sizes and loop order to cover all these use cases.” [Pp. 9-10, Section: 5.4] “Short-and-fat matrices in workloads II and III (i.e., K >> M and N) show a different trend based on the skewness of the aspect ratio of matrices. For the workload II, with aspect ratio of 1:8 between M/N and K, MAERI-style and Eyeriss-style mappings provide the lowest runtime, which is 57.1% less compared to other mappings, on average... This use case demonstrates the success of workload and architecture-aware tiling strategy. The large skew in dimension (M:N=1:1024) results in an extreme tiling strategy for MAERI-style mapping that maximizes data reuse on the smaller matrix A, which significantly reduces the number of expensive S2 buffer accesses... Hence, FC layer 1 corresponds to the first GEMM operation that multiplies an input matrix of size (128×784) and a weight matrix of size (784×512) where the batch size is set to 128.” Further see Fig. 2 and Algorithm 2: Lines 7-8.) and performing a subsequent tiling based on the skewness of the subsequent matrix operation. (Moon, [P. 2, Section: 2.1] “For the candidate outer tile sizes for S2 buffer size, as the dimension N is spatially mapped in the outer cluster-level, Tout N in Equation1 can be replaced with N/(P/Tout K ). Then if Tout M and Tout K are assumed to be equal, the candidate tile sizes are shown in Equation 3. We iteratively decrease the largest tile size when the tiles do not fit in the S2 buffer.” [Pp. 9-10, Section: 5.4] “This use case demonstrates the success of workload and architecture-aware tiling strategy. The large skew in dimension (M:N=1:1024) results in an extreme tiling strategy for MAERI-style mapping that maximizes data reuse on the smaller matrix A, which significantly reduces the number of expensive S2 buffer accesses... Hence, FC layer 1 corresponds to the first GEMM operation that multiplies an input matrix of size (128×784) and a weight matrix of size (784×512) where the batch size is set to 128.” Further see Fig. 2 and Algorithm 2: Lines 7-8.)
Accordingly, it would have been obvious to a person having ordinary skill in the art, before the effective filing date of the claimed invention, having the combination of Kung and Moon, to incorporate the FLASH framework as taught by Moon. One would have been motivated to make such a combination in order to find optimized mappings (dataflow and tile sizes) for a tiled GEMM for a given spatial accelerator and workload combination. Doing so would provide high performance on various GEMM workloads and accelerators (Moon [Abstract]).
Claim(s) 9-11 are rejected under 35 U.S.C. 103 as being unpatentable over Kung in view of Moon as outlined above, and further in view of Kwon et al., (Pub. No.: US 20210097347 A1).
Regarding Claim 9,
Kung in view of Moon teaches the elements of claim 8 as outlined above, and further teaches:
Moon further teaches the subsequent tiling condition (Moon [P. 6, Section: 3.2] “FLASH takes care of this as we discuss later in Section4. From Fig. 5(d), it can be seen that each time-step of the mapping computes one row of outputs C0,: for the matrix C, and would move onto the next row in the next time-step. If the dimensions of the matrix exceed he dimensions of the physical array, the computation would need to be tiled.” Further see Section: 4.)
Kung in view of Moon does not appear to explicitly suggest:
determining whether an end condition is not satisfied, wherein the subsequent tiling is performed based on the end condition.
However, Kwon, in combination with Kung and Moon, teaches the limitation:
determining whether an end condition is not satisfied, wherein the subsequent tiling is performed based on the end condition. (Kwon, [0132]-[0134] “the processor 420 or 522 may calculate the data processing time by using a predetermined layer parameter for each layer. The processor 420 or 522 may calculate output feature map data by using data (e.g., tiles) stored in the internal memory 410 or 521. In this case, as a utilization rate (including recycling) of the data stored in the internal memory 410 or 521 decreases, the number of times the processor 20 or 522 accesses the external memory 510 may increase. Therefore, the data processing time of the processor 420 or 522 may increase... In operation 1120, the processor 420 or 522 may identify whether there is an inefficient section during data processing. The method proceeds to operation 1130 when there is an inefficient section and proceeds to operation 1160 when there is an inefficient section.”) [Examiner’s Note: subsequent parameter adjustment (subsequent tiling) based on the condition whether the data processing improved or remains inefficient section.]
Accordingly, at the effective filing date, it would have been prima facie obvious to one ordinarily skilled in the art to modify the combination of Kung and Moon to incorporate the method of processing neural network data as taught by Kwan. One would have been motivated to make such a combination in order to reduce the size of a neural network by changing the structure of the neural network to reduce the amount of calculations and/or quantizing the neural network for faster calculations (Kwan [0073]).
Regarding Claim 10, the combination of Kung, Moon, and Kwan teaches the elements of claim 9 as outlined above, and further teaches:
wherein the end condition is satisfied when a size of a tile corresponding to the feature map and the kernel is less than or equal to a memory budget in a hardware. (Kwan, [0009] “The inefficient section may correspond to a layer of the neural network in which a data size of a generated feature map exceeds the set data size of the set number of tile data blocks.” [0095] “the processor 420 or 522 may use less operation cycles to process the data 720 than to process the data 710, as the processor 420 or 522 may use eight tiles stored in the internal memory 410 or 521 to process the data 720, compared to using fifteen tiles, which may exceed the storage capacity of the internal memory 410 or 521, to process the data 710.” [0137] “The processor 420 or 522 may adjust the layer parameters such that the size of the input data matches the hardware configuration of the data processing apparatus 400 or 520. As an example, the processor 420 or 522 may adjust the layer parameter to increase the size of kernel data related to the inefficient section. As another example, the processor 420 or 522 may adjust the layer parameter to decrease the number of paddings of feature map data related to the inefficient section. As another example, the processor 420 or 522 may adjust the layer parameter to increase the number of strides of the feature map data related to the inefficient section.”)
Regarding Claim 11, the combination of Kung, Moon, and Kwan teaches the elements of claim 10 as outlined above, and further teaches:
providing at least one value corresponding to the tiled feature map and the tiled kernel to the hardware executing the neural network. (Kung also teaches the limitation (see p. 4, Section: 3)). Kwan, also teaches: providing at least one value corresponding to the tiled feature map and the tiled kernel to the hardware executing the neural network. (Kwan, [0142]-[0143] “In operation 630, the processor 420 or 522 may process the data, based on the adjusted layer parameter. For example, the processor 420 or 522 may perform an addition operation on the products of the adjusted kernel data and the input feature map data... as the data processing apparatus 400 or 520 adjusts the layer parameters, the size of the data to be processed may be matched to hardware configuration and thus an inefficient section (i.e., a section in which an operation is inefficiently performed) may be improved during processing of the data.” [0020] “The data may include feature map data corresponding to an input image, and the processing of the data may include identifying features of the input image by performing a convolution operation with the adjusted layer parameter.” Further see [0066].)
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
(Pub. No.: US 20230140173 A1) – “Arnab Raha” relates to “Deep neural network (dnn) accelerators with heterogeneous tiling.”
[Abstract] “A heterogenous tile set includes tiles of different sizes, e.g., PE arrays including different numbers of columns or rows. The DNN accelerator may identify a tile set from the tile sets for running a DNN model based on dimensions of output tensors convolutional layers in the DNN. Within the selected tile set, a tile may be selected for a convolutional layer in the DNN, e.g., based on dimensions of the output tensor of the convolutional layer and the size of the tile. After the tile is selected, the workload for running a convolutional operation of the layer may be partitioned and assigned to individual PEs in the tile by partitioning the output tensor into output tensor segments. The workload of computing an individual output tensor segment can be assigned to an individual PE in the tile.”
See Figure 11.
(Pub. No.: US 20190278600 A1) – “Michael Alex Frumkin” relates to “Tiled compressed sparse matrix format.”
FIG. 5 illustrates an example process 500 for using tiling for sparse matrix multiplication that can be utilized in accordance with various embodiments. See paragraphs [0025]-[0047].
(Pub. No.: US 20220164629 A1) – “Youngcheon You” relates to “Electronic device for compressing convolutional artificial intelligence neural network model and method of controlling the electronic device.”
[Abstract] “The method includes identifying a convolution tensor of the at least one convolution layer; determining a tiling direction for the convolution tensor based on a shape of the convolution tensor; generating a tile matrix from the convolution tensor along the tiling direction; generating a U matrix and a V matrix by performing low rank approximation (LRA) on the tile matrix; and generating a U convolution tensor by recombining the U matrix and generating a V convolution tensor by recombining the V matrix.”
See Paragraph [0064]-[0082].
(Pub. No.: KR 20210113004 A) – “Bernhard Egger” relates to “A method and device for generating a code for a neural network operation.”
The processor 200 may determine from which memory 400 to load data for performing a neural network operation in the processing element 300 . The processor 200 may control the utilization rate of the processing element 300 by adjusting a tiling method of data for a neural network operation. The processor 200 may determine an appropriate tiling method and dataflow for each layer included in the neural network, and generate a code based on the determined tiling method and dataflow. The processor 200 achieves in hardware when performing a neural network operation based on the computing power according to the number of cores used for the neural network operation, the size of data required for the neural network operation, and the memory bandwidth. The maximum performance of a possible operation can be calculated.
NPL: Samajdar, Ananda, et al. "A systematic methodology for characterizing scalability of dnn accelerators using scale-sim." (2020).
[Abstract] “this work makes two major contributions. (i) We describe a cycle-accurate simulator called SCALE-SIM for DNN inference on systolic arrays, which we use to model both scale-up and scale-out systems, modeling on-chip memory access, runtime, and DRAM bandwidth requirements for a given workload. (ii) We also present an analytical model to estimate the optimal scale-up vs scale-out ratio given hardware constraints (e.g, TOPS and DRAM bandwidth) for a given workload.”
Section: II-C describes the Optimal Partitioning for Scale-Out based on aspect ratio.
NPL: Zhang, Chen, et al. "Optimizing FPGA-based accelerator design for deep convolutional neural networks." (2015).
[Abstract] “we quantitatively analyze its computing throughput and required memory bandwidth using various optimization techniques, such as loop tiling and transformation. Then, with the help of roofline model, we can identify the solution with best performance and lowest FPGA resource requirement.”
It describes the CTC Ratio: “Computation to communication (CTC) ratio is used to describe the computation operations per memory access. Data reuse optimization will reduce the total number of memory accesses, thus increase the computation to communication ratio. The computation to communication ratio of the code shown in Figure 9 can be calculated by Equation (4), where α_in, α_out, α_wght and Bin, Bout, Bwght denote the trip counts and buffer sizes of memory accesses to input/output feature maps and weights respectively.”
Apply loop tiling (Figure 5) and Tile size selection based on the roofline model ratio Section: 3.2.
NPL: Park, Chan, Sungkyung Park, and Chester Sungchung Park. "Roofline-model-based design space exploration for dataflow techniques of CNN accelerators." (2020).
NPL: Gu, Peng, et al. "DLUX: A LUT-based near-bank accelerator for data center deep learning training workloads." (2020).
Fig. 8. (b) Inner loop mapping. (a) Data partitioning within a PE. (b) Computation flow and temporal data reuse scheme based on (a).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SADIK ALSHAHARI whose telephone number is (703)756-4749. The examiner can normally be reached Monday - Friday, 9 a.m. 6 p.m. ET.
Examiner interviews are available via telephone, 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, Li Zhen can be reached on (571) 272-3768. 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.
/S.A.A./Examiner, Art Unit 2121
/Li B. Zhen/Supervisory Patent Examiner, Art Unit 2121
Prosecution Insights