DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Drawings
The drawings are objected to under 37 CFR 1.83(a). The drawings must show every feature of the invention specified in the claims. Therefore, the “computer system comprising: a field-programmable gate array (FPGA)… and an electronic processor…” must be shown or the features canceled from the claims. No new matter should be entered.
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(5) because they do not include the following reference sign(s) mentioned in the description: ”FPGA 828” on specification par.96.
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 4, 14, and 18 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Regarding claims 4 and 14, the claim recites “vector addition and matrix extension hardware modules” and “sqrt, vector division, outer product, and vector subtraction hardware modules”. It is unclear if the limitation means:
A plurality of “vector addition and matrix extension hardware module” and a plurality of “sqrt, vector division, outer product, and vector subtraction hardware module”.
Or vector addition hardware module and matrix extension hardware module, and sqrt hardware module, vector division hardware module, outer product hardware module, and vector subtraction hardware module.
Claim 18 recites the limitation "the FIFO channels" in line 2. There is insufficient antecedent basis for this limitation in the claim. For purposes of examination, claim 18 will be treated as if it depends on claim 17, similar to claims 7 and 8.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1-3, 9-10, 11-13, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Thuerck et al. (US 2023/0024035 A1), hereinafter Thuerck, and in view of Ng et al. (NPL: “Block Sparse Cholesky Algorithms on Advanced Uniprocessor Computers”), hereinafter Ng.
Regarding claim 1, Thuerck discloses:
A computer system for Cholesky factorization, the computer system comprising:
a field-programmable gate array (FPGA), the FPGA comprising an FPGA hardware architecture comprising a plurality of hardware processing elements, ["These accelerators could be… programmable FPGAs" par.12; Figure 14, Accelerator Device 1410; Fig.13A+B, 1300]
the FPGA configured to perform kernel operations comprising: performing a supernodal multifrontal algorithm for Cholesky factorization of a matrix, and providing the Cholesky factorization of the matrix ["A sequence of computations is then performed on the index buffers using iBLAS kernels compiled for the accelerator device." par.94; "the one or more kernels can be created by taking a source code for an algorithm, such as a Cholesky decomposition, and modifying the source code to generate the iBLAS Kernels" par.104; “Hence, in the last three decades, the so-called "multifrontal" ( or, more generally, "supernodal") method for sparse matrix factorization has become the de-facto standard.” Par.10]
an electronic processor, the electronic processor communicatively coupled to the FPGA ["where a CPU ("host")… accelerators...need a "host" system for feeding it data and jobs." par.12; "The host device can communicate with the accelerator device 1300 via the bus transmitting instructions and/or data over the bus." Par.119; see figures 13-14],
the electronic processor implementing a host program, the host program configured to perform host operations comprising: identifying dependencies among computation nodes in an elimination tree derived from the matrix, and scheduling the processing elements to perform the Cholesky factorization operations, using temporal parallelism, based on the dependencies ["These data dependencies are rooted in the dynamic creation of buffers (i.e., "frontal matrices") for subsequent amalgamated notes within the elimination tree in the multifrontal method" par.70 "A symbolic analysis can be performed on the block-elimination tree and one or more index buffers with pointers to the blocks are created that represent all frontal matrices that need to be decomposed…". par.94; "frontal matrices may be factored using iBLAS kernels, with nonintersecting nodes being processed in parallel... Second, we can schedule … across branches of the elimination tree… This mode suits pipelined systems such as FPGAs." Par.91; “multiple index buffers are processed sequentially or in parallel, or interleaved…” par.104].
However, Thuerck does not explicitly disclose wherein the supernodal multifrontal algorithm for Cholesky factorization comprises factorize and update operations performed by the processing elements, and providing the Cholesky factorization of the matrix; and scheduling the processing elements to perform the factorize and update operations, using temporal parallelism, based on the dependencies.
In the analogous art of block/supernodal sparse Cholesky algorithms, Ng teaches various supernodal multifrontal algorithm for Cholesky factorization comprises factorize and update operations performed by the processing elements, and providing the Cholesky factorization of the matrix [Sec.2.1 discloses cdiv and cmod functions i.e. factorize and update operations respectively; Sec.2.2-2.3 explains Supernode-based Cholesky and elimination tree; Sec.2.3.2 to Sec.3 and figures 7-8 discloses supernodal multifrontal Cholesky factorization algorithms];
It would have been obvious to one of ordinary skill in the art, to seek out an implementation of Thuerck’s use of the supernodal/multifrontal Cholesky algorithm. As such, it would have been obvious to one of ordinary skill in the art, having the teachings of Thuerck and Ng before him before the effective filing date of the claimed invention to implement the detailed supernodal multifrontal Cholesky algorithm disclosed by Ng into the system of Thuerck, in order to implement a block/supernodal version of the Cholesky algorithm that is proven to be extremely effective on vector supercomputers, allowing data reuse, and efficient on machines with virtual memory and paging [Thuerck: Sec.2.3.2, Sec.5, and Sec.6]. The combination of Thuerck and Ng discloses wherein the supernodal multifrontal algorithm for Cholesky factorization comprises factorize and update operations performed by the processing elements, and providing the Cholesky factorization of the matrix; and scheduling the processing elements to perform the factorize and update operations, using temporal parallelism, based on the dependencies.
Regarding claim 2, Thuerck and Ng disclose the invention substantially as claimed. See the discussion of claim 1 above.
Thuerck discloses wherein the computer system implements the Cholesky factorization of the matrix for one of:
engineering, wherein the Cholesky factorization is implemented in structural analysis ["Finite element simulations (e.g., load simulations on airplanes);" par.5], and
optimization, wherein the Cholesky factorization is implemented in convex optimization [“Linear optimization and Non-linear integer optimization” par.7-8].
Regarding claim 3, Thuerck and Ng disclose the invention substantially as claimed. See the discussion of claim 1 above.
Thuerck discloses wherein the electronic processor comprises a central processing unit (CPU), wherein the CPU is communicatively coupled to the FPGA via a bus ["where a CPU ("host")… accelerators...need a "host" system for feeding it data and jobs." par.12; "The host device can communicate with the accelerator device 1300 via the bus transmitting instructions and/or data over the bus." Par.119].
Regarding claim 9, Thuerck and Ng disclose the invention substantially as claimed. See the discussion of claim 1 above.
Thuerck discloses scheduling the processing elements to perform the Cholesky factorization operations, using temporal parallelism, based on the dependencies [See claim 1].
However, Thuerck does not explicitly disclose wherein the scheduling the processing elements to perform the factorize and update operations comprises: assigning, to each processing element, an update operation for a parent node immediately after a factorize operation for a child node.
In the analogous art of block/supernodal sparse Cholesky algorithms, Ng teaches various supernodal multifrontal algorithm for Cholesky factorization that performs cdiv (factoring) operations for the children then performing update operations after [Sec.2.1 discloses cdiv and cmod functions i.e. factorize and update operations respectively; Sec.2.2-2.3 explains Supernode-based Cholesky and elimination tree; Sec.2.3.2 to Sec.3 and figures 7-8 discloses supernodal multifrontal Cholesky factorization algorithms; See Section 4.3 which discloses child, parent, grandparent nodes/supernodes];
It would have been obvious to one of ordinary skill in the art, to seek out an implementation of Thuerck’s use of the supernodal/multifrontal Cholesky algorithm. As such, it would have been obvious to one of ordinary skill in the art, having the teachings of Thuerck and Ng before him before the effective filing date of the claimed invention to implement the detailed supernodal multifrontal Cholesky algorithm disclosed by Ng into the system of Thuerck, in order to implement a block/supernodal version of the Cholesky algorithm that is proven to be extremely effective on vector supercomputers, allowing data reuse, and efficient on machines with virtual memory and paging [Thuerck: Sec.2.3.2, Sec.5, and Sec.6]. the combination of Thuerck and Ng discloses the additional limitations of the claim.
Regarding claim 10, Thuerck and Ng disclose the invention substantially as claimed. See the discussion of claim 1 above.
Thuerck discloses wherein the matrix is sparse ["An input matrix, which is a sparse matrix with zero and non-zero scalar values, is processed in such a way ( e.g., via permutation operations) that dividing the input matrix into a plurality of blocks minimizes the number of blocks that contain non-zero scalar values" par.93].
Ng teaches wherein the matrix is sparse ["These are sparse operations requiring indirect indexing because an update matrix generally modifies a proper subset of the entries in the target frontal matrix. These are the only sparse operations required by the multifrontal method." p.10].
Claims 11-13, and 19-20 are directed to claims 1-3 and 9-10, respectively. A mere change in statutory class is obvious. The claims are rejected for the reasons given above.
Claims 4 and 14 are rejected under 35 U.S.C. 103 as being unpatentable over Thuerck and Ng, and in view of Sun et al. (NPL: “Sparse Cholesky Factorization on FPGA using Parameterized Model", see IDS filed 08/14/2023), hereinafter Sun.
Regarding claim 4, Thuerck and Ng disclose the invention substantially as claimed. See the discussion of claim 1 above.
Thuerck discloses a field-programmable gate array (FPGA), the FPGA comprising an FPGA hardware architecture comprising a plurality of hardware processing elements, ["These accelerators could be… programmable FPGAs" par.12; Figure 14, Accelerator Device 1410; Fig.13A+B, 1300]
However, Thuerck and Ng does not explicitly disclose wherein each hardware processing element comprises: vector addition and matrix extension hardware modules responsible for the update operation; and sqrt, vector division, outer product, and vector subtraction hardware modules responsible for the factorize operation.
In the analogous art of sparse Cholesky algorithms and architectures, Sun teaches a vector architecture including hardware modules for extended addition, Sqrt, division, multiplication, and subtraction [Fig.1, Sec.3.2; see Algorithms 2-4]
It would have been obvious to one of ordinary skill in the art, having the teachings of Thuerck, Ng, and Sun before him before the effective filing date of the claimed invention to modify the elements within the FPGA disclosed by Thuerck, to implement the Vector Architecture of Sun, in order to implement an dedicated FPGA Architecture to compute the operations required for the Cholesky factorization allowing for improved parallel operations, high bandwidth, and better performance [Sun: Sec.1, Sec.3.2, and Sec.4-5]. The combination of Thuerck, Ng, and Sun discloses the additional limitations of the claim.
Claim 14 is directed to claim 4. A mere change in statutory class is obvious. The claims are rejected for the reasons given above.
Claims 5 and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Thuerck and Ng, and in view of Soltaniyeh et al. (NPL: “Synergistic CPU-FPGA Acceleration of Sparse Linear Algebra" see IDS filed 08/14/2023), hereinafter Sun.
Regarding claim 5, Thuerck and Ng disclose the invention substantially as claimed. See the discussion of claim 1 above.
Thuerck and Ng does not explicitly disclose wherein the computer system avoids off-chip memory access for intermediate data in performing the supernodal multifrontal algorithm for Cholesky factorization.
In the analogous art of CPU-FPGA architectures, Soltaniyeh teaches that FPGAs avoids off-chip memory access for intermediate data in performing the Cholesky factorization ["When accesses are regular the FPGA can provide significant acceleration for computation compared to a CPU because it can execute thousands of floating point operations using digital signal processing (DSP) units with support for fused-multiply-add operations, and its high throughput distributed on-chip memory can store intermediate results, thus avoiding write-backs to DRAM." Sec.II: Regularizing the FPGA data access; “This is especially useful in sparse linear algebra kernels such as sparse Cholesky factorization with data dependency.” Sec.II: RIR includes scheduling].
It would have been obvious to one of ordinary skill in the art, having the teachings of Thuerck, Ng, and Soltaniyeh before him before the effective filing date of the claimed invention to modify the FPGA disclosed by Thuerck, to implement the Pipelined variant of the FPGA taught by Soltaniyeh, in order to implement an pipelined FPGA Architecture provide acceleration over CPU and avoiding off-chip access for intermediate results [Soltaniyeh: Sec.II: Regularizing the FPGA data access]. The combination of Thuerck, Ng, and Soltaniyeh discloses the additional limitations of the claim.
Claim 15 is directed to claim 5. A mere change in statutory class is obvious. The claims are rejected for the reasons given above.
Claims 6 and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Thuerck and Ng, and in view of Nicol (US 2018/0181503 A1).
Regarding claim 6, Thuerck and Ng disclose the invention substantially as claimed. See the discussion of claim 1 above. Thuerck and Ng does not explicitly disclose wherein the plurality of processing elements are communicatively coupled to each-other via at least one first-in-first- out (FIFO) channel.
In the analogous art of high performance computing, Nicol teaches wherein the plurality of processing elements are communicatively coupled to each-other via at least one first-in-first-out (FIFO) channel [“FIFO is dynamically configured between a pair of neighboring processing elements" par.11; See figure 1, and 3].
It would have been obvious to one of ordinary skill in the art, having the teachings of Thuerck, Ng, and Nicol before him before the effective filing date of the claimed invention to modify the elements within the FPGA disclosed by Thuerck, to implement FIFOs between processing elements taught by Nicol, Allowing for more flexible data handling, provide efficient and scalable dataflow processing, improved latencies and data manipulation [Nicol: par.11 and 30-31]. The combination of Thuerck, Ng, and Nicol discloses the additional limitations of the claim.
Claim 16 is directed to claim 6. A mere change in statutory class is obvious. The claims are rejected for the reasons given above.
Claims 7-8 and 17-18 are rejected under 35 U.S.C. 103 as being unpatentable over Thuerck and Ng, and in view of Moreau et al. (NPL: “A Hardware-Software Blueprint for Flexible Deep Learning Specialization”), hereinafter Moreau, and further in view of Nicol.
Regarding claim 7, Thuerck and Ng disclose the invention substantially as claimed. See the discussion of claim 1 above.
Thuerck discloses a load unit for loading data into the processing elements and a load unit for storing the data from the processing elements, and providing a function for each processing element [Fig.13B; “The functional units 1360 can be the same, such as to process multiple blocks in parallel, or different, such as to implement multiple functions on the same block data” Par.125]
However, Thuerck and Ng does not explicitly disclose a respective load module for each of the processing elements, wherein each processing element is communicatively coupled to its respective load module via at least one FIFO channel; and a respective store module for each of the processing elements, wherein each processing element is communicatively coupled to its respective store module via at least one FIFO channel.
In the analogous art of Architectures for FPGAs, Moreau teaches wherein a task pipeline comprises a load module, compute module, and store module [Fig.3].
It would have been obvious to one of ordinary skill in the art, having the teachings of Thuerck, Ng, and Moreau before him before the effective filing date of the claimed invention to include the store and load modules for each processing element as taught by Moreau into the FPGA disclosed by Thuerck, in order to implement concurrent storing, loading, and computing operations, maximizing compute and memory resource utilization [Moreau: Sec.3.1]. The combination of Thuerck, Ng, and Moreau discloses a respective load module for each of the processing elements, wherein each processing element is communicatively coupled to its respective load module; and a respective store module for each of the processing elements, wherein each processing element is communicatively coupled to its respective store module.
However, Thuerck, Ng, and Moreau does not explicitly disclose FIFO channels.
In the analogous art of high performance computing, Nicol teaches within a reconfigurable system, using FIFO to coordinate the flow of data [“An agent executing in software on each processing element interacts with dynamically established first-in-first-out (FIFO) buffers to coordinate the flow of data.” Par.28; “The process agent retrieves data from one or more FIFOs and outputs data to one or more FIFOs.” Par.32].
It would have been obvious to one of ordinary skill in the art, having the teachings of Thuerck, Ng, Moreau, and Nicol before him before the effective filing date of the claimed invention to modify the flows/buffers of datapath of the FPGA disclosed by Thuerck and Moreau, to use FIFOs as taught by Nicol, in order to allow for dynamically scaling FIFOs that improves efficiency, and reduces downtime [Nicol: par.28-31]. The combination of Thuerck, Ng, Moreau, and Nicol discloses the additional limitations of the claim.
Regarding claim 8, Thuerck, Ng, Moreau, and Nicol disclose the invention substantially as claimed. See the discussion of claim 7 above. Thuerck, Ng, and Moreau does not explicitly disclose the additional limitations of the claim.
In the analogous art of high performance computing, Nicol teaches wherein depths of the FIFO channels are determined by an offline compiler [“Flow 100… dataflow graph 114… The dataflow graph may be processed as an input by an automated tool such as a compiler... The output of the compiler may include instructions for reconfiguring processing elements…The reconfiguring can also include insertion of a FIFO between two processing elements of a plurality of processing elements.” Par.43; “Offline operations can include software subsystems such as compilers, linkers, simulators, emulators, and so on.” Par.67; see par.32-42 which talks about the size of the FIFO and includes inserting the FIFOs]
It would have been obvious to one of ordinary skill in the art, having the teachings of Thuerck, Ng, Moreau, and Nicol before him before the effective filing date of the claimed invention to modify the flows/buffers of datapath of the FPGA disclosed by Thuerck and Moreau, to use FIFOs as taught by Nicol, in order to allow for dynamically scaling FIFOs that improves efficiency, and reduces downtime [Nicol: par.28-31]. The combination of Thuerck, Ng, Moreau, and Nicol discloses the additional limitations of the claim.
Claims 17-18 are directed to claims 7 and 8, respectively. A mere change in statutory class is obvious. The claims are rejected for the reasons given above.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Vandenberghe et al. (NPL: “Chordal Graphs and Semidefinite Optimization”) discloses Cholesky factorization, supernodal Cholesky, convex cones, and convex optimization problems. See Abstract, Chapters 9-10 and 13, and Sec.9.4.
Seeger (NPL: "Low Rank Updates for the Cholesky Decomposition") discloses Cholesky factorization can be used in machine learning. See abstract.
Kang et al. (NPL: "An Improved Modified Cholesky Decomposition Approach for Precision Matrix Estimation") discloses the use of Cholesky factorization in regression problems and estimator for covariance. See p.3 and p.10.
Van Zandt (NPL: “Efficient Covariance Encoding”) discloses Cholesky factor, Covariance, and Mahalanobis distance. See abstract and Sec.2.1
Besson et al. (NPL: “Properties of the partial Cholesky factorization and application to reduced-rank adaptive beamforming”) discloses Adaptive filtering, finance portfolios and Cholesky factorization. See Sec.1.
Fang et al. (NPL: "An efficient radial basis function mesh deformation with greedy algorithm based on recurrence Cholesky decomposition and parallel computing”) discloses mesh deformation and Cholesky decomposition. See abstract.
Li et al. (NPL: “Accelerating Sparse Cholesky Factorization on Sunway Manycore Architecture”) discloses task queues, update and factor functions, supernodal Cholesky and parent/child operations. See figure 3.
M.I.T. (NPL: “Computation Structures: Performance Measures”) discloses basics of pipelining and benefits of breaking up functions with multiple functions into separated pipelined parts. See Sec.11.5.
Rouet (NPL: “Memory and performance issues in parallel multifrontal factorizations and triangular solutions with sparse right-hand sides”) discloses the operations of extend-add operator for frontal matrices. See p.7.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Kenny K. Bui whose telephone number is (571)270-0604. The examiner can normally be reached 8:00 am to 3:00 pm on Monday, 8:00 am to 4:00 pm on Tuesday to Friday ET.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Andrew T Caldwell can be reached at (571)272-3702. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/KENNY K. BUI/Patent Examiner, Art Unit 2182 (571)270-0604
/ANDREW CALDWELL/Supervisory Patent Examiner, Art Unit 2182
Prosecution Insights