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 .
Claims 1-11 are presented for examination. Claims 12-20 have been withdrawn. Applicant is reminded to cancel non-elected claims.
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-11 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Independent Claims
Step 1 – Claim 1 is drawn to a method. Therefore, it falls under one of the four categories of statutory subject matter (process/method, machine/product/apparatus, manufacture or composition of matter).
Step 2A Prong 1 – Claim 1 is directed to a judicially recognized exception of an abstract idea without significantly more. Claim 1 recites:
generating a probability distribution of an action under a current state of a chip, the action indicating a coordinate on the chip to place a macro – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 12, Lines 38-41] of the specification, it states “The policy network generates a policy
π
θ
(
a
|
s
)
, where
π
θ
(
a
|
s
)
is a probability distribution over action a. The value network generates a value that predicts the reward of action a. The macro-order network generates a policy
ρ
θ
(
a
|
s
)
, where
ρ
θ
a
s
is a probability distribution over action m.” BRI in light of the specification would support that “generating a probability distribution of an action” would encompass a series of mathematical computations and fall under the mathematical concepts grouping.
optimize a reward calculated from the objectives and the preferences – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 10, Lines 30-36] of the specification, it states “At time
T
=
0
, the NN with policy
π
0
is randomly initialized to produce trajectories
S
0
=
{
τ
1
,
τ
2
,
…
,
τ
n
}
, and a reward function
R
0
(
τ
)
is randomly initialized. At
T
=
t
, the system first search for a reward function
R
t
(
τ
)
that satisfies the constraint:
∑
τ
^
∈
S
^
R
t
(
τ
^
)
>
∑
τ
∈
S
t
R
t
(
τ
)
(S1110), since
S
^
is the set of golden samples. The reward
∑
τ
^
∈
S
^
R
t
(
τ
^
)
is referred to as the target reward, and
∑
τ
∈
S
t
R
t
(
τ
)
is referred to as the learned reward. The reward search may be performed by another NN such as A004 in FIG. 10A using a method 1200 illustrated in FIG. 12. If an
R
t
(
τ
)
that satisfies the constraint can be found (S1120), the NN proceeds to search for a policy
π
t
+
1
whose samples (i.e., trajectories)
S
t
+
1
maximize
∑
τ
∈
S
t
+
1
R
t
(
τ
)
(S1130).” BRI in light of the specification would support that “optimiz[ing] a reward calculated from the objectives and the preferences” would encompass a series of mathematical computations and fall under the mathematical concepts grouping.
Step 2A Prong 2 – The following additional limitations recited do not integrate the abstract idea into a practical application:
receiving an input including a plurality of objectives and a subspace of preferences – This limitation recites an insignificant extra-solution activity of mere data gathering (see MPEP § 2106.05(g)) and thus, fails to integrate the exception into a practical application.
wherein each preference is a vector of weights assigned to corresponding objectives, and each objective is a measurement of a placement characteristic – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to semiconductors and thus, fails to integrate the exception into a practical application.
training the NN to place macros on a training set of chips to optimize a reward – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to ---being performed by a computer in a computer environment. It additionally merely recites the idea of performing --neural network training and fails to recite details of how the training of the model to optimize a reward is accomplished beyond the conclusory assertion of a trained model that performs the abstract idea. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to integrate the exception into a practical application.
by the NN – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to ---being performed by a computer in a computer environment and thus, fails to integrate the exception into a practical application.
generating a sequence of (state, action) pairs to form a trajectory, wherein a final state in the trajectory corresponds to a completed macro placement – This limitation merely recites the idea of generating a trajectory comprising a sequence of (state, action) pairs and fails to recite details of how the generating is accomplished beyond the result-oriented assertion of a completed macro placement. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to integrate the exception into a practical application.
Step 2B – The additional elements in Step 2A Prong 2, view individually or wholistically, do not provide an inventive concept or otherwise amount to significantly more than the abstract idea itself.
receiving an input including a plurality of objectives and a subspace of preferences – This limitation recites an insignificant extra-solution activity of mere data gathering (see MPEP § 2106.05(g)), which is well-understood, routine and conventional activity similar to cases reviewed by the courts involving receiving or transmitting data over a network (see MPEP § 2106.05(d)(II)) and thus, fails to provide significantly more to the judicial exception.
wherein each preference is a vector of weights assigned to corresponding objectives, and each objective is a measurement of a placement characteristic – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to semiconductors and thus, fails to provide significantly more to the judicial exception.
training the NN to place macros on a training set of chips to optimize a reward – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to ---being performed by a computer in a computer environment. It additionally merely recites the idea of performing --neural network training and fails to recite details of how the training of the model to optimize a reward is accomplished beyond the conclusory assertion of a trained model that performs the abstract idea. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to provide significantly more to the judicial exception.
by the NN – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to ---being performed by a computer in a computer environment and thus, fails to provide significantly more to the judicial exception.
generating a sequence of (state, action) pairs to form a trajectory, wherein a final state in the trajectory corresponds to a completed macro placement – This limitation merely recites the idea of generating a trajectory comprising a sequence of (state, action) pairs and fails to recite details of how the generating is accomplished beyond the result-oriented assertion of a completed macro placement. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to provide significantly more to the judicial exception.
As such, Claim 1 is not patent eligible.
Dependent Claims
Claims 2-11 merely narrow the previously cited abstract idea limitations. For the reasons described above with respect to independent claims 2-11, these judicial exceptions are not meaningfully integrated into a practical application, nor amount to significantly more than the abstract idea itself. The claims disclose similar limitations described for the independent claims above and do not provide anything more than the mental processes that are practically capable of being performed in the human mind with the assistance of pen and paper and mathematical concepts that are achievable through mathematical computation. Therefore claims 2-11 also recite abstract ideas that do not integrate into a practical application or amount to significantly more than the judicial exception, and are rejected under U.S.C. § 101.
Step 1 – Claims 2-11 are drawn to a method. Therefore, each of these claims fall under one of the four categories of statutory subject matter (process/method, machine/product/apparatus, manufacture or composition of matter).
Step 2A Prong 1 – These claims are directed to a judicially recognized exception of an abstract idea without significantly more.
Claim 2:
wherein training the NN includes encoding a sampled preference from the subspace into a latent state of the NN – This limitation is directed towards the abstract idea of a mathematical relationship (see MPEP § 2106.04(a)(2), section I, A). On [Page 4, Lines 10-12] of the specification, it states “NN 10 receives an input including state s (macro, netlist graph, node id), netlist metadata, and preference ω, each of which is encoded into a low-dimension vector called embedding. NN 10 concatenates these embedding vectors to represent a latent state”. BRI in light of the specification would support that “encoding a sampled preference into a latent state” would encompass organizing information and manipulating information through mathematical correlation and fall under the mathematical concepts grouping.
Claim 3:
wherein the reward is calculated from a linear combination of a sampled preference from the subspace and the corresponding objectives – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 11, Lines 17-20] of the specification, it states “The input to method 1300 includes a preference subspace Ω and a set of objectives
{
o
i
}
i
=
1
K
, in addition to all of the inputs to method 1100 (FIG. 11). Furthermore, the reward function in method 1300 is a linear combination of objectives and the corresponding preference values; i.e., reward function
R
τ
=
∑
i
=
1
K
ω
i
o
i
(
τ
)
.” BRI in light of the specification would support that “calculating the reward from a linear combination of a sampled preference and corresponding objectives” would encompass a linear combination and fall under the mathematical concepts grouping.
Claim 4:
applying a mask to the probability distribution to produce a masked distribution over the chip, wherein the mask blocks off areas on the chip – This limitation is directed towards the abstract idea of a mathematical relationship (see MPEP § 2106.04(a)(2), section I, A). On [Page 5, Lines 1-4] of the specification, it states “An example of a masked distribution is as follows. If the probability distribution generated by the policy network of NN 20 over 5 coordinates where actions can take place is: [Table]. Applying a mask that blocks out areas where actions 1, 2, and 4 can take place, this probability distribution becomes a masked distribution as follows: [Table]”. BRI in light of the specification would support that “applying a mask to the probability distribution” would encompass organizing information and manipulating information through mathematical correlation and fall under the mathematical concepts grouping.
based on a stochastic policy, sampling the action according to the masked distribution – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 4, Lines 43-44] of the specification, it states “With a stochastic policy, NN 20 samples an action for placing a macro according to the masked distribution.” BRI in light of the specification and the plain meaning of “stochastic policy” in reinforcement learning would support that “sampling the action based on a stochastic policy” would encompass random selection of actions weighted by the probability of each action in the distribution and fall under the mathematical concepts grouping.
Claim 5:
sampling a set of trajectories in a sample collection operation according to the stochastic policy – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 4, Lines 43-44] of the specification, it states “With a stochastic policy, NN 20 samples an action for placing a macro according to the masked distribution.” BRI in light of the specification and the plain meaning of “stochastic policy” in reinforcement learning would support that “sampling a set of trajectories according to the stochastic policy” would encompass random selection of actions weighted by the probability of each action in the distribution and fall under the mathematical concepts grouping.
using the set of trajectories to calculate an update to parameters of the NN – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 7, Lines 15-17] of the specification, it states “The NN calculates the loss function
L
C
L
I
P
+
V
F
+
S
(
θ
,
ω
)
based on this mini-batch (S620), and updates the parameters ϴ of NN based on gradient descent (S630):
θ
←
θ
-
η
∇
θ
L
C
L
I
P
+
V
F
+
S
(
θ
,
ω
)
, where η is the learning state.” BRI in light of the specification would support that “calculate an update to the parameters of the NN” would encompass a loss calculation and subsequent gradient descent and fall under the mathematical concepts grouping.
Claim 6:
applying a mask to the probability distribution to produce a masked distribution over the chip, wherein the mask blocks off areas on the chip – This limitation is directed towards the abstract idea of a mathematical relationship (see MPEP § 2106.04(a)(2), section I, A). On [Page 5, Lines 1-4] of the specification, it states “An example of a masked distribution is as follows. If the probability distribution generated by the policy network of NN 20 over 5 coordinates where actions can take place is: [Table]. Applying a mask that blocks out areas where actions 1, 2, and 4 can take place, this probability distribution becomes a masked distribution as follows: [Table]”. BRI in light of the specification would support that “applying a mask to the probability distribution” would encompass organizing information and manipulating information through mathematical correlation and fall under the mathematical concepts grouping.
based on a deterministic policy, choosing the action with a highest probability according to the masked distribution – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 4, Lines 42-43] of the specification, it states “With a deterministic policy, NN 20 chooses an action with the highest probability to place a macro according to the masked distribution.” BRI in light of the would support that “choosing the action based on a deterministic policy” would encompass selecting an action based on a basic numerical comparison and fall under the mathematical concepts grouping.
Claim 7:
sampling a set of trajectories in an evaluation operation according to the deterministic policy – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 4, Lines 42-43] of the specification, it states “With a deterministic policy, NN 20 chooses an action with the highest probability to place a macro according to the masked distribution.” BRI in light of the would support that “sampling a set of trajectories according to the deterministic policy” would encompass selecting an action based on a basic numerical comparison and fall under the mathematical concepts grouping.
calculating a final reward value from a plurality of reward values, each reward value calculated based on a final state of one of the trajectories – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 8, Lines 22-26] of the specification, it states “The NN proceeds to calculate the reward
r
ω
=
∑
i
=
1
K
o
i
ω
i
based on the final state sη in this trajectory and collect this reward (S730). S710, S720 (including S721-S723), and S730 are repeated until the number of collected rewards has reached a predetermined threshold (S740). The NN then averages over all the collected rewards (S750) and outputs a single reward value (S760).” BRI in light of the specification would support that “calculating a final reward value” would encompass series of mathematical computations and fall under the mathematical concepts grouping.
Claim 8:
sampling a final trajectory using the further-trained NN to generate the completed macro placement – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 5, Lines 23-27] of the specification, it states “The NN trained in the first stage is further trained with the training phase (S101), and then samples a trajectory based on the new preference ω with the deterministic policy (S102). The deterministic policy is described with reference to network A001 in FIG. 1A. The output of the second stage is the new chip paces with macros (i.e., the final state sη in the trajectory).” BRI in light of the specification would support that “sampling a final trajectory using the further-trained NN” would encompass applying a deterministic policy and fall under the mathematical concepts grouping.
Claim 9:
wherein the objectives further include a distance to at least one of a positive anchor and a negative anchor, the positive anchor to attract the placement of a first subset of the macros and the negative anchor to repel the placement of a second subset of the macros – This limitation is directed towards the abstract idea of a mathematical formula (see MPEP § 2106.04(a)(2), section I, B). On [Page 6, Lines 7-14] of the specification, it states “In one embodiment, a location objective may be modeled as positional anchors. Anchors are pairs of positional coordinates together with influence weights on the positions of selected macros. The influence of an anchor a on a macro m, denoted t(a, m), is a positive scalar function that can be computed from positional information alone. A reward objective corresponding to the anchors is formed as a weighted sum:
∑
a
n
c
h
o
r
α
∑
m
a
c
r
o
m
i
w
i
α
i
(
α
,
m
i
)
. The anchors with only negative weights are referred to as negative anchors and the anchors with only positive weights are referred to as positive anchors.” BRI in light of the specification would support that “objective including distance to a positive anchor and a negative anchor” would encompass a scalar function for influencing the probability distribution for the placement of macros and fall under the mathematical concepts grouping.
Claim 10:
modifying the candidate preference to generate p preferences – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 9, Lines 28-33] of the specification, it states “The selected placement may be the closest to the designer’s hidden preference. The NN then generates another p preferences
{
ω
j
}
j
=
1
p
by a small perturbation in the preference ωs selected by the designer (S870). For example, a script may modify one or more preference values ωj in ωs by respective one or more delta values, where each delta value is in a predetermined value range (e.g., within the range of +/-ε). S820, S830, and S840 are repeated until the designer accepts one of the placements generated by the NN.” BRI in light of the specification would support that “modifying the preference to generates p preferences” would a series of numerical perturbations of objective weights and fall under the mathematical concepts grouping.
Claim 11:
modifying one or more vector elements of the candidate preference by respective one or more delta values, wherein each delta value is in a predetermined value range – This limitation is directed towards the abstract idea of a mathematical calculation (see MPEP § 2106.04(a)(2), section I, C). On [Page 9, Lines 28-33] of the specification, it states “The selected placement may be the closest to the designer’s hidden preference. The NN then generates another p preferences
{
ω
j
}
j
=
1
p
by a small perturbation in the preference ωs selected by the designer (S870). For example, a script may modify one or more preference values ωj in ωs by respective one or more delta values, where each delta value is in a predetermined value range (e.g., within the range of +/-ε). S820, S830, and S840 are repeated until the designer accepts one of the placements generated by the NN.” BRI in light of the specification would support that “modifying one or more vector elements of the candidate preference” would a series of numerical perturbations of objective weights and fall under the mathematical concepts grouping.
Step 2A Prong 2 – These limitations do not recite any additional elements which integrate the abstract idea into a practical application.
Claim 8:
receiving, after the training of the NN, a given preference and a given chip on which a plurality of macros are to be placed – This limitation recites an insignificant extra-solution activity of mere data gathering (see MPEP § 2106.05(g)) and thus, fails to integrate the exception into a practical application.
further training the NN with the given preference and a plurality of stochastically sampled trajectories on the given chip – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to ---being performed by a computer in a computer environment. It additionally merely recites the idea of performing --further neural network training and fails to recite details of how the training of the model is accomplished beyond the conclusory assertion of a trained model that performs the abstract idea. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to integrate the exception into a practical application.
Claim 10:
generating a set of placements by the NN to place a same set of macros on a given chip, wherein each placement is generated based on a different preference – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to ---being performed by a neural network in a computer environment. It additionally merely recites the idea of generating a set of placements and fails to recite details of how the generating a set of placements is accomplished beyond the result-oriented assertion of a set of placements. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to integrate the exception into a practical application.
receiving an indication of a candidate placement among the set of placements, wherein the candidate placement is generated based on a candidate preference – This limitation recites an insignificant extra-solution activity of mere data gathering (see MPEP § 2106.05(g)) and thus, fails to integrate the exception into a practical application.
generating a subsequent set of p placements by the NN to place the same set of macros on the given chip – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to ---being performed by a neural network in a computer environment. It additionally merely recites the idea of generating a set of placements and fails to recite details of how the generating a set of placements is accomplished beyond the result-oriented assertion of a set of placements. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to integrate the exception into a practical application.
repeating the receiving of the indication, the modifying of the candidate preference, and the generating of the subsequent set of p placements until a final placement is accepted – This limitation recites iteratively providing and receiving feedback from a user, which an insignificant extra-solution activity of mere data gathering similar to OIP Technologies (Presenting offers to potential customers and gathering statistic generated based on the testing about how potential customers responded to the offers; the statistics are then used to calculate an optimized price) (see MPEP § 2106.05(g)) and thus, fails to integrate the exception into a practical application.
Step 2B – These limitations, as a whole, do not amount to significantly more than the judicial exception.
Claim 8:
receiving, after the training of the NN, a given preference and a given chip on which a plurality of macros are to be placed – This limitation recites an insignificant extra-solution activity of mere data gathering (see MPEP § 2106.05(g)), which is well-understood, routine and conventional activity similar to cases reviewed by the courts involving receiving or transmitting data over a network (see MPEP § 2106.05(d)(II)) and thus, fails to provide significantly more to the judicial exception.
further training the NN with the given preference and a plurality of stochastically sampled trajectories on the given chip – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to ---being performed by a computer in a computer environment. It additionally merely recites the idea of performing --further neural network training and fails to recite details of how the training of the model is accomplished beyond the conclusory assertion of a trained model that performs the abstract idea. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to provide significantly more to the judicial exception.
Claim 10:
generating a set of placements by the NN to place a same set of macros on a given chip, wherein each placement is generated based on a different preference – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to ---being performed by a neural network in a computer environment. It additionally merely recites the idea of generating a set of placements and fails to recite details of how the generating a set of placements is accomplished beyond the result-oriented assertion of a set of placements. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to provide significantly more to the judicial exception.
receiving an indication of a candidate placement among the set of placements, wherein the candidate placement is generated based on a candidate preference This limitation recites an insignificant extra-solution activity of mere data gathering (see MPEP § 2106.05(g)), which is well-understood, routine and conventional activity similar to cases reviewed by the courts involving receiving or transmitting data over a network (see MPEP § 2106.05(d)(II)) and thus, fails to provide significantly more to the judicial exception.
generating a subsequent set of p placements by the NN to place the same set of macros on the given chip – This limitation amounts to no more than generally linking the use of the judicial exception to a particular technological environment or field of use (see MPEP § 2106.05(h)). It merely limits the use of the abstract idea to ---being performed by a neural network in a computer environment. It additionally merely recites the idea of generating a set of placements and fails to recite details of how the generating a set of placements is accomplished beyond the result-oriented assertion of a set of placements. Reciting the idea of a solution or outcome without detailing how the result is accomplished is equivalent to saying "apply it" (see MPEP § 2106.05(f)) and thus, fails to provide significantly more to the judicial exception.
repeating the receiving of the indication, the modifying of the candidate preference, and the generating of the subsequent set of p placements until a final placement is accepted – This limitation recites the well-understood, routine, conventional activity of performing repetitive calculations (see MPEP § 2106.05(d)) and thus, fails to provide significantly more to the judicial exception.
As such, Claims 2-11 are not patent eligible.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-5 and 8-9 are rejected under 35 U.S.C. 103 as being unpatentable over Mirhoseini et al. (“Chip Placement with Deep Reinforcement Learning”, published 04/22/2020), hereinafter Mirhoseini; in view of Yang et al. (“A Generalized Algorithm for Multi-Objective Reinforcement Learning and Policy Adaptation”, published 12/14/2019), hereinafter Yang. Mirhoseini was cited in the IDS filed 05/10/2026.
Regarding Claim 1, Mirhoseini teaches A method for macro placement by a neural network (NN) (Mirhoseini: “We propose a novel neural architecture that enables us to train domain-adaptive policies for chip placement.” [Section 4.1. A Supervised Approach to Enable Transfer Learning]), comprising:
receiving an input including a plurality of objectives, wherein each objective is a measurement of a placement characteristic (Mirhoseini: “Figure 2 depicts an overview of the policy network (modeled by πθ in Equation 3) and the value network architecture that we developed for chip placement. The inputs to these networks are the netlist graph (graph adjacency matrix and node features), the id of the current node to be placed, and the metadata of the netlist and the semiconductor technology.” [Section 4.2. Policy Network Architecture]; “In this work, we target the chip placement optimization problem, in which the objective is to map the nodes of a netlist (the graph describing the chip) onto a chip canvas (a bounded 2D space), such that final power, performance, and area (PPA) is optimized.” [Section 3.1. Problem Statement]; “To combine multiple objectives into a single reward function, we take the weighted sum of proxy wirelength and congestion where the weight can be used to explore the trade-off between the two metrics.” [Section 3.3. Reward]);
training the NN to place macros on a training set of chips to optimize a reward calculated from the objectives (Mirhoseini: “we pose placement as a Reinforcement Learning (RL) problem and train an agent to place the nodes of a chip netlist onto a chip canvas. To enable our RL policy to generalize to unseen blocks, we ground representation learning in the supervised task of predicting placement quality. By designing a neural architecture that can accurately predict reward across a wide variety of netlists and their placements, we are able to generate rich feature embeddings of the input netlists.” [Abstract]; “Through repeated episodes (sequences of states, actions, and rewards), the policy network learns to take actions that will maximize cumulative reward.” [Section 3.2. Overview of Our Approach]; “To combine multiple objectives into a single reward function, we take the weighted sum of proxy wirelength and congestion where the weight can be used to explore the trade-off between the two metrics.” [Section 3.3. Reward]);
generating, by the NN, a probability distribution of an action under a current state of a chip, the action indicating a coordinate on the chip to place a macro (Mirhoseini: “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) onto which that macro can be placed without violating any hard constraints on density or blockages). state transition: given a state and an action, this is the probability distribution over next states.” [Section 3.2. Overview of Our Approach]; “For policy optimization purposes, we convert the canvas into a m × n grid. Thus, for any given state, the action space (or the output of the policy network) is the probability distribution of placements of the current macro over the m × n grid. The action is the argmax of this probability distribution.” [Section 3.4. Action Representation]); and
generating, by the NN, a sequence of (state, action) pairs to form a trajectory, wherein a final state in the trajectory corresponds to a completed macro placement (Mirhoseini: “Through repeated episodes (sequences of states, actions, and rewards), the policy network learns to take actions that will maximize cumulative reward. We use Proximal Policy Optimization (PPO) (Schulman et al., 2017) to update the parameters of the policy network, given the cumulative reward for each placement.” [Section 3.2. Overview of Our Approach]; “In our setting, at the initial state, s0, we have an empty chip canvas and an unplaced netlist. The final states T 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).” [Section 3.2. Overview of Our Approach]).
However, Mirhoseini fails to expressly disclose receiving an input including a subspace of preferences, wherein each preference is a vector of weights assigned to corresponding objectives; and optimizing a reward calculated from the preferences.
In the same field of endeavor, Yang teaches receiving an input including a subspace of preferences, wherein each preference is a vector of weights assigned to corresponding objectives (Yang: “A multi-objective Markov decision process (MOMDP) can be represented by the tuple <S,A,P,r,Ω,fΩ> with state space S, action space A, transition distribution P(s’|s,a), vector reward function r(s,a), the space of preferences Ω, and preference functions, e.g., fω(r) which produces a scalar utility using preference ω ∈ Ω.” [Section 2. Background]; “Since our goal is to induce a single model that can adapt to the entire space of Ω, we use one parameterized function to represent Q ⊆ (Ω → Rm)S×A. We achieve this by using a deep neural network with s,ω as input and |A| × m Q-values as output.” [Section 3. Multi-objective RL with Envelope Value Updates]); and
optimizing a reward calculated from the preferences (Yang: “we learn a set of policies simultaneously over multiple preferences, and our concept of optimality is defined on vectorized rewards” [Section 3. Multi-objective RL with Envelope Value Updates]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to have incorporated receiving an input including a subspace of preferences, wherein each preference is a vector of weights assigned to corresponding objectives; and optimizing a reward calculated from the preferences, as taught by Yang to the method of Mirhoseini because both of these methods are directed towards determining an optimal policy for tasks within multi-objective reinforcement learning. In making this combination and basing the reward on a preferences corresponding to objectives provided by the user, it would allow the method of Mirhoseini to define the relative importance of multiple competing objectives (Yang: [Abstract]) and subsequently adapt to new tasks with unseen preferences (Yang: [Section 2. Background]).
Regarding Claim 2, Mirhoseini and Yang teach the method of Claim 1, wherein training the NN includes encoding a sampled preference from the subspace into a latent state of the NN (Mirhoseini: “To train a supervised model that can accurately predict wire length and congestion labels and generalize to unseen data, we developed a novel graph neural network architecture that embeds information about the netlist. The role of graph neural networks is to distill information about the type and connectivity of a node within a large graph into low-dimensional vector representations which can be used in downstream tasks.” [Abstract]; Yang: “For policy optimization purposes, we convert the canvas into a m × n grid. Thus, for any given state, the action space (or the output of the policy network) is the probability distribution of placements of the current macro over the m × n grid. The action is the argmax of this probability distribution.” [Section 3.4. Action Representation]; In light of [Page 4, Lines 10-13] of the specification, which states “NN 10 receives an input including state s (macro, netlist graph, node id), netlist metadata, and preference ω, each of which is encoded into a low-dimension vector called embedding. NN 10 concatenates these embedding vectors to represent a latent state”, BRI would support that encoding a preference into latent state of the NN would encompass representing the components of the input as a concatenated embedding that can be interpretated by the NN).
Regarding Claim 3, Mirhoseini and Yang teach the method of Claim 1, wherein the reward is calculated from a linear combination of a sampled preference from the subspace and the corresponding objectives (Mirhoseini: “The reward, a linear combination of the approximate wirelength and congestion, are calculated and passed to the agent to optimize its parameters for the next iteration.” [Fig. 1]).
Regarding Claim 4, Mirhoseini and Yang teach the method of Claim 1, wherein generating the probability distribution of the action further comprises:
applying a mask to the probability distribution to produce a masked distribution over the chip, wherein the mask blocks off areas on the chip (Mirhoseini: “A feasible standard cell cluster placement should meet the following criterion: the density of placed items in each grid cell should not exceed a given target density threshold (maxdensity). We set this threshold to be 0.6 in our experiments. To meet this constraint, during each RL step, we calculate the current density mask, a binary m × n matrix that represents grid cells onto which we can place the center of the current node without violating the density threshold criteria. Before choosing an action from the policy network output, we first take the dot product of the mask and the policy network output and then take the argmax over feasible locations. This approach prevents the policy network from generating placements with overlapping macros or dense standard cell areas.” [Section 3.3.6. Density]); and
based on a stochastic policy, sampling the action according to the masked distribution (Mirhoseini: “For policy optimization purposes, we convert the canvas into a m × n grid. Thus, for any given state, the action space (or the output of the policy network) is the probability distribution of placements of the current macro over the m × n grid. The action is the argmax of this probability distribution.” [Section 3.4. Action Representation]; Plain meaning of "stochastic policy" in reinforcement learning, supported by [Page 4, Lines 42-44] of the specification, is a policy that maps each state to a probability distribution over actions, as opposed to "deterministic policy" in which the same action is always selected for a given state.).
Regarding Claim 5, Mirhoseini and Yang teach the method of Claim 4, wherein training the NN further comprises:
sampling a set of trajectories in a sample collection operation according to the stochastic policy (Mirhoseini: “Through repeated episodes (sequences of states, actions, and rewards), the policy network learns to take actions that will maximize cumulative reward.” [Section 3.2. Overview of Our Approach]; “To combine multiple objectives into a single reward function, we take the weighted sum of proxy wirelength and congestion where the weight can be used to explore the trade-off between the two metrics.” [Section 3.3. Reward]; “Our goal is to develop RL agents that can generate higher quality results as they gain experience placing chips. We can formally define the placement objective function as follows: [Equation 3]. Here J(θ,G) is the cost function. The agent is parameterized by θ. The dataset of netlist graphs of size K is denoted by G with each individual netlist in the dataset written as g. Rp,g is the episode reward of a placement p drawn from the policy network applied to netlist g.” [Section 4. Domain Transfer: Learning Better Chip Placements from Experience]); and
using the set of trajectories to calculate an update to parameters of the NN (Mirhoseini: “In Equation 3, the objective is to train a policy network πθ that maximizes the expected value (E) of the reward (Rp,g) over the policy network’s placement distribution. To optimize the parameters of the policy network, we use Proximal Policy Optimization (PPO) (Schulman et al., 2017) with a clipped objective as shown below: [Equation] where ˆEt represents the expected value at timestep t, rt is the ratio of the new policy and the old policy, and ˆAt is the estimated advantage at timestep t.” [Section 4.3. Policy Network Update: Training Parameters θ]).
Regarding Claim 8, Mirhoseini and Yang teach the method of Claim 1, further comprising:
receiving, after the training of the NN, a given preference and a given chip on which a plurality of macros are to be placed (Mirhoseini: “In our setting, at the initial state, s0, we have an empty chip canvas and an unplaced netlist.” [Section 3.2. Overview of Our Approach]; Yang: “In this paper, we propose a novel algorithm for learning a single policy network that is optimized over the entire space of preferences in a domain. This allows our trained model to produce the optimal policy for any user-specified preference.” [Section 1. Introduction]);
further training the NN with the given preference and a plurality of stochastically sampled trajectories on the given chip (Mirhoseini: “We can further optimize placement quality by finetuning the policy network. Doing so gives us the flexibility to either use the pre-trained weights (that have learned a rich representation of the input state) or further finetune these weights to optimize for the properties of a particular chip netlist.” [Section 4.1. A Supervised Approach to Enable Transfer Learning]; “Visualization of placements. On the left, zero-shot placements from the pre-trained policy and on the right, placements from the finetuned policy are shown. The zero-shot policy placements are generated at inference time on a previously unseen chip.” [Fig. 6]; Yang: “After learning, the agent is provided a new task, with either a) a preference ω specified by a human, or b) an unknown preference, where the agent has to automatically infer ω. Efficiently aligning ΠL(ω) with the preferred optimal policy is non-trivial since the CCS can be very large. In both cases, the agent is evaluated on how well it can adapt to tasks with unseen preferences.” [Section 3.2. Overview of Our Approach]); and
sampling a final trajectory using the further-trained NN to generate the completed macro placement (Mirhoseini: “The final states T 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).” [Section 3.2. Overview of Our Approach]).
Regarding Claim 9, Mirhoseini and Yang teach the method of Claim 1, wherein the objectives further include a distance to at least one of a positive anchor and a negative anchor, the positive anchor to attract the placement of a first subset of the macros and the negative anchor to repel the placement of a second subset of the macros (Mirhoseini: “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).” [Section 1. Introduction]; “To place standard cell clusters, we use an approach similar to classic force-directed methods. We represent the netlist as a system of springs that apply force to each node, according to the weight × distance formula, causing tightly connected nodes to be attracted to one another. We also introduce a repulsive force between overlapping nodes to reduce placement density. After applying all forces, we move nodes in the direction of the force vector. To reduce oscillations, we set a maximum distance for each move.” [Section 3.3.4. Standard Cell Placement]).
Claims 6-7 are rejected under 35 U.S.C. 103 as being unpatentable over Mirhoseini in view of Yang, as applied to Claim 1 above, in further view of Chen et al. (“A Two-Stage Multi-Objective Deep Reinforcement Learning Framework”, published 9/8/2020).
Regarding Claim 6, Mirhoseini and Yang teach the method of Claim 1, wherein generating the probability distribution of the action further comprises:
applying a mask to the probability distribution to produce a masked distribution over the chip, wherein the mask blocks off areas on the chip (Mirhoseini: “A feasible standard cell cluster placement should meet the following criterion: the density of placed items in each grid cell should not exceed a given target density threshold (maxdensity). We set this threshold to be 0.6 in our experiments. To meet this constraint, during each RL step, we calculate the current density mask, a binary m × n matrix that represents grid cells onto which we can place the center of the current node without violating the density threshold criteria. Before choosing an action from the policy network output, we first take the dot product of the mask and the policy network output and then take the argmax over feasible locations. This approach prevents the policy network from generating placements with overlapping macros or dense standard cell areas.” [Section 3.3.6. Density]; “For policy optimization purposes, we convert the canvas into a m × n grid. Thus, for any given state, the action space (or the output of the policy network) is the probability distribution of placements of the current macro over the m × ngrid. The action is the argmax of this probability distribution.” [Section 3.4. Action Representation]).
However, they fail to expressly disclose based on a deterministic policy, choosing the action with a highest probability according to the masked distribution.
In the same field of endeavor, Chen teaches based on a deterministic policy, choosing the action with a highest probability according to the masked distribution (Chen: “Firstly, the learned policies are tested deterministically. The agent always takes action with maximum probability. In this setting, there are ten Pareto optimal policies. Each optimal policy leads to one treasure location.” [Section 4.3 Problem 1: Deep Sea Treasure]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to have incorporated based on a deterministic policy, choosing the action with a highest probability according to the masked distribution, as taught by Chen to the method of Mirhoseini and Yang because both of these methods are directed towards multi-objective reinforcement learning. Deterministic and stochastic policies are well-known as the two basic types of action selection policies in reinforcement learning. In making this combination and selecting actions based on a deterministic policy, it would allow the method of Mirhoseini to perform evaluation in “only one episode” (Chen: [Section 4.3 Problem 1: Deep Sea Treasure]).
Regarding Claim 7, Mirhoseini, Yang, and Chen teach the method of Claim 6, wherein training the NN further comprises:
sampling a set of trajectories in an evaluation operation according to the deterministic policy (Chen: “Firstly, the learned policies are tested deterministically. The agent always takes action with maximum probability. In this setting, there are ten Pareto optimal policies. Each optimal policy leads to one treasure location.” [Section 4.3 Problem 1: Deep Sea Treasure]; “The initialized individual ai is evaluated by simulation and labeled by a fitness vector yi. Each element of yi represents the accumulated reward of the related objective. In every generation, each individual generates one offspring by sampling from the Gaussian distribution: ¯φi ∼ N(¯φi,σiCi), in which the mean and the covariance matrix are ¯φi and σiCi. New offsprings are evaluated by simulation and labeled with fitness vectors.” [Section 3.2 Multi-Objective Covariance Matrix Adaptation Evolution Strategy (MO-CMA-ES)]); and
calculating a final reward value from a plurality of reward values, each reward value calculated based on a final state of one of the trajectories (Mirhoseini: “Through repeated episodes (sequences of states, actions, and rewards), the policy network learns to take actions that will maximize cumulative reward. We use Proximal Policy Optimization (PPO) to update the parameters of the policy network, given the cumulative reward for each placement.” [Section 3.2. Overview of Our Approach]).
Claims 10-11 are rejected under 35 U.S.C. 103 as being unpatentable over Mirhoseini in view of Yang, as applied to Claim 1 above, in further view of Deb et al. (“Interactive Evolutionary Multi-Objective Optimization and Decision-Making using Reference Direction Method”, published 07/07/2007).
Regarding Claim 10, Mirhoseini and Yang teach the method of Claim 1, further comprising:
generating a set of placements by the NN to place a same set of macros on a given chip, wherein each placement is generated based on a different preference (Mirhoseini: “To create diverse placements for each netlist, we trained a vanilla policy network at various congestion weights (ranging from 0 to 1) and random seeds, and collected snapshots of each placement during the course of policy training.” [Section 4.1. A Supervised Approach to Enable Transfer Learning]; “We observe that if ω is fixed to a single value, this MOMDP collapses into a standard MDP. On the other hand, if we consider all possible returns from an MOMDP, we have a Pareto frontier F∗ := {ˆr |∃ˆr≥ ˆr}, where the return ˆr := tγtr(st,at). And for all possible preference in Ω, we define a convex coverage set (CCS) of the Pareto frontier as: [Equation] which contains all returns that provide the maximum cumulative utility.” [Section 2. Background]).
However, they fail to expressly disclose receiving an indication of a candidate placement among the set of placements, wherein the candidate placement is generated based on a candidate preference; modifying the candidate preference to generate p preferences; generating a subsequent set of p placements by the NN to place the same set of macros on the given chip; and repeating the receiving of the indication, the modifying of the candidate preference, and the generating of the subsequent set of p placements until a final placement is accepted.
In the same field of endeavor, Deb teaches receiving an indication of a candidate placement among the set of placements, wherein the candidate placement is generated based on a candidate preference (Deb: “Step 3: Find the most preferred solution qk in Qk using a utility function or by other means.” [Section 2. Reference Direction Method]);
modifying the candidate preference to generate p preferences (Deb: “Step 1: Specify another vector gk and determine the reference direction dk=gk-qk-1… Step 4: If qk−1 ̸ = qk, set k = k+1 and go to Step 1.” [Section 2. Reference Direction Method]);
generating a subsequent set of p placements by the NN to place the same set of macros on the given chip (Deb: “Step 2: Determine a set Qk of efficient solutions q which solve the following achievement scalarizing function s: [Equation 2]. The parameter t is increased from zero to infinity, w is a weighting vector and I is the set of indices of objectives having a nonzero weight value.” [Section 2. Reference Direction Method]); and
repeating the receiving of the indication, the modifying of the candidate preference, and the generating of the subsequent set of p placements until a final placement is accepted (Deb: “Step 4: If If qk−1 ̸ = qk,setk = k+1 and go to Step 1. Otherwise, check for optimality conditions (Kuhn-Tucker conditions or other optimality conditions) of the solution qk. If qk is optimal, terminate the procedure, else increment k and define a new reference direction and go to Step 2.” [Section 2. Reference Direction Method]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to have incorporated receiving an indication of a candidate placement among the set of placements, wherein the candidate placement is generated based on a candidate preference; modifying the candidate preference to generate p preferences; generating a subsequent set of p placements by the NN to place the same set of macros on the given chip; and repeating the receiving of the indication, the modifying of the candidate preference, and the generating of the subsequent set of p placements until a final placement is accepted, as taught by Deb to the method of Mirhoseini and Yang because both of these methods are directed towards multi-objective optimization in representing a Pareto front of optimal policies. In making this combination and generating multiple solutions based on modifications of a candidate preference to determine a final placement, it would allow the method of Mirhoseini and Yang to allow the user to “provide a tentative information about his/her preference”, provide “information about other solutions which are close to the preferred solution but may have interesting trade-off for the decision-maker to consider”, and “may help decipher common properties of such solutions, thereby providing salient information about desired solutions” (Deb: [Section 1. Introduction]).
Regarding Claim 11, Mirhoseini, Yang, and Deb teach the method of Claim 10, wherein modifying the candidate preference further comprises: modifying one or more vector elements of the candidate preference by respective one or more delta values, wherein each delta value is in a predetermined value range (Deb: “The first reference direction is chosen using q0 = znad and g1 = z∗. 25 equi-spaced points are chosen between q0 and g1 and the corresponding optimal solutions to the achievement scalarizing function is found simultaneously using RD-NSGA-II.” [Section 4.7 Car Side Impact Problem]; “Step 1: Specify another vector gk and determine the reference direction dk=gk-qk-1… Step 4: If qk−1 ̸ = qk, set k = k+1 and go to Step 1.” [Section 2. Reference Direction Method]).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Huang et al. (“Machine Learning for Electronic Design Automation: A Survey”) discusses various machine learning techniques in electronic design automation.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MEGAN E HWANG whose telephone number is (703)756-1377. The examiner can normally be reached Monday-Thursday 10:00AM-7:30PM ET.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Jennifer Welch can be reached at (571) 272-7212. 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.
/M.E.H./Examiner, Art Unit 2143
/JENNIFER N WELCH/Supervisory Patent Examiner, Art Unit 2143
Prosecution Insights