DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
This Action is Non-Final and is in response to the claims filed 09/25/2022. Claims 1-20 are currently pending, of which claims 1-20 are currently rejected.
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 “variables are stored on a first memory and referencing the weight matrix includes accessing a second memory on which the weight matrix is stored, the second memory being separate from the first memory” first disclosed in claim 4 must be shown or the feature(s) canceled from the claim(s). No new matter should be entered.
Additionally, 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: Variables 305 first disclosed in ¶0039 of the specification.
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 § 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.
Apparatus claims 8-14 and 20 will be addressed before corresponding method claims 1-7, and corresponding media claims 15-19.
Regarding Claim 8, at Step 1 the claim is directed to a system, which is a statutory category of invention.
At Step 2A, Prong 1, Examiner notes that claims are directed to mathematical concepts:
A system, comprising:
one or more processors, each of the processors including a plurality of computing cores;
a local memory;
an off-chip memory; and
one or more non-transitory computer-readable storage media configured to store instructions that, in response to being executed by the local memory, cause the system to perform operations (mathematical calculations), the operations comprising:
obtaining a plurality of variables that each represent a characteristic related to an optimization problem;
obtaining weights that correspond to the variables, each respective weight relating to one or more relationships between a respective variable and one or more other variables related to the optimization problem (mathematical calculations);
dividing the variables into a plurality of groups in which each respective group includes a sub-set of variables of the plurality of variables (mathematical relationships);
obtaining a respective group local field matrix for each respective group of variables, each respective local field matrix including local field values that each indicate interactions between a respective variable and the other variables of the plurality of variables, as influenced by the respective weights of the respective variables (mathematical relationships);
performing a semi-sequential trial process with respect to the plurality of groups, the semi-sequential trial process including:
performing, based on first weights and first local field values that correspond to a first group of first variables of the plurality of groups, a first stochastic process with respect to the first group, the first stochastic process being with respect to changing a respective state of one or more of the first variables of the first group, the first stochastic process including performing first trials with respect to one or more of the first variables in which a respective first trial determines whether to change a respective state of a respective first variable (mathematical relationships/calculations);
updating all of the group local field matrices based on results of the first stochastic process (mathematical relationships/calculations);
performing, based on second weights and second local field values that correspond to a second group of second variables of the plurality of groups, a second stochastic process with respect to the second group, the second stochastic process being with respect to changing a respective state of one or more of the second variables of the second group, the second stochastic process including performing second trials with respect to one or more of the second variables in which a respective second trial determines whether to change a respective state of a respective second variable (mathematical relationships/calculations); and
updating all of the group local field matrices based on results of the second stochastic process (mathematical relationships/calculations); and
determining a solution to the optimization problem based on the semi-sequential trial process (mathematical calculations).
At Step 2A Prong 2, the additional element is bolded above. This additional elements are merely
an “apply it” scenario using generically recited computer components. See MPEP 2106.05 (f).
The “A system, comprising: one or more processors, each of the processors including a plurality of computing cores; a local memory; an off-chip memory; and one or more non-transitory computer-readable storage media configured to store instructions that, in response to being executed by the local memory, cause the system to perform” limitation simply uses generic computer components to perform the mathematical relationships/calculations (operations). Alternatively, even if not considered as merely an ”apply it” scenario, this type of architecture of a system using a multi-core processor is well understood routine and conventional. See Step 2B analysis below
Additionally, the italicized limitations above are describing insignificant extra-solution activity
used for the processing of the mathematical concepts.
At Step 2B, there are no additional elements claimed that amount to significantly more than the
recited judicial exception.
Regarding the architecture of the system, this is a well understood routine and conventional architecture known to be used in generic computers. As per the book Computer Organization and Design : The Hardware/Software Interface, Chapter 1: Computer Abstractions and Technology, “Many embedded processors are designed using processor cores” (Page 6: Last paragraph), “The five classic components of a computer are input, output, memory, datapath, and control, with the last two sometimes combined and called the processor.” (Page 15: The BIG Picture), and “Descending into the depths of any component of the hardware reveals insights into the machine. The memory in Figure 1.10 is built from DRAM chips. DRAM stands for dynamic random access memory. Several DRAMs are used together to contain the instructions and data of a program.” (Page 20: Last paragraph). These limitations therefore are considered well understood routine and conventional even upon consideration. Thus, these limitations do not amount to significantly more.
In regards to the insignificant extra-solution activity found in the Italicized limitations, the “store instructions that, in response to being executed” limitation describe mere data storing and execution recited at a high level of generality. Per the book Computer Organization and Design : The Hardware/Software Interface, Chapter 1: Computer Abstractions and Technology “Several DRAMs are used together to contain the instructions and data of a program.” (Page 20: Last paragraph), and “the software systems used to create and translate the program into machine instructions, and the effectiveness of the computer in executing those instructions” (Page 10: Understanding Program Performance). The “obtaining” limitations describe mere data transmitting recited at a high level of generality. Per MPEP 2106.05(d)(II), the courts have recognized the following computer functions as well-understood, routine, and conventional functions when they are claimed in a merely generic manner (e.g., at a high level of generality) or as insignificant extra-solution activity: i. Receiving or transmitting data over a network, e.g., using the Internet to gather data, Symantec, 838 F.3d at 1321, 120 USPQ2d at 1362. Therefore, data transmitting is considered as a computer function that is a well-understood, routine, and conventional function when claimed in a merely generic manner. These limitations therefore remain insignificant extra-solution activity even upon consideration. Thus, these limitations do not amount to significantly more.
Claim 9 is directed to the mathematical concept of weight data corresponding to variables (mathematical relationships). Under Steps 2A prong 2 and 2B, the claim does not recite any additional elements that integrate the abstract idea into a practical application nor do they amount to significantly more than the judicial exception.
Claim 10 is directed to the mathematical concept of weight data corresponding to variables (mathematical relationships). Under Steps 2A prong 2 and 2B, the claim does not recite any additional elements that integrate the abstract idea into a practical application nor do they amount to significantly more than the judicial exception.
Claim 11 is directed to the mathematical concept of weights and variables (mathematical relationships). Moreover, none of the additional elements regarding generic computer components (i.e., first memory, second memory) are more than high level generic computer components that simply provide data to be used for the mathematical calculations. Additionally, as explained in the Step 2B analysis of claim 8, mere data storing and transferring is an insignificant extra-solution activity even upon consideration.
Claim 12 is directed to the mathematical concept of updating temperatures based on a stochastic process (mathematical relationships/calculations). Under Steps 2A prong 2 and 2B, the claim does not recite any additional elements that integrate the abstract idea into a practical application nor do they amount to significantly more than the judicial exception.
Claim 13 is directed to the mathematical concept of dividing variables (mathematical relationships). Moreover, none of the additional elements regarding the generic computer components (i.e., computing cores of a computer system) are more than high level generic computer components that amount to mere instructions to apply the abstract idea on a generic computer. See MPEP 2106.05(f). Even if not considered an apply it scenario, as explained in the Step 2B analysis of claim 8, multi-core processors are considered well understood routine and conventional. Thus, these limitations do not amount to significantly more.
Claim 14 is directed to the mathematical concept of the optimization problem being an unconstrained binary optimization problem (mathematical calculations). Under Steps 2A prong 2 and 2B, the claim does not recite any additional elements that integrate the abstract idea into a practical application nor do they amount to significantly more than the judicial exception.
Regarding claim 20, limitations are similar to the claimed limitations of claim 13. Claim is rejected for the same reasons as claim 13.
Claim 1 is a method version of the method of claim 8 and is rejected for at least the same reasons therein. Herein, Claim 1 is directed towards the statutory category of a method, thus also satisfying Step 1. Under Steps 2A prong 2 and 2B, the claim does not recite any additional elements that integrate the abstract idea into a practical application nor do they amount to significantly more than the judicial exception.
Regarding Claims 2-7, they are method claims practiced by the apparatus of claims 9-14. They are rejected for the same reasons as claims 9-14.
Claim 15 is a media version of the method of claim 8 and is rejected for at least the same reasons therein. Herein, Claim 15 is directed towards the statutory category of machine or manufacture, thus also satisfying Step 1. Moreover, none of the additional elements regarding the generic computer components (i.e., one or more non-transitory computer-readable storage media, computer system) are more than high level generic computer components that amount to mere instructions to apply the abstract idea on a generic computer. See MPEP 2106.05(f).
Regarding Claims 16-19, they are media claims practiced by the apparatus of claims 9-12. They are rejected for the same reasons as claims 9-12.
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.
Apparatus claims 8-14 and 20 will be addressed before corresponding method claims 1-7, and corresponding media claims 15-19.
Claims 1, 2, 4-6, 8, 9, 11-13, 15, 16, and 18-20 are rejected under 35 U.S.C. 103 as being unpatentable over Satoshi Matsubara in NPL: “Ising-Model Optimizer with Parallel-Trial Bit-Sieve Engine” (https://link.springer.com/chapter/10.1007/978-3-319-61566-0_39), hereinafter “Matsubara”, in view of Kanda et al. (U.S. Patent Application Publication No.: US 20200326673 A1) (cited in IDS on 08/27/2024), hereinafter “Kanda”.
Regarding Claim 8, Matsubara teaches:
A system, comprising:
one or more processors, each of the processors including a plurality of computing cores (Fig. 1, e.g., shows Ising-model optimizing system including FPGAs (processors), each including Engine (computing cores));
a local memory (Fig. 1, e.g., shows DDR inside FPGA);
an off-chip memory (Fig. 1, e.g., shows server; Page 433, Section 2 Operating Principle, e.g., server provides weights and bias terms); and
… cause the system to perform operations, the operations comprising:
obtaining a plurality of variables that each represent a characteristic related to an optimization problem (Page 433, Section 2, e.g., weights correspond to the connection between bits in state variables);
obtaining weights that correspond to the variables, each respective weight relating to one or more relationships between a respective variable and one or more other variables related to the optimization problem (Abstract, e.g., hardware architecture solves combinatorial optimization problem; Page 433, Section 2, e.g., weights correspond to the connection between bits in state variables);
dividing the variables into a plurality of groups in which each respective group includes a sub-set of variables of the plurality of variables (Fig. 2, e.g., shows divided trails (plurality of groups); Page 434, Second paragraph, e.g., energy increment (in each trial) have corresponding bits);
obtaining a respective group local field matrix for each respective group of variables, each respective local field matrix including local field values that each indicate interactions between a respective variable and the other variables of the plurality of variables, as influenced by the respective weights of the respective variables (Page 433, Section 2, e.g., weights correspond to the connection between bits in state variables; Page 434, Section 3 Engine Implementation, e.g., local fields are updated when a variable x is flipped);
performing a semi-sequential trial process with respect to the plurality of groups (Page 435, e.g., multiple trial/update cycles are performed), the semi-sequential trial process including:
performing, based on first weights and first local field values that correspond to a first group of first variables of the plurality of groups, a first stochastic process with respect to the first group (Page 433, Section 2 Operating principle, e.g., Stochastic search is based on values of weights; Page 433 Last paragraph - Page 434 First paragraph, e.g., search in engine is done stochastically based on the increment in energy calculated from local field hi),
the first stochastic process being with respect to changing a respective state of one or more of the first variables of the first group (Page 433 Last paragraph - Page 434 First paragraph, e.g., search is done stochastically and moves state to a neighboring state, which is generated by flipping value of xi),
the first stochastic process including performing first trials with respect to one or more of the first variables in which a respective first trial determines whether to change a respective state of a respective first variable (Page 433 Last paragraph - Page 434 First paragraph, e.g., search is done stochastically and moves state to a neighboring state, which is generated by flipping value of xi);
updating all of the group local field matrices based on results of the first stochastic process (Page 434, Section 3 Engine Implementation, e.g., local fields are updated when a variable x is flipped);
performing, based on second weights and second local field values that correspond to a second group of second variables of the plurality of groups, a second stochastic process with respect to the second group (Page 433, Section 2 Operating principle, e.g., Stochastic search is based on values of weights; Page 433 Last paragraph - Page 434 First paragraph, e.g., search in engine is done stochastically based on the increment in energy calculated from local field hi; Page 435, e.g., multiple trial/update cycles are performed, hence a second stochastic process is performed),
the second stochastic process being with respect to changing a respective state of one or more of the second variables of the second group (Page 433 Last paragraph - Page 434 First paragraph, e.g., search is done stochastically and moves state to a neighboring state, which is generated by flipping value of xi),
the second stochastic process including performing second trials with respect to one or more of the second variables in which a respective second trial determines whether to change a respective state of a respective second variable (Page 433 Last paragraph - Page 434 First paragraph, e.g., search is done stochastically and moves state to a neighboring state, which is generated by flipping value of xi); and
updating all of the group local field matrices based on results of the second stochastic process (Page 434, Section 3 Engine Implementation, e.g., local fields are updated when a variable x is flipped); and
determining a solution to the optimization problem based on the semi-sequential trial process (Page 434, Second paragraph, e.g., faster convergence to an optimum solution is achieved).
Matsubara does not teach:
one or more non-transitory computer-readable storage media configured to store instructions that, in response to being executed by the local memory
However, Kanda teaches:
one or more non-transitory computer-readable storage media configured to store instructions that, in response to being executed by the [processor] (¶0116, e.g., processor performs processing by executing a program (instructions) stored in a memory)
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine the memory to store a program to be executed by a processor as taught by Kanda with the FPGA (including DDR) as taught by Matsubara. One would have been motivated to combine these references because both references disclose solving optimization problems in hardware, and Kanda enhances the model of Matsubara by allowing for program instructions to be stored in memory for execution on hardware.
Regarding Claim 9, Matsubara in view of Kanda teach:
The system of claim 8, wherein obtaining the weights that correspond to the variables includes referencing a weight matrix that includes a weight of each variable with respect to each other variable included in the optimization problem (Matsubara: Page 433, equation 1, e.g., Weight elements from weight matrix are used for each bit).
Regarding Claim 11, Matsubara in view of Kanda teach:
The system of claim 9, wherein the variables are stored on a first memory and referencing the weight matrix includes accessing a second memory on which the weight matrix is stored, the second memory being separate from the first memory (Kanda: Fig. 1, e.g., shows storage units 11 and 12 for storing weight and bit values).
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine the first and second memories to store weight and bit values as taught by Kanda with the server providing weight and bias values as taught by Matsubara. One would have been motivated to combine these references because both references disclose solving optimization problems in hardware, and Kanda enhances the model of Matsubara because “the memory access time can be shortened and a decrease in throughput can be suppressed.” (Kanda: ¶0106)
Regarding Claim 12, Matsubara in view of Kanda teach:
The system of claim 8, wherein a number of the first trials being performed for the first stochastic process is determined based on a respective temperature associated with each respective first variable, wherein: the temperature begins at a first temperature (Matsubara: Page 435, First paragraph, e.g., temperature is used in the trial phase); and
the temperature updates to a second temperature after updating all of the group local field matrices based on the results of the first stochastic process, the second temperature being lower than the first temperature (Matsubara: Page 435, e.g., multiple trial/update cycles are performed, hence local fields are updated every cycle; Kanda: ¶0190, e.g., temperature is updated and is lowered from previous temperature).
It would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine the updating of temperature as taught by Kanda with the update phase as taught by Matsubara. One would have been motivated to combine these references because both references disclose solving optimization problems in hardware, and Kanda enhances the model of Matsubara because " when the temperature is gradually lowered from a high temperature, an occupation probability of a low energy state increases, so that the low energy state is desirably obtained when the temperature is sufficiently lowered.” (Kanda: ¶0190)
Regarding Claim 13, Matsubara in view of Kanda teach:
The system of claim 8, wherein dividing the variables into the plurality of groups is based on a number of computing cores of a computer system configured to perform the semi- sequential trial process and a processing capability of each of the computing cores (Page 433, Section 2 Operating Principle, First paragraph, e.g., proposed hardware consists of multiple engines (computing cores) to perform a MCMC stochastic search to minimize the Ising energy).
Regarding Claim 20, Matsubara in view of Kanda teach:
The one or more non-transitory computer-readable storage media of claim 8, wherein dividing the variables into the plurality of groups is based on a number of computing cores of the computer system configured to perform the semi-sequential trial process and a processing capability of each of the computing cores (Page 433, Section 2 Operating Principle, First paragraph, e.g., proposed hardware consists of multiple engines (computing cores) to perform a MCMC stochastic search to minimize the Ising energy).
Regarding Claims 1, 2, and 4-6, they are method claims practiced by the apparatus of claims 8, 9, and 11-13. They are rejected for the same reasons as claims 8, 9, and 11-13.
Regarding Claims 15, 16, 18, and 19, they are media claims practiced by the apparatus of claims 8, 9, 11, and 12. They are rejected for the same reasons as claims 8, 9, 11, and 12.
Claims 3, 10, and 17 are rejected under 35 U.S.C. 103 as being unpatentable over Matsubara in view of Kanda, further in view of J.-L. Bouquard in NPL: “Application of an optimization problem in Max-Plus algebra to scheduling problems” (https://www.sciencedirect.com/science/article/pii/S0166218X06000485?ref=pdf_download&fr=RR-2&rr=9ecba09a1e8cf094), hereinafter “Bouquard”.
Regarding Claim 10, Matsubara in view of Kanda teach:
The system of claim 9, wherein the weight matrix … includes the weight of each respective variable with respect to each other variable included in the optimization problem (Abstract, e.g., hardware architecture solves combinatorial optimization problem; Page 433, Section 2, e.g., weights correspond to the connection between bits in state variables) …
Matsubara in view of Kanda do not teach:
… wherein the weight matrix is a half-weight matrix … but not a bidirectional weight between each other variable and the each respective variable.
However, Bouquard teaches using triangular matrices for solving optimization problems. Bouquard explains in Page 2065, First paragraph “In Section 3 we present a general optimization problem in Max-Plus algebra, that involves 2 × 2 matrices”, and in Section 3 Optimization problem in T2×2(Rmax) “Let us consider a set of n 2 × 2 triangular matrices in Max-Plus algebra”. As shown in Section 3, triangular matrix M(i) contains upper elements of the matrix, hence elements are not bidirectional.
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine using triangular matrices for solving optimization problems as taught by Bouquard with the weight data used for solving the optimization problem as taught by Matsubara in view of Kanda. One would have been motivated to combine these references because both references disclose solving optimization problems, and Bouquard enhances the model of Matsubara in view of Kanda because “Max-Plus algebra is more adapted for solving sequencing problems than the classical (R,+,×) algebra.” (Bouquard: First page, Introduction)
Regarding Claim 3, it is a method claim practiced by the apparatus of claim 10. It is rejected for the same reasons as claim 10.
Regarding Claim 17, it is a media claim practiced by the apparatus of claim 10. It is rejected for the same reasons as claim 10.
Claims 7 and 14 are rejected under 35 U.S.C. 103 as being unpatentable over Matsubara in view of Kanda, further in view of Oshima (U.S. Patent Application No.: US 20210065087 A1), hereinafter “Oshima”
Regarding Claim 14, Matsubara in view of Kanda teach the system of claim 8. Matsubara in view of Kanda do not teach:
wherein the optimization problem is a quadratic unconstrained binary optimization (QUBO) problem.
However, Oshima teaches:
wherein the optimization problem is a quadratic unconstrained binary optimization (QUBO) problem (¶0044, e.g., energy function of the optimization problem is formulated to QUBO).
Therefore, it would have been obvious before the effective filing date of the claimed invention to one of ordinary skill in the art to which said subject matter pertains to combine formulating the optimization problem into QUBO as taught by Oshima with the optimization problem as taught by Matsubara in view of Kanda. One would have been motivated to combine these references because both references disclose solving optimization problems, and Oshima enhances the model of Matsubara in view of Kanda because formulating optimization problems to QUBO maps complex combinatorial problems into a simple representation.
Regarding Claim 7, it is a method claim practiced by the apparatus of claim 10. It is rejected for the same reasons as claim 14.
Prior Art Made of Record
NPL: “Replica exchange MCMC engine for combinatorial optimization problems” – teaches a Boltzmann machine as a parallel hardware architecture developed to solve combinatorial optimization problems. See Section 2.6 “1024 Fully-Connected Boltzmann Machine with Parallel Trial” and Figure 2.5.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to CARLOS H DE LA GARZA whose telephone number is (571)272-0474. The examiner can normally be reached Monday-Friday 9:30AM-6PM.
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.
/C.H.D./
Carlos H. De La GarzaExaminer, Art Unit 2182 (571)272-0474
/ANDREW CALDWELL/Supervisory Patent Examiner, Art Unit 2182
Prosecution Insights