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 .
Remarks
[0109] defines the term “computer-readable storage medium” is not a transitory.
Claim Objections
Claims 7 and 14-20 are objected to because of the following informalities:
Claim 7 line 3; claim 14 line 3; claim 20 line 6 “the operand matrices” should be “the plurality of operand matrices” as antecedently recited.
Claim 15 line 1-2 “one or more computer readable storage mediums” should be “one or more computer-readable storage media” as media refers to plural and to recite “computer-readable” as defined in [0109].
Dependent claims are also rejected for inheriting the same deficiencies in which claims they depend on.
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.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Claim 1 recites a method claim
Under Prong One of Step 2A of the USPTO current eligibility guidance (MPEP 2106), the claim recites a method comprising generating a formulation of the matrix multiply operation based on the parameters (see at least figure 5 step 504 includes generating mathematical formulation, such as SMT based on the variables); determining a matrix multiply solution for performing the matrix multiply operation, wherein the matrix multiply solution specifies a spatial and temporal partitioning of the matrix multiply operation, and partition input data (see at least figure 5 step 508 determining an optimal solution that specifies partitioning operation [0076]). Such limitations cover mathematical calculations, relationship, and/or formula. Therefore, the claim includes limitations that fall within the “Mathematical Concepts” grouping of abstract ideas. Accordingly, the claim recites an abstract idea.
Under Prong Two of Step 2A, this judicial exception is not integrated into a practical application. The claim recites the additional elements of computer hardware, data processing array, interface, and external memory, but such additional elements are merely recited at a high level of generality, e.g., computer components performing computer function of processing and storing data. The claim further recites the step of receiving parameters defining a matrix multiply operation to be implemented in a data processing array, transfer input from memory to array and result from array to memory, such step of receiving, transmitting, and storing data are at most considered as insignificant extra/post solution activities as they are mere data gathering. Moreover, the step of generating synthesizable program code is also considered as insignificant extra solution activity as such step is known in programming FPGA circuit. Accordingly, such additional elements fail to provide a meaningful limitation on the claim invention, and amount to no more than mere instructions to apply the exception using computer elements. Thus, the claim as a whole does not integrate the exception into a practical application
Under Step 2B, as discussed with respect to Prong Two of Step 2A, the additional elements in the claim amount no more than mere instructions to apply the exception using computer components. The same conclusion is reached in step 2B, i.e., mere instructions to apply an exception on computer components cannot integrate a judicial exception into a practical application at step 2A or provide an inventive concept that is furnished by an element or combination of elements that is recited in the claim in addition to (beyond) the judicial exception. The step of receiving, transferring, and storing considered to be insignificant extra/post solution activities in step 2A, and are determined to be well-understood, routine, conventional activity in the field. Court decisions cited in MPEP 2106.05(d)(II) section (i), indicate that mere receiving or transmitting data over a network and (iv) storing and retrieving information in memory are well known when reciting in a generic manner. Moreover, the concept of generating synthesizable program code defining an interface is also considered insignificant extra solution activity under step 2A and is determined to be well-understood, routine, and conventional under step 2B (see Munden, Richard. ASIC and FPGA Verification : A Guide to Component Modeling, Elsevier Science & Technology, 2004, page 8 describes the step of generating an RTL code that defines interface of the FPGA. Thus, generating synthesizable program code and synthesizing such code to program the FPGA is conventional activity). Thus, the additional element fails to ensure the claim as a whole amount to significantly more than the judicial exception itself. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 2 further recites wherein the formulation is a Satisfiability Modulo Theory (SMT) formulation, the determining the matrix multiply solution based on the SMT formulation provided as input. Such limitation covers mathematical calculations, relationship, and/or formula (merely describes determining the optimal solution based on the SMT formulation). The claim further recites executing an SMT solver, such additional element is recited at a high level of generality, e.g., computer component performing functions, as [0047] describes SMT solver is merely a computer program. Thus, such additional element recites at a high level and amounts to no more than mere instructions to apply the judicial exception using computer program. Thus, the claim does not recite additional elements that would integrate the judicial exception into a practical application under step 2A or provide significantly more under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 3 further recites synthesizing the synthesizable program code to generate a circuit design for the interface for the data processing array. Under step 2A prong two, such step of synthesizing the synthesizable program code to generate a circuit design is at most considered as insignificant extra solution activity, and determined to be well-understood, conventional activity under step 2B (see Munden, Richard. ASIC and FPGA Verification : A Guide to Component Modeling, Elsevier Science & Technology, 2004, page 8 describes the step of synthesizing the RTL code to generate a circuit design. Thus, the claim does not recite additional elements that would integrate the judicial exception into a practical application under step 2A or provide significantly more under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 4 further recites for the matrix multiply operation, the input data corresponds to a plurality of operand matrices and the output data corresponds to a result matrix. Such limitation covers mathematical calculations, relationship, and/or formula (merely describes the input data and the output data of the matrix multiplication operation). The claim further recites the synthesizable program code defines a number of input ports configured to convey the input data from each operand matrix of the plurality of operand matrices and a number of output ports for conveying the output data of the result matrix. Such concept of having the synthesizable program code to define inputs ports and outputs of the circuit design for FPGA is at most considered as insignificant extra solution activity under step 2A prong two and determined to be well-understood, routine, and conventional under step 2B (see Munden, Richard. ASIC and FPGA Verification : A Guide to Component Modeling, Elsevier Science & Technology, 2004, page 8 describes the RTL code that generate a circuit design of a selector and a latch, wherein the selector includes 2 input ports for receiving D0 and D1, an output port that connects to input of that latch to output signal D0 and D1 based on the sel signal, the code also defines the clock input and Q output. Thus, the claim does not recite additional elements that would integrate the judicial exception into a practical application under step 2A or provide significantly more under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 5 further recites wherein the input ports are configured to load corresponding batches of data of each operand matrix from the external memory to the data processing array based on the spatial and temporal partitioning for each input matrix. The concept of loading data from input ports from external memory are considered as insignificant extra solution activity under step 2A prong two and determined to be well-understood, routine, and conventional activity under step 2B (See MPEP 2106.05(d)(II)(i) Receiving or transmitting data over a network and (iv) Storing and retrieving information in memory), and loading data based on the spatial and temporal partitioning for each input matrix is merely flowing from the mathematical operation of partition. Thus, the claim does not recite additional elements that would integrate the judicial exception into a practical application under step 2A or provide significantly more under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claims 6-7 further recites the synthesizable program code that defines accumulation circuitry for the output ports, wherein the accumulation circuitry is configured to accumulate partial results on the output ports to generate a result batch for each corresponding set of batches of data from the operand matrices. The step of accumulating partial results to generate a result batch for each corresponding set of batches of data from the operand matrices cover mathematical calculations, relationship, and/or formula under step 2A prong one, and as explained above, the concept of having a synthesizable program code to define circuit design for FPGA is considered as insignificant extra solution activity under step 2A prong two and determined to be well-understood, routine, and conventional under step 2B (see Munden, Richard. ASIC and FPGA Verification : A Guide to Component Modeling, Elsevier Science & Technology, 2004, page 8 describes the RTL code that generate a circuit design of a selector and a latch. Thus, defining accumulation circuitry is merely a result of the mathematical expression from the code, such that if the RTL code is to perform MAC operation, then such RTL code would generate circuit design having multiplier and accumulator circuitries to perform the MAC operation. Thus, the claims do not recite additional elements that would integrate the judicial exception into a practical application under step 2A or provide significantly more under step 2B. Accordingly, the claims are not patent-eligible under 35 U.S.C. 101.
Claims 8-14 recite apparatus claims that would practice the method claims 1-7. Thus, they are rejected for the same reasons. Furthermore, claim 8 recites a system comprising one or more hardware processors, such additional elements are recited at a high level of generality, e.g., computer components performing computer functions, which amounts to no more than mere instructions to apply the judicial exception using computer components. Thus, the claims do not recite additional elements that would integrate the judicial exception into a practical application under step 2A or provide significantly more under step 2B. Accordingly, the claims are not patent-eligible under 35 U.S.C. 101.
Claims 15-20 recite product claims having similar limitations as method claims 1-7. Thus, they are rejected for the same reasons. Furthermore, claim 15 recites a computer program product comprising one or more computer readable storage mediums having program instructions embodied therewith, the program instructions executable by computer hardware to cause the computer hardware to initiate executable operations, such additional elements are recited at a high level of generality, e.g., computer components performing computer functions of storing and executing instructions, which amount to no more than mere instructions to apply the judicial exception using computer components. Thus, the claims do not recite additional elements that would integrate the judicial exception into a practical application under step 2A or provide significantly more under step 2B. Accordingly, the claims are not patent-eligible under 35 U.S.C. 101.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1, 3-8, 10-15, 17-20 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Wang - NPL AutoSA: A Polyhedral Compiler for High-Performance Systolic Array on FPGA.
Regarding claim 1, Wang teaches a method, comprising:
receiving, using computer hardware, parameters defining a matrix multiply operation to be implemented in a data processing array (Wang figure 4 illustrates a compilation method that is executed on Xilinx Alveo U250 [i.e., a computer hardware] that receives code C as illustrated in figure 1 having information of dimensions of N, M, K of matrices [i.e., parameters] that defines A*B [i.e., a matrix multiply operation] implemented on an array of processing elements [i.e., a data processing array] as illustrated in figure 3B);
generating, using the computer hardware, a formulation of the matrix multiply operation based on the parameters (Wang, figure 4 illustrates generating a polyhedral model [i.e., a formulation] based on the parameters in C to optimize PE arrays as section 3.1 describes the polyhedral model is a mathematical framework for loop nest optimization);
determining, using the computer hardware, a matrix multiply solution for performing the matrix multiply operation in the data processing array (Wang page 96 describes AutoSA includes computation management, sections 4.2 and 5 describes the construction and optimization PE arrays using space-time transformation and array partition. Thus, Wang generates an optimized configuration [i.e., a matrix multiply solution] for performing A*B in the PE arrays, also see figure 3A), wherein the matrix multiply solution specifies a spatial and temporal partitioning of the matrix multiply operation for implementation in the data processing array (Wang page 96 section 5 describes the space-time transformation that performs mapping to specifies a space [i.e., spatial] and time [i.e., temporal partition of the matrix multiplication operation of A*B for implementing in the PE array, also see figure 3A); and
generating, using the computer hardware, synthesizable program code defining an interface for the data processing array based on the matrix multiply solution (Wang page 96 figure 4 illustrates a step that generates target hardware code HLS C [i.e., synthesizable program code] defines I/O network [i.e., an interface] for the array based on the optimized configuration [i.e., the matrix multiply solution], also describes in section 6.2 page 98 I/O construction for transferring data between PEs and external memory), wherein the interface is configured to partition and transfer input data to the data processing array from an external memory and convey output data from the data processing array to the external memory (Wang, page 98 section 6.2 describes I/O constructions to partition data based on loops and transfer between PEs and external memory. Figure 10B illustrates optimized array having I/O network partitions and transfers input data of matrix A and B to the PE array from a DRAM [i.e., an external memory] and also convey output data from PE array back to the external memory DRAM).
Regarding claim 3, Wang teaches the method of claim 1, further comprising: synthesizing the synthesizable program code to generate a circuit design for the interface for the data processing array (Wang figure 4 illustrates the step of synthesizing the HLS C [i.e., the synthesizable program code] to generate an optimized array [i.e., a circuit design] for the I/O network for the PE array in FPGA).
Regarding claim 4, Wang teaches the method of claim 1, wherein: for the matrix multiply operation, the input data corresponds to a plurality of operand matrices and the output data corresponds to a result matrix (Wang figure 1 illustrates the matrix multiplication operation A*B, wherein the input data A and B corresponds to a plurality of operand matrices and the output data C corresponds to a result matrix); and
the synthesizable program code defines a number of input ports configured to convey the input data from each operand matrix of the plurality of operand matrices and a number of output ports for conveying the output data of the result matrix (Wang figure 4 illustrates the HLS C [i.e., the synthesizable program code] defines computation and communication management for the optimized array having I/O network as illustrated in figure 10B for supplying the operand matrices A and B to the PE array, wherein Wang figure 10B illustrates separate I/O communication paths for conveying A and B data from external DRAM into the PE array and an I/O communication path for conveying result C back to external DRAM. Thus, the HLS C defines the number of input and output ports to convey matrices A, B, and C).
Regarding claim 5, Wang teaches the method of claim 4, wherein the input ports are configured to load corresponding batches of data of each operand matrix from the external memory to the data processing array based on the spatial and temporal partitioning for each input matrix (Wang figure 10B illustrates the input ports load portions of data of each operand matrix A and B within the loop from DRAM [i.e., external memory] to the PE array based on space loops and time loops of each matrix A and B as illustrated figure 1).
Regarding claim 6, Wang teaches the method of claim 5, wherein the synthesizable program code defines accumulation circuitry for the output ports (Wang figure 1 illustrates the matrix operation that includes C += A*B or C = C + A*B. Thus, Wang teaches the accumulation operation for a plurality of space loops and the AutoSA constructs the PE array implementation for this computation and generate systolic array design as HLS C. Thus, the generated HLS C code defines accumulation circuitry to implement the accumulation for the output port C. Also see figure 11B illustrates each PE includes MAC and buffC circuit to perform accumulation operation, thus a plurality of MAC and BuffC circuit in the PE array corresponds to accumulation circuitry for the output ports).
Regarding claim 7, Wang teaches the method of claim 6, wherein the accumulation circuitry is configured to accumulate partial results on the output ports to generate a result batch for each corresponding set of batches of data from the operand matrices (Wang figures 1 and 11B describes the accumulation operation to accumulate partial results of A and B on k dimension on the output ports to generate a result of corresponding C[i,j] [i.e., a result batch] for each corresponding set of i and j [i.e., set of batches of data] from the operand matrices).
Claims 8, and 10-14 recite apparatus claims that would practice the method claims 1, and 3-7, respectively. Thus, they are rejected for the same reasons. The claim 8 further recites a system comprising one or more hardware processors (Wang abstract teaches the AutoSA compiler for the FPGA Xilinx Alveo U250. Thus, a host computer along with the FPGA Xilinx Alveo corresponds to a system, and the hose computer that executes the AutoSA compilation framework corresponds to one or more hardware processors)
Claims 15, and 17-20 recite product claims having similar limitations as the method claims 1, and 3-7, respectively. Thus, they are rejected for the same reasons. The claim 15 further recites a computer program product comprising one or more computer readable storage mediums having program instructions embodied therewith, the program instructions executable by computer hardware to cause the computer hardware to initiate executable instructions (Wang abstract teaches the AutoSA frame work is compiler and as a software compilation framework, the AutoSA comprises program instructions that are stored in memory to be executed by a computer hardware to perform the operations of the framework)
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 2, 9, and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Wang in view of Yuan - NPL Hardware/Software Partitioning and Static Task Scheduling on Runtime Reconfigurable FPGAs using SMT solver.
Regarding claim 2, Wang teaches the method of claim 1, but does not teach the formulation is a Satisfiability Modulo Theory (SMT) formulation and the determining the matrix multiply solution is performed by executing an SMT solver with the SMT formulation provided as input. However, Yuan teaches formulating a Satisfiability Modulo Theory (SMT) formulation and the determining the partition and task scheduling solution is performed by executing an SMT solver with the SMT formulation provided as input (Yuan Abstract, formulating and solving an optimal hardware/software partitioning and static task scheduling problem for FPGA-based computing in the framework of Satisfiability Modulo Theory (SMT) using linear integer arithmetic to provide an optimal solution for designing the FPGA)
It would have been obvious to one of ordinary skill in the art before the effective filing date to substitute Yuan’s SMT-based solving technique for Wang’s exhausting search technique for auto tuning as described in section 7.2 page 100. This modification would have been obvious because both techniques solve constrained FPGA design optimization problem to provide an optimal design. Furthermore, the claim would have been obvious because the substitution of one known element for another would have yielded predictable results to one of ordinary skill in the art, which is to provide optimal design for FPGA. See MPEP 2141(III)(B) Simple substitution of one known element for another to obtain predictable results.
Claims 9 and 16 recite system and product claims having similar limitation as claim 2. Thus, they are rejected for the same reasons.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Zang - US 20210200521 teaches A system and method is provided for optimizing general matrix multiplication on target hardware by splitting matrices to be multiplied into tiles and formulating a tiling configuration search problem for matrices to be multiplied that explores a configuration search space to identify an optimal tiling configuration that minimizes running time on the target hardware for multiplication of matrices A and B on the target hardware for respective configuration states as a function of matrix parameters m, k, and n, and numbers of respective nested loops for each dimension m, k, and n, respectively. The optimal tiling configuration for the target hardware is obtained by implementing a Greedy Best-First-Search (GBFS) algorithm or a Neighborhood Actor Advantage Critic (N-A2C) algorithm that optimizes the running time for multiplication of the matrices on the target hardware.
Moon - NPL Evaluating Spatial Accelerator Architectures with Tiled Matrix-Matrix Multiplication - teaches a framework that finds optimized mapping (dataflow and tile sizes) for a given spatial accelerator. Figure 1 illustrates a framework that receives parameters inputs and generate an optimized mapping that specifies the spatial and temporal partitioning of the operation as illustrated in figure 5.
Tian - NPL SASA A Scalable and Automatic Stencil Acceleration Framework for Optimized Hybrid Spatial and Temporal Parallelism on HBM-based FPGAs - teaches an approach for accelerator design optimization and an end to end automation framework that takes the high level DSL and FPGA platform as inputs and automatically generates the optimized FPGA design with best parallelism configuration on that FPGA. Page 1-24 describes a configuration of hybrid parallelism design that also performs both temporal and spatial parallelism.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to HUY DUONG whose telephone number is (571)272-2764. The examiner can normally be reached Mon-Friday 7:30-5:30.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Andrew Caldwell can be reached at (571) 272-3702. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/HUY DUONG/Examiner, Art Unit 2182 (571)272-2764
/ANDREW CALDWELL/Supervisory Patent Examiner, Art Unit 2182
Prosecution Insights