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 .
Response to Argument
Applicant's arguments filed 03/28/2026 ("Arguments/Remarks") have been fully considered but they are not persuasive.
Argument – 1: (page: 6) Applicant contends: “With respect to Step 2A, Prong 1 applied to claim 1, Applicant submits that claim 1 recites training a neural network, wherein the neural network generates coordinates for the macro placement. Neural network training requires iterative numerical optimization executed by a computer. Therefore, "training a neural network" cannot be a "mental process" under MPEP 2106.04.”
Regarding the above argument, the Examiner respectfully notes that, "training a neural network" is categorized as “apply it”, (or an equivalent), such as mere instructions to implement an abstract idea on a computer under Step 2A, Prong 2 not as an abstract idea under Step 2A, Prong 1.
Argument – 2: (page: 6) Applicant contends: “Furthermore, with respect to Step 2A, Prong 2, the specific neural network training method, as recited in amended claim 1, is directed to a specific technological application (e.g., generating coordinates for macro placement on the canvas of a semiconductor integrated circuit block). Thus, the claimed neural network training integrates any alleged judicial exception into a practical application and contributes to an improvement in the technical field of electronic design automation (EDA). As such, Applicant submits that amended claim 1 is patent eligible under 35 U.S.C. 101.”
Regarding the above argument, the Examiner respectfully disagrees with Applicant’s assertion that the amended claim integrates the judicial exception into a practical application and contributes to an improvement in the technical field of electronic design automation (EDA). The additional recitation of training a neural network, adding the chip is an integrated circuit (IC) and the Macros contain IC components do not integrate the judicial exception into a practical application because it merely applied computer as a tool to perform the recited data processing and sample construction operations. The amendment lacks sufficient technical details to support a conclusion that the recited operations improve computer functionality, placement operation or another technical aspect of integrated circuit design, but instead recites an abstract idea implemented on generic computer component.
Applicant’s arguments with respect to amended claim(s) have been considered but are moot, because arguments/remarks are directed to amended claim limitations that were not previously examined by the examiner. The rejections are noted in the current office action to address amended claim limitations.
As to the remaining dependent claims, applicant argue that they are allowable due to their respective direct and indirect dependencies upon one of the aforementioned Independent claims. The examiner respectfully disagrees, Independent claims were not allowable as stated in the paragraph above in this “Response to Arguments” section in this office action.
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.
Claim(s) 1 – 20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e. an abstract idea) without significantly more.
In step 1, of the 101-analysis set forth in the MPEP 2106, the examiner has determined
that the following limitations recite a process that, under the broadest reasonable interpretation, falls within one or more statutory categories (processes).
In step 2A prong 1, of the 101-analysis set forth in MPEP 2106, the examiner has determined
that the following limitations recite a process that, under broadest reasonable interpretation, covers
a mental process but for the recitation of generic computer components:
Regarding claim 1,
constructing a set of positive samples of trajectories by sequentially removing a same set of macros in different orders from an at least partially-placed canvas of a chip
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves identifying different order of removing macros from a placement and evaluating the resulting trajectories to form a set of “positive” samples. See (MPEP 2106.04)).
constructing a set of negative samples of trajectories by placing not-yet-placed macros at random positions on an at least partially-empty canvas of the chip
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves selecting arbitrary placements of macros on a canvas and treating the resulting arrangements as a “negative” sample. See (MPEP 2106.04)).
If the claim limitations, under their broadest reasonable interpretation, covers performance of the limitations as a mental process, but for the recitation of generic computer components, then it falls within the mental process. Accordingly, the claim recites an abstract idea.
Step 2A Prong 2 of the 101-analysis, set forth in MPEP 2106, the examiner has determined that
the following additional elements do not integrate this judicial exception into a practical application:
wherein the chip is a semiconductor integrated circuit block and each macro contains integrated circuit components;
(i.e.: deemed insufficient to transform the judicial exception to a patentable invention because the claim recites limitation simply links the judicial exception to a field of use and/or technology environment, see MPEP 2106.05(h)).
training the NN and a graph NN (GNN) in the NN using the positive samples and the negative samples.
(i.e.: deemed insufficient to transform the judicial exception to a patentable invention because the claim recites limitation which does not amount to more than a recitation of the words "apply it" (or an equivalent), such as mere instructions to implement an abstract idea on a computer. See MPEP 2106.05(f)).
wherein the NN generates coordinates for the macro placement.
(i.e.: deemed insufficient to transform the judicial exception to a patentable invention because the claim recites limitation simply links the judicial exception to a field of use and/or technology environment, see MPEP 2106.05(h)).
In Step 2B of the 101-analysis set forth in the 2019 PEG, the examiner has determined that the
claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception:
Regarding limitation (I), recites mere application of the abstract idea or mere instructions to implement an abstract idea on a computer are deemed insufficient to transform the judicial exception to a patentable invention because the limitations generally apply the use of a generic computer and/or process with the judicial exception, see MPEP 2106.05(f).
As analyzed above, the additional elements, analyzed above, do not integrate the noted judicial exception into a practical application because they do not impose any meaningful limits on practicing the abstract idea. Therefore, the claim is directed to an abstract idea.
Regarding claim 2, dependent upon claim 1, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein each positive sample is a trajectory of (state, action) pairs, the state is a canvas state after a macro is removed and the action is a coordinate of the macro.
The recitation in the additional limitation simply links the judicial exception to a field of use and/or technology environment, see MPEP 2106.05(h).
Limitations directed to field of use cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Regarding claim 3, dependent upon claim 1, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein at least one of the positive samples is constructed by sequentially removing all macros from the chip in a random order
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves determining an order in which items (macros) are removed and treating the resulting sequence as a “positive” sample. See (MPEP 2106.04)).
Regarding claim 4, dependent upon claim 1, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein at least one of the positive samples is constructed by sequentially removing a first subset of the macros in the same set from the chip in a predetermined order and a second subset of the macros in the same set from the chip in a random order.
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves deciding how to partition items into subsets and determining an order (predetermined or random) in which those items are removed. See (MPEP 2106.04)).
Regarding claim 5, dependent upon claim 1, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein each negative sample is a trajectory of (state, action) pairs, the state is a canvas state before a macro is placed and the action is a coordinate of the macro.
The recitation in the additional limitation simply links the judicial exception to a field of use and/or technology environment, see MPEP 2106.05(h).
Limitations directed to field of use cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Regarding claim 6, dependent upon claim 1, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein at least one of the negative samples is constructed by sequentially placing all macros at random positions on an empty canvas of the chip.
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves deciding, in a random order, where items are placed within a canvas to create negative samples. See (MPEP 2106.04)).
Regarding claim 7, dependent upon claim 1, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein at least one of the negative samples is constructed by sequentially placing a first subset of the macros in the same set on the chip at predetermined positions and a second subset of the macros in the same set on the chip at random positions.
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves deciding how to place items by following predefined rules for one subset and making random placement choice for another subset. See (MPEP 2106.04)).
Regarding claim 8, dependent upon claim 1, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein at least one of the negative samples is constructed by placing the not-yet-placed macros in a random placement order.
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves selecting an order in which items are placed based on randomness. See (MPEP 2106.04)).
Regarding claim 9, dependent upon claim 1, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein the GNN is trained based on a contrastive loss function that measures distances between a pair of positive samples and between a pair of negative samples.
Deemed insufficient to transform the judicial exception to a patentable invention because the limitation is directed to mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and are considered to adding the words “apply it” (or an equivalent) with the judicial exception, See MPEP 2106.05(f).
Limitations directed to using the computer as a tool for implementing an abstract idea cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Regarding claim 10, dependent upon claim 1, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein the GNN is trained based on a contrastive loss function that measures similarity between a true sample and a positive sample and between the true sample and one or more negative samples, and wherein the true sample is an original trajectory of the completed macro placement.
Deemed insufficient to transform the judicial exception to a patentable invention because the limitation is directed to mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and are considered to adding the words “apply it” (or an equivalent) with the judicial exception, See MPEP 2106.05(f).
Limitations directed to using the computer as a tool for implementing an abstract idea cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Regarding claim 11, dependent upon claim 1, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein training the NN comprises: pre-training the NN using the positive samples and the negative samples; and fine-tuning the NN using the positive samples, the negative samples, and trajectories generated from the pre-trained NN.
Deemed insufficient to transform the judicial exception to a patentable invention because the limitation is directed to mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and are considered to adding the words “apply it” (or an equivalent) with the judicial exception, See MPEP 2106.05(f).
Limitations directed to using the computer as a tool for implementing an abstract idea cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Regarding claim 12, dependent upon claim 11, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein pre-training the NN further comprises: updating parameters of the GNN based on a contrastive loss function calculated from the positive samples and the negative samples; and updating parameters of the NN including the GNN based on a loss function different from the contrastive loss function.
Deemed insufficient to transform the judicial exception to a patentable invention because the limitation is directed to mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and are considered to adding the words “apply it” (or an equivalent) with the judicial exception, See MPEP 2106.05(f).
Limitations directed to using the computer as a tool for implementing an abstract idea cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Regarding claim 13, dependent upon claim 11, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein fine-tuning the NN further comprises: updating parameters of the GNN based on a contrastive loss function calculated from the positive samples and the negative samples; and updating parameters of the NN excluding the GNN based on a loss function different from the contrastive loss function.
Deemed insufficient to transform the judicial exception to a patentable invention because the limitation is directed to mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and are considered to adding the words “apply it” (or an equivalent) with the judicial exception, See MPEP 2106.05(f).
Limitations directed to using the computer as a tool for implementing an abstract idea cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Regarding claim 14, dependent upon claim 11, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein fine-tuning the NN further comprises: updating parameters of the NN excluding the GNN based on gradient descent with a first learning rate; and updating parameters of the GNN based on the gradient descent with a second learning rate different from the first learning rate.
Deemed insufficient to transform the judicial exception to a patentable invention because the limitation is directed to mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and are considered to adding the words “apply it” (or an equivalent) with the judicial exception, See MPEP 2106.05(f).
Limitations directed to using the computer as a tool for implementing an abstract idea cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Regarding claim 15, dependent upon claim 11, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
generating, [ ], a first set of trajectories for updating NN parameters
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves determining sequences of actions (trajectories) to adjust model parameters. See (MPEP 2106.04)).
by the NN,
Deemed insufficient to transform the judicial exception to a patentable invention because the limitation is directed to mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and are considered to adding the words “apply it” (or an equivalent) with the judicial exception, See MPEP 2106.05(f).
Limitations directed to using the computer as a tool for implementing an abstract idea cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
wherein each trajectory in the first set includes an action that is sampled stochastically according to a probability distribution, the action indicating a coordinate on a chip canvas to place a macro;
The recitation in the additional limitation simply links the judicial exception to a field of use and/or technology environment, see MPEP 2106.05(h).
Limitations directed to field of use cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
generating, [ ], a second set of trajectories for evaluating the updated NN parameters,
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves determining sequences of actions (trajectories) for evaluating updated neural network. See (MPEP 2106.04)).
by the NN
Deemed insufficient to transform the judicial exception to a patentable invention because the limitation is directed to mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and are considered to adding the words “apply it” (or an equivalent) with the judicial exception, See MPEP 2106.05(f).
Limitations directed to using the computer as a tool for implementing an abstract idea cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
wherein each trajectory in the second set includes another action that is chosen according to another probability distribution as having a highest probability.
The recitation in the additional limitation simply links the judicial exception to a field of use and/or technology environment, see MPEP 2106.05(h).
Limitations directed to field of use cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Regarding claim 16,
The rest of the limitations are analogous to claim 1, so are rejected under similar rationale.
A system operative to train a neural network (NN) for macro placement comprising: processing hardware; and memory coupled to the processing hardware to store information on the NN, a set of chips, and macros placed on the chips
Deemed insufficient to transform the judicial exception to a patentable invention because the limitation is directed to mere instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea and are considered to adding the words “apply it” (or an equivalent) with the judicial exception, See MPEP 2106.05(f).
Limitations directed to using the computer as a tool for implementing an abstract idea cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Regarding claim 17, dependent upon claim 16, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein the processing hardware is further operative to remove all or a subset of the macros from the chip in a random sequential order when constructing at least one of the positive samples.
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves selecting items to remove and determine a random sequence for removal to construct positive sample. See (MPEP 2106.04)).
Regarding claim 18, dependent upon claim 16, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein the processing hardware is further operative to sequentially place all or a subset of the macros at random positions on the chip when constructing at least one of the negative samples.
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves selecting items to place on a canvas and determine a random sequence for placing to construct negative sample. See (MPEP 2106.04)).
Regarding claim 19, dependent upon claim 16, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein the processing hardware is further operative to sequentially place all or a subset of the macros in a random placement order on the chip when constructing at least one of the negative samples.
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves selecting items to place on a canvas and determine a random sequence for placing to construct negative sample. See (MPEP 2106.04)).
Regarding claim 20, dependent upon claim 16, and fail to resolve the deficiencies identified above by integrating the judicial exception into a practical application, or introducing significantly more than the judicial exception. The claim recites:
wherein the processing hardware is further operative to update parameters of the GNN based on a contrastive loss function calculated from the positive samples and the negative samples.
(i.e.: the broadest reasonable interpretation, the claim recites abstract idea: mental process: It involves evaluating differences between “positive” and “negative” samples, calculating a measure of discrepancy, and adjusting parameter values accordingly. See (MPEP 2106.04)).
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.
Claim(s) 1 – 5 and 16 – 17 are rejected under 35 U.S.C. 103 as being unpatentable over Mirhoseini et al., "Chip placement with deep reinforcement learning" in view of Dudha et al., Pub. No.: US10289786B1 and Sha et al., Pub. No.: US20190370434A1.
Regarding claim 1, Mirhoseini teaches: A method for training a neural network (NN) for macro placement, comprising:
(Mirhoseini, page: 1, “In this work, we present a learning-based approach to chip placement, one of the most complex and time-consuming stages of the chip design process [A method for training a neural network (NN) for macro placement]. The objective is to place a netlist graph of macros (e.g., SRAMs) and standard cells (logic gates, such as NAND, NOR, and XOR) onto a chip canvas, such that power, performance, and area (PPA) are optimized, while adhering to constraints on placement density and routing congestion (described in Sections 3.3.6 and 3.3.5).”)
constructing a set of negative samples of trajectories by placing not-yet-placed macros at random positions on an at least partially-empty canvas of the chip; and
(Mirhoseini, page: 2, “Simulated annealing (SA) is named for its analogy to metallurgy, in which metals are first heated and then gradually cooled to induce, or anneal, energy optimal crystalline surfaces. SA applies random perturbations to a given placement (e.g., shifts, swaps, or rotations of macros) [constructing a set of negative samples of trajectories by placing not-yet-placed macros at random positions on an at least partially-empty canvas of the chip], and then measures their effect on the objective function (e.g., half-perimeter wirelength described in Section 3.3.1)”)
training the NN and a graph NN (GNN) in the NN using the positive samples and the negative samples.
(Mirhoseini, page: 3, “To address this classic problem, we propose a new category of approach: end-to-end learning-based methods [training the NN and a graph NN (GNN) in the NN]. This type of approach is most closely related to analytic solvers, particularly non-linear ones, in that all of these methods optimize an objective function via gradient updates. However, our approach differs from prior approaches in its ability to learn from past experience to generate higher-quality placements on new chips. Unlike existing methods that optimize the placement for each new chip from scratch, our work leverages knowledge gained from placing prior chips to become better over time [using the positive samples and the negative samples]. In addition, our method enables direct optimization of the target metrics, such as wirelength, density, and congestion, without having to define convex approximations of those functions as is done in other approaches (Cheng et al., 2019; Lu et al., 2015).”)
Mirhoseini does not teach:
constructing a set of positive samples of trajectories by sequentially removing a same set of macros in different orders from an at least partially-placed canvas of a chip, wherein the chip is a semiconductor integrated circuit block and each macro contains integrated circuit components;
wherein the NN generates coordinates for the macro placement.
Dudha teaches:
constructing a set of positive samples of trajectories by sequentially removing a same set of macros in different orders from an at least partially-placed canvas of a chip, wherein the chip is a semiconductor integrated circuit block and each macro contains integrated circuit components;
(Dudha, (col. 8 line [49 – 60]), “ In the example of FIG. 7, each of combinatorial circuitries 605, 705, and 710 has a number of logic levels that is less than or equal to the TMLL of 4 for the target technology process and the target operating frequency of the target IC [wherein the chip is a semiconductor integrated circuit block and each macro contains integrated circuit components]. The retiming operations illustrated in FIGS. 5 and 6 have allowed the system to remove further sequential circuit elements from the set of sequential circuit elements [constructing a set of positive samples of trajectories by sequentially removing a same set of macros in different orders from an at least partially-placed canvas of a chip] thereby further reducing latency, power consumption, and/or area usage for circuit design 200. In the example of FIG. 7, the system may discontinue processing since the set of sequential circuit elements to be processed does not include any further sequential circuit elements.”)
Dudha and Mirhoseini are related to the same field of endeavor (i.e.: neural network training). It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to combine the teaching of Dudha with teachings of Mirhoseini to modify an existing circuit design by identifying and removing specific sequential circuit elements to reduce latency, (Dudha, Abstract).
Mirhoseini in view of Dudha do not teach:
wherein the NN generates coordinates for the macro placement.
Sha teaches:
wherein the NN generates coordinates for the macro placement.
(Sha, “[0025] In an embodiment, one RNN is trained to predict sequences of via coordinates. The trained RNN is then used to generate new data (coordinate arrays) [wherein the NN generates coordinates for the macro placement] (i.e.: the training dataset of coordinate arrays contains coordinates via from existing layouts, after training, the RNN generates new placement coordinates). Hence, it is to be appreciated that the coordinate arrays involved in training the RNN are different than the coordinate arrays generated by the RNN.”)
Sha, Mirhoseini and Dudha are related to the same field of endeavor (i.e.: neural network training). It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to combine the teaching of Sha with teachings of Mirhoseini and Dudha to add the use of a neural network trained using coordinate based layout data to learn spatial design patterns from existing integrated circuit layouts to enhance automatically generate or refine layout patterns based on learned coordinates relationship, (Sha, Abstract).
Regarding claim 2, Mirhoseini in view of Dudha and Sha teach the method of claim 1.
Mirhoseini further teaches: wherein each positive sample is a trajectory of (state, action) pairs,
(Mirhoseini, page: 3 – 4, “reward: the reward for taking an action in a state [wherein each positive sample is a trajectory of (state, action) pairs]. (e.g., in our case, the reward is 0 for all actions except the last action where the reward is a negative weighted sum of proxy wirelength and congestion, subject to density constraints as described in Section 3.3).”)
the state is a canvas state after a macro is removed and
(Mirhoseini, page: 4, “In our setting, at the initial state, s0, we have an empty chip canvas and an unplaced netlist [the state is a canvas state after a macro is removed]. The final state sT corresponds to a completely placed netlist. At each step, one macro is placed. Thus, T is equal to the total number of macros in the netlist. At each time step t, the agent begins in state (st), takes an action (at), arrives at a new state (st+1), and receives a reward (rt) from the environment (0 for t < T and negative proxy cost for t = T).”)
the action is a coordinate of the macro.
(Mirhoseini, page: 3, “actions: the set of actions that can be taken by the agent (e.g., given the current macro to place, the available actions are the set of all the locations in the discrete canvas space (grid cells) [the action is a coordinate of the macro] onto which that macro can be placed without violating any hard constraints on density or blockages).”)
Regarding claim 3, Mirhoseini in view of Dudha and Sha teach the method of claim 1.
Dudha further teaches: wherein at least one of the positive samples is constructed by sequentially removing all macros from the chip
(Dudha, (col. 8 line [49 – 60]), “ In the example of FIG. 7, each of combinatorial circuitries 605, 705, and 710 has a number of logic levels that is less than or equal to the TMLL of 4 for the target technology process and the target operating frequency of the target IC. The retiming operations illustrated in FIGS. 5 and 6 have allowed the system to remove further sequential circuit elements from the set of sequential circuit elements [wherein at least one of the positive samples is constructed by sequentially removing all macros from the chip] thereby further reducing latency, power consumption, and/or area usage for circuit design 200. In the example of FIG. 7, the system may discontinue processing since the set of sequential circuit elements to be processed does not include any further sequential circuit elements.”)
Mirhoseini further teaches: in a random order.
(Mirhoseini, page: 2, “Simulated annealing (SA) is named for its analogy to metallurgy, in which metals are first heated and then gradually cooled to induce, or anneal, energy optimal crystalline surfaces. SA applies random perturbations to a given placement (e.g., shifts, swaps, or rotations of macros) [in a random order], and then measures their effect on the objective function (e.g., half-perimeter wirelength described in Section 3.3.1)”)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Dudha with teachings of Mirhoseini and Sha for the same reasons disclosed for claim 1.
Regarding claim 4, Mirhoseini in view of Dudha and Sha teach the method of claim 1.
Dudha further teaches: wherein at least one of the positive samples is constructed by sequentially removing a first subset of the macros in the same set from the chip in a predetermined order and
(Dudha, (col. 1 line [41 – 48])), “FIG. 4 illustrates another example state of circuit design 200 subsequent to removing further sequential circuit elements. In the example of FIG. 4, the system has made another cut and removed sequential circuit elements 215 and 235 from circuit design 200 [wherein at least one of the positive samples is constructed by sequentially removing a first subset of the macros in the same set from the chip in a predetermined order]. Sequential circuit elements 205, 210, 230, and 225 remain in circuit design 200. Further, combinatorial circuitry 245 remains unchanged in circuit design 200.”)
Mirhoseini further teaches: a second subset of the macros in the same set from the chip in a random order.
(Mirhoseini, page: 2, “Simulated annealing (SA) is named for its analogy to metallurgy, in which metals are first heated and then gradually cooled to induce, or anneal, energy optimal crystalline surfaces. SA applies random perturbations to a given placement (e.g., shifts, swaps, or rotations of macros) [a second subset of the macros in the same set from the chip in a random order], and then measures their effect on the objective function (e.g., half-perimeter wirelength described in Section 3.3.1)”)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Dudha with teachings of Mirhoseini and Sha for the same reasons disclosed for claim 1.
Regarding claim 5, Mirhoseini in view of Dudha and Sha teach the method of claim 1.
Mirhoseini further teaches: wherein each negative sample is a trajectory of (state, action) pairs, the state is a canvas state before a macro is placed and the action is a coordinate of the macro.
(Mirhoseini, page: 6, “3.5. State Representation Our state contains information about the netlist graph (adjacency matrix) [the state is a canvas state], its node features (width, height, type, etc.), edge features (number of connections), current node (macro) to be placed [before a macro is placed and the action is a coordinate of the macro], and metadata of the netlist and the underlying technology (e.g., routing allocations, total number of wires, macros, and standard cell clusters, etc.).”)
Regarding claim 16,
The rest of the limitations are analogous to claim 1, so are rejected under similar rationale.
Mirhoseini teaches: A system operative to train a neural network (NN) for macro placement comprising:
a set of chips, and macros placed on the chips, wherein the processing hardware is operative to
(Mirhoseini, page: 1, “In this work, we present a learning-based approach to chip placement [A system operative to train a neural network (NN) for macro placement comprising], one of the most complex and time-consuming stages of the chip design process [a set of chips, and macros placed on the chips, wherein the processing hardware is operative to]. The objective is to place a netlist graph of macros (e.g., SRAMs) and standard cells (logic gates, such as NAND, NOR, and XOR) onto a chip canvas, such that power, performance, and area (PPA) are optimized, while adhering to constraints on placement density and routing congestion (described in Sections 3.3.6 and 3.3.5).”)
Dudha teaches: processing hardware; and memory coupled to the processing hardware to store information on the NN,
(Dudha, (col. 3 line [42 – 49]), “System 100 includes at least one processor 105. Processor 105 is coupled to memory 110 through interface circuitry 115. System 100 stores computer readable instructions (also referred to as “program code”) within memory 110. Memory 110 is an example of computer readable storage media. Processor 105 executes the program code accessed from memory 110 via interface circuitry 115 [processing hardware; and memory coupled to the processing hardware to store information on the NN].”)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Dudha with teachings of Mirhoseini and Sha for the same reasons disclosed for claim 1.
Regarding claim 17, Mirhoseini in view of Dudha and Sha teach the method of claim 16.
Dudha further teaches: wherein the processing hardware is further operative to remove all or a subset of the macros from the chip [ ] when constructing at least one of the positive samples.
(Dudha, (col. 8 line [49 – 60]), “ In the example of FIG. 7, each of combinatorial circuitries 605, 705, and 710 has a number of logic levels that is less than or equal to the TMLL of 4 for the target technology process and the target operating frequency of the target IC. The retiming operations illustrated in FIGS. 5 and 6 have allowed the system to remove further sequential circuit elements from the set of sequential circuit elements [wherein the processing hardware is further operative to remove all or a subset of the macros from the chip [ ] when constructing at least one of the positive samples] thereby further reducing latency, power consumption, and/or area usage for circuit design 200. In the example of FIG. 7, the system may discontinue processing since the set of sequential circuit elements to be processed does not include any further sequential circuit elements.”)
Mirhoseini further teaches: in a random sequential order.
(Mirhoseini, page: 2, “Simulated annealing (SA) is named for its analogy to metallurgy, in which metals are first heated and then gradually cooled to induce, or anneal, energy optimal crystalline surfaces. SA applies random perturbations to a given placement (e.g., shifts, swaps, or rotations of macros) [in a random sequential order], and then measures their effect on the objective function (e.g., half-perimeter wirelength described in Section 3.3.1)”)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Dudha with teachings of Mirhoseini and Sha for the same reasons disclosed for claim 1.
Claim(s) 6 – 8 and 18 – 19 are rejected under 35 U.S.C. 103 as being unpatentable over Mirhoseini in view of Dudha, Sha and in further view of Meyyappan et al., Pub. No.: US20070220470A1.
Regarding claim 6, Mirhoseini in view of Dudha and Sha teach the method of claim 1.
Mirhoseini in view of Dudha and Sha do not teach:
wherein at least one of the negative samples is constructed by sequentially placing all macros at random positions on an empty canvas of the chip
Meyyappan teaches:
wherein at least one of the negative samples is constructed by sequentially placing all macros at random positions on an empty canvas of the chip.
(Meyyappan, “[0044] In step 305, a first set of placements is generated. Any approach, manual or automatic or a combination, can be used to generate such placements. However, in an embodiment, the location of each macro in each placement is determined randomly [wherein at least one of the negative samples is constructed by sequentially placing all macros at random positions on an empty canvas of the chip], using a pseudo-random number generator. For illustration, it is assumed that the placements are represented by g1 through g1m (of FIG. 3C). Control then passes to step 310.”)
Meyyappan, Mirhoseini, Dudha and Sha are related to the same field of endeavor (i.e.: neural network training). It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to combine the teaching of Meyyappan with teachings of Mirhoseini, Dudha and Sha to add propagating desirable placement properties across iterations and automatic removal of overlaps to improve placement quality, (Meyyappan, Abstract).
Regarding claim 7, Mirhoseini in view of Dudha and Sha teach the method of claim 1.
Mirhoseini in view of Dudha and Sha do not teach:
wherein at least one of the negative samples is constructed by sequentially placing a first subset of the macros in the same set on the chip at predetermined positions and a second subset of the macros in the same set on the chip at random positions.
Meyyappan teaches:
wherein at least one of the negative samples is constructed by sequentially placing a first subset of the macros in the same set on the chip at predetermined positions and
(Meyyappan, “[0060] In step 350, new placements are created from each group created in step 340 [sequentially placing a first subset of the macros in the same set on the chip]. The position of a macro in a new placement is chosen to be at least substantially identical to one of the positions [at predetermined positions] of the same macro in the placements in the corresponding group. The specific present placement in the subset which controls the position of a macro in the new placement is chosen randomly. An example approach to implement this step is illustrated below with respect to FIGS. 4A-4C.”)
a second subset of the macros in the same set on the chip at random positions.
(Meyyappan, “[0044] In step 305, a first set of placements is generated [a second subset of the macros in the same set on the chip]. Any approach, manual or automatic or a combination, can be used to generate such placements. However, in an embodiment, the location of each macro in each placement is determined randomly [at random positions], using a pseudo-random number generator. For illustration, it is assumed that the placements are represented by g1 through g1m (of FIG. 3C). Control then passes to step 310.”)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Meyyappan with teachings of Mirhoseini, Dudha and Sha for the same reasons disclosed for claim 6.
Regarding claim 8, Mirhoseini in view of Dudha and Sha teach the method of claim 1.
Mirhoseini in view of Dudha and Sha do not teach:
wherein at least one of the negative samples is constructed by placing the not-yet-placed macros in a random placement order.
Meyyappan teaches:
wherein at least one of the negative samples is constructed by placing the not-yet-placed macros in a random placement order.
(Meyyappan, “[0044] In step 305, a first set of placements is generated [wherein at least one of the negative samples is constructed]. Any approach, manual or automatic or a combination, can be used to generate such placements. However, in an embodiment, the location of each macro in each placement is determined randomly [by placing the not-yet-placed macros in a random placement order], using a pseudo-random number generator. For illustration, it is assumed that the placements are represented by g1 through g1m (of FIG. 3C). Control then passes to step 310.”)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Meyyappan with teachings of Mirhoseini, Dudha and Sha for the same reasons disclosed for claim 6.
Regarding claim 18, Mirhoseini in view of Dudha and Sha teach the method of claim 16.
Mirhoseini in view of Dudha and Sha do not teach:
wherein the processing hardware is further operative to sequentially place all or a subset of the macros at random positions on the chip when constructing at least one of the negative samples
Meyyappan teaches:
wherein the processing hardware is further operative to sequentially place all or a subset of the macros at random positions on the chip when constructing at least one of the negative samples.
(Meyyappan, “[0044] In step 305, a first set of placements is generated [when constructing at least one of the negative samples]. Any approach, manual or automatic or a combination, can be used to generate such placements. However, in an embodiment, the location of each macro in each placement is determined randomly [wherein the processing hardware is further operative to sequentially place all or a subset of the macros at random positions on the chip], using a pseudo-random number generator. For illustration, it is assumed that the placements are represented by g1 through g1m (of FIG. 3C). Control then passes to step 310.”)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Meyyappan with teachings of Mirhoseini, Dudha and Sha for the same reasons disclosed for claim 6.
Regarding claim 19, Mirhoseini in view of Dudha and Sha teach the method of claim 16.
Mirhoseini in view of Dudha and Sha do not teach:
wherein the processing hardware is further operative to sequentially place all or a subset of the macros in a random placement order on the chip when constructing at least one of the negative samples.
Meyyappan teaches:
wherein the processing hardware is further operative to sequentially place all or a subset of the macros in a random placement order on the chip when constructing at least one of the negative samples
(Meyyappan, “[0044] In step 305, a first set of placements is generated [when constructing at least one of the negative samples]. Any approach, manual or automatic or a combination, can be used to generate such placements. However, in an embodiment, the location of each macro in each placement is determined randomly [wherein the processing hardware is further operative to sequentially place all or a subset of the macros in a random placement order on the chip], using a pseudo-random number generator. For illustration, it is assumed that the placements are represented by g1 through g1m (of FIG. 3C). Control then passes to step 310.”)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Meyyappan with teachings of Mirhoseini, Dudha and Sha for the same reasons disclosed for claim 6.
Claim(s) 9 – 10 are rejected under 35 U.S.C. 103 as being unpatentable over Mirhoseini in view of Dudha, Sha and in further view of Jain et al., Pub. No.: CN113326864A.
Regarding claim 9, Mirhoseini in view of Dudha and Sha teach the method of claim 1.
Mirhoseini in view of Dudha and Sha do not teach:
wherein the GNN is trained based on a contrastive loss function that measures distances between a pair of positive samples and between a pair of negative samples
Jian teaches:
wherein the GNN is trained based on a contrastive loss function that measures distances between a pair of positive samples and between a pair of negative samples.
(Jian, “[0007] Multiple similarity loss: Based on the structural loss [wherein the GNN is trained based on a contrastive loss function], a more generalized weighting strategy is used to design multiple similarity loss to make full use of positive and negative pairs. First, information pairs are mined using the triplet criterion through a pre-set threshold: positive pairs with a distance greater than the minimum distance of the minimum negative pair are sampled, and negative pairs with a distance less than the maximum distance plus the threshold of the positive pair are sampled [that measures distances between a pair of positive samples and between a pair of negative samples]. Specifically, the multiple similarity loss mines information pairs through the triplet criterion for positive and negative pairs, and then assigns different weights to positive and negative pairs respectively.”)
Jian, Mirhoseini, Dudha and Sha are related to the same field of endeavor (i.e.: neural network training). It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to combine the teaching of Jian with teachings of Mirhoseini, Dudha and Sha to leverage positive and negative examples with weighting similarity objectives to extend learning framework to more explicitly differentiate and refine representations based on relative placement quality, (Jian, ¶[0005] – [0007]).
Regarding claim 10, Mirhoseini in view of Dudha and Sha teach the method of claim 1.
Mirhoseini further teaches: wherein the true sample is an original trajectory of the completed macro placement.
(Mirhoseini, page: 2, “Simulated annealing (SA) is named for its analogy to metallurgy, in which metals are first heated and then gradually cooled to induce, or anneal, energy optimal crystalline surfaces. SA applies random perturbations to a given placement (e.g., shifts, swaps, or rotations of macros) wherein the true sample is an original trajectory of the completed macro placement], and then measures their effect on the objective function (e.g., half-perimeter wirelength described in Section 3.3.1)”)
Mirhoseini in view of Dudha and Sha do not teach:
wherein the GNN is trained based on a contrastive loss function that measures similarity between a true sample and a positive sample and between the true sample and one or more negative samples, and
Jain teaches:
wherein the GNN is trained based on a contrastive loss function that measures similarity between a true sample and a positive sample and between the true sample and one or more negative samples,
(Jian, “[0026] For example, if the similarity between a negative sample pair is large, it means that there is a high similarity between the negative sample and the query sample. Therefore, it is reasonable to ensure that there is a small distance between them, that is, to appropriately reduce the impact of the negative sample pair on the loss function [wherein the GNN is trained based on a contrastive loss function]. Conversely, if the similarity between a negative sample pair [and one or more negative samples] is small, it means that there is a large difference between the two samples [that measures similarity between a true sample and a positive sample and between the true sample]. For such sample pairs, the reasonable method should be to increase the distance between them. Unlike most loss functions, where the greater the similarity between negative sample pairs, the greater the impact on the loss function, and the smaller the similarity, the smaller the impact on the loss function, this will lead to the loss function not being able to accurately represent the gap between the training result and the optimization target in the later stages of training, thus failing to further improve the accuracy.”)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Jain with teachings of Mirhoseini, Dudha and Sha for the same reasons disclosed for claim 9.
Claim(s) 11 – 12 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Mirhoseini in view of Dudha, Sha and in further view of Fan et al., Pub. No.: CN113378074A.
Regarding claim 11, Mirhoseini in view of Dudha and Sha teach the method of claim 1.
Mirhoseini in view of Dudha and Sha do not teach:
wherein training the NN comprises: pre-training the NN using the positive samples and the negative samples; and fine-tuning the NN using the positive samples, the negative samples, and trajectories generated from the pre-trained NN.
Fan teaches:
wherein training the NN comprises: pre-training the NN using the positive samples and the negative samples; and fine-tuning the NN using the positive samples, the negative samples, and trajectories generated from the pre-trained NN.
(Fan, “[0042] The idea of this invention is to reasonably expand trajectory data using data augmentation techniques, and then combine this with a self-supervised method to better learn the representation of trajectory data. Then, a pre-trained model is constructed (this model includes deep learning neural network layers such as RNN and attention mechanisms). In the pre-trained model [wherein training the NN comprises: pre-training the NN], contrastive learning is used to construct positive and negative samples [using the positive samples and the negative samples;], learning the mutual information between different trajectory points. Then, the parameters learned in the pre-trained model are transferred to downstream tasks, and fine-tuning is used to improve the performance of the downstream tasks [and fine-tuning the NN using the positive samples, the negative samples and trajectories generated from the pre-trained NN]. The downstream tasks refer to supervised learning tasks using pre-trained models or components, as described in this field. Specifically, the following steps are included”)
Fan, Mirhoseini, Dudha and Sha are related to the same field of endeavor (i.e.: neural network training). It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to combine the teaching of Fan with teachings of Mirhoseini, Dudha and Sha to add the concept of contrastive learning over trajectories using positive and negative samples to improve representation learning by capturing relationships between high-quality and low-quality placement over time, (Fan, ¶[0040] – [0042]).
Regarding claim 12, Mirhoseini in view of Dudha, Sha and Fan teach the method of claim 11.
Fan further teaches: wherein pre-training the NN further comprises: updating parameters of the GNN based on a contrastive loss function calculated from the positive samples and the negative samples; and
(Fan, “[0044] S2. Input the data augmented trajectory data and the vector representation of trajectory points into the pre-trained model. Divide the trajectory time period into the current trajectory Tc and the historical trajectory Th. Learn the different features of the current and historical trajectories. In the pre- trained model, use contrastive learning to construct a positive and negative sample and noise contrast loss function [wherein pre-training the NN further comprises: updating parameters of the GNN based on a contrastive loss function calculated from the positive samples and the negative samples;]. Learn the mutual information between different trajectory points. Distinguish between real advantageous positions and a few negative positions to capture the implicit movement intention. Save the parameters in the pre-trained model.”)
updating parameters of the NN including the GNN based on a loss function different from the contrastive loss function.
(Fan, “[0064] Adam is an algorithm that performs first-order gradient optimization on a stochastic objective function. This algorithm is based on adaptive low-order moment estimation. It can adjust different learning rates for each different parameter, updating frequently changing parameters [updating parameters of the NN including the GNN based on a loss function different from the contrastive loss function] with smaller step sizes and sparse parameters with larger step sizes. The diagonal rescaling of the Adam algorithm gradient is invariant, so it is well-suited for solving problems with largescale data or parameters.”)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Fan with teachings of Mirhoseini, Dudha and Sha for the same reasons disclosed for claim 11.
Regarding claim 20, Mirhoseini in view of Dudha and Sha teach the method of claim 16.
Mirhoseini in view of Dudha and Sha do not teach:
wherein the processing hardware is further operative to update parameters of the GNN based on a contrastive loss function calculated from the positive samples and the negative samples.
Fan teaches:
wherein the processing hardware is further operative to update parameters of the GNN based on a contrastive loss function calculated from the positive samples and the negative samples.
(Fan, “[0044] S2. Input the data augmented trajectory data and the vector representation of trajectory points into the pre-trained model. Divide the trajectory time period into the current trajectory Tc and the historical trajectory Th. Learn the different features of the current and historical trajectories. In the pre- trained model, use contrastive learning to construct a positive and negative sample and noise contrast loss function [wherein the processing hardware is further operative to update parameters of the GNN based on a contrastive loss function calculated from the positive samples and the negative samples]. Learn the mutual information between different trajectory points. Distinguish between real advantageous positions and a few negative positions to capture the implicit movement intention. Save the parameters in the pre-trained model.”)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the present application to combine the teachings of Fan with teachings of Mirhoseini, Dudha and Sha for the same reasons disclosed for claim 11.
Allowable Subject Matter
Claim(s) 13 – 15 objected to as being dependent upon a rejected base claim, but would be allowable if rewritten or amended to overcome 35 U.S.C. 101 rejection set forth in this Office action and rewritten in independent form including all of the limitations of the base claim and any intervening claims.
The prior art made of record does not teach, make obvious, or suggest the claim limitations as disclosed in applicant's claims.
Claim 13 recites:
wherein fine-tuning the NN further comprises: updating parameters of the GNN based on a contrastive loss function calculated from the positive samples and the negative samples; and updating parameters of the NN excluding the GNN based on a loss function different from the contrastive loss function. wherein fine-tuning the NN further comprises: updating parameters of the GNN based on a contrastive loss function calculated from the positive samples and the negative samples; and updating parameters of the NN excluding the GNN based on a loss function different from the contrastive loss function.
The closest prior art(s):
Mirhoseini et al., "Chip placement with deep reinforcement learning".
Mirhoseini presents a learning-based chip placement system that formulates placement as a reinforcement learning problem, enabling an agent to automatically place netlist nodes on a chip canvas while improving though experience. The system uses supervised prediction of placement quality to learn transferable representations that generalize to previously unseen chip blocks. However Mirhoseini, does not teach fine-tuning the neural network involving updating the parameters of the graph neural network (GNN) using a contrastive loss based on positive and negative samples, while simultaneously updating the remaining neural network parameters using a different loss function.
Dudha et al., Pub. No.: US20190378047A1.
Dudha teaches a system for reducing latency of a circuit design by determining a set of sequential circuit elements of a circuit design that meets a condition for removal from the circuit design, wherein the condition is dependent upon a target technology process and a target operating frequency. However, Dudha does not teach fine-tuning the neural network involving updating the parameters of the graph neural network (GNN) using a contrastive loss based on positive and negative samples, while simultaneously updating the remaining neural network parameters using a different loss function.
Claim 14 recites:
wherein fine-tuning the NN further comprises: updating parameters of the NN excluding the GNN based on gradient descent with a first learning rate; and updating parameters of the GNN based on the gradient descent with a second learning rate different from the first learning rate.
The closest prior art(s):
Mirhoseini et al., "Chip placement with deep reinforcement learning".
Mirhoseini presents a learning-based chip placement system that formulates placement as a reinforcement learning problem, enabling an agent to automatically place netlist nodes on a chip canvas while improving though experience. The system uses supervised prediction of placement quality to learn transferable representations that generalize to previously unseen chip blocks. However Mirhoseini, does not teach fine-tuning the NN further by updating parameters of the NN excluding the GNN based on gradient descent with a first learning rate; and updating parameters of the GNN based on the gradient descent with a second learning rate different from the first learning rate.
Dudha et al., Pub. No.: US20190378047A1.
Dudha teaches a system for reducing latency of a circuit design by determining a set of sequential circuit elements of a circuit design that meets a condition for removal from the circuit design, wherein the condition is dependent upon a target technology process and a target operating frequency. However, Dudha does not teach fine-tuning the NN further by updating parameters of the NN excluding the GNN based on gradient descent with a first learning rate; and updating parameters of the GNN based on the gradient descent with a second learning rate different from the first learning rate.
Claim 15 recites:
wherein fine-tuning the NN further comprises: generating, by the NN, a first set of trajectories for updating NN parameters, wherein each trajectory in the first set includes an action that is sampled stochastically according to a probability distribution, the action indicating a coordinate on a chip canvas to place a macro; and generating, by the NN, a second set of trajectories for evaluating the updated NN parameters, wherein each trajectory in the second set includes another action that is chosen according to another probability distribution as having a highest probability.
The closest prior art(s):
Mirhoseini et al., "Chip placement with deep reinforcement learning".
Mirhoseini presents a learning-based chip placement system that formulates placement as a reinforcement learning problem, enabling an agent to automatically place netlist nodes on a chip canvas while improving though experience. The system uses supervised prediction of placement quality to learn transferable representations that generalize to previously unseen chip blocks. However Mirhoseini, does not teach generating, a first set of trajectories for updating NN parameters, wherein each trajectory in the first set includes an action that is sampled stochastically according to a probability distribution, the action indicating a coordinate on a chip canvas to place a macro; and generating, a second set of trajectories for evaluating the updated NN parameters, wherein each trajectory in the second set includes another action that is chosen according to another probability distribution as having a highest probability.
Dudha et al., Pub. No.: US20190378047A1.
Dudha teaches a system for reducing latency of a circuit design by determining a set of sequential circuit elements of a circuit design that meets a condition for removal from the circuit design, wherein the condition is dependent upon a target technology process and a target operating frequency. However, Dudha does not teach generating, a first set of trajectories for updating NN parameters, wherein each trajectory in the first set includes an action that is sampled stochastically according to a probability distribution, the action indicating a coordinate on a chip canvas to place a macro; and generating, a second set of trajectories for evaluating the updated NN parameters, wherein each trajectory in the second set includes another action that is chosen according to another probability distribution as having a highest probability.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Lin et al., Pub. No.: US20180150583A1.
Lin teaches macro placement includes partitioning an entire region of a semiconductor chip into sub-regions; determining a packing sequence of a plurality of movable macros in the sub-region; extracting search points of a plurality of placed blocks in the sub-region with respect to one of the movable macros
Chen et al., Pub. No.: US8661388B2.
Chen describes a multi-packing tree (MPT) macro placer, creating a k-level binary multi-packing tree comprising k branch nodes each corresponding to one level and k+1 packing sub-trees each corresponding to one of the nodes and comprising a group of macros, optimizing the multi-packing tree according to a packing result thereof, and generating output files in a DEF format
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any extension fee pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner
should be directed to MATIYAS T MARU whose telephone number is (571)270-0902 or via email: matiyas.maru@uspto.gov. The examiner can normally be reached Monday - Friday (8:00am - 4:00pm) EST.
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,
Michelle Bechtold can be reached on (571)431-0762. The fax phone number for the organization were 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.
/M.T.M./ Examiner, Art Unit 2148
/MICHELLE T BECHTOLD/Supervisory Patent Examiner, Art Unit 2148
Prosecution Insights