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 .
Specification
The disclosure is objected to because of the following informalities:
“S201” (paragraph [0032], line 16) must be amended to --S202-- as per FIG. 3; and
--S505-- must be inserted into paragraph [0051] as per FIG. 8.
Appropriate correction is required.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-10 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
As per claim 1, the boundaries of claim scope are not clear. For example, there does not appear to be antecedent basis for “placed chips” [line 3], thus, what is intended by “status” and “generating pix-level masks (there)from” is not particularly clear. Similarly, there does not appear to be antecedent basis for “features” [line 2], “the next two chips to be placed” [lines 3-4], “local and global features” [line 5], “placement position” [line 7], “merged features” [line 7], “congestion threshold” [7], thus rendering the generating, extracting and selecting steps incomplete, vague and indefinite. In other words, is the claim intended for chip placement, placement of features of the chip, or otherwise? How are features (line 2) related to the chip, placed chips, next two chips? What are local and global features, how are they related to the chip, placed chips, next two chips, the masks? What is the placement position in reference to, the chip, features, placed chips, etc.? Thus, the claim can be considered rather broad, at the very least the claim is vague and indefinite for not particularly pointing out and distinctly claiming a chip placement method. The language of the dependent claims similarly follow. Therefore, the claims are rejected as being indefinite.
The following rejections are based on the Examiner’s best interpretation of the claims in view of the indefiniteness identified above.
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 7-10 are rejected under 35 U.S.C. 103 as being unpatentable over Ren [US 2022/0292335 A1].
As per claim 1, Ren teaches a broadest reasonable interpretation of a chip placement method, comprising the steps of:
determining the order of placement by features of the chip [0063 ordering, 0075 specify the placement order of pins],
generating pix-level masks [0102 grid space of the stick layout representation, 0038 stick diagrams constrain the placement of devices, locations for pins] from the status of placed chips and the next two chips to be placed [0047-0053 a given state, reward, two is considered a design choice],
extracting local and global features [0002 dependent on technology node, 0058 features are collected, 0160-0161 Cooperative Groups, enables programmers to define groups, within local context, and global synchronization] from the masks by convolutional neural networks [FIG. 11], and,
selecting the placement position by merged features and congestion threshold [0049 reward, congestion, pin placement optimality, 0075 optimize a scoring function].
Thus, given the rejection under 35 U.S.C. 112(b), 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 because an RL placer generates placements with accuracy on par with simulated annealing algorithms [0042].
As per claim 2, the method of claim 1, wherein determining the order of placement by the features of the chip comprises:
extracting the number of pins, the area and the number of chips connected to each chip [0002 layouts may be constructed from a very large number of instances to improve area efficiency, 0003 the design goal is to minimize cell area, 0038 locations are inferred intrinsically, 0058-0062 features are collected, design choice, 0065/0075 scoring function is weighted];
computing scores by linear weighting of extracted features [0051-0057 linear network and weighted average]; and
achieving placement order by sorting the scores [0042 RL placer, which pin of the devices to place in the next step, 0049 reinforcement learning reward function, reward value(s) applied as feedback to further train, pin placement optimality may also be considered in the computation of the reward, 0066-0075].
As per claim 3, the method of claim 2, wherein computing scores by linear weighting of extracted features comprises:
acquiring the hyperparameter for each weight of each feature [hyperparameters are inherent in machine learning]; and
calculating the weighted sum as score for each chip [0065/0075 scoring function is weighted sum].
As per claim 4, the method of claim 1, wherein generating pix-level masks from the status of placed modules and the next two modules to be placed comprises:
generating two position masks from the features of placed chips and the next two chips to be placed [0102 grid space of the stick layout representation, 0038 stick diagrams constrain the placement of devices, locations for pins, 0039 double patterning, 0047-0053 a given state, reward, two is considered a design choice, FIG. 11];
generating two wire masks from the features of placed modules and the next two modules to be placed [0102 grid space of the stick layout representation, 0038 stick diagrams constrain the placement of devices, 0039 double patterning, locations for pins, 0047-0053 a given state, reward, two is considered a design choice, FIG. 11]; and
generating one view mask from the features of placed modules [0102 grid space of the stick layout representation, 0038 stick diagrams constrain the placement of devices, locations for pins, 0047-0053 a given state, reward; FIG. 11].
As per claim 5, the method of claim 4, wherein generating two position masks from the features of placed chips and the next two chips to be place comprises:
acquiring the size and position of placed chips [0047-0053 a given state, reward, two is considered a design choice];
acquiring the size of the next two chips to be placed [0047-0053 a given state, reward, two is considered a design choice];
calculating all possible positions of the chip that will not overlap with the already placed chips with the next two chips to be placed separately [0102 grid space of the stick layout representation, 0038 stick diagrams constrain the placement of devices, locations for pins, 0039 double patterning, 0047-0053 a given state, reward, two is considered a design choice, FIG. 11];
marking all possible positions with 1 and other positions with 0 in the position masks [0043 one-hot encoded].
As per claim 7, the method of claim 4, wherein generating one view mask from the features of placed chips comprises:
acquiring the size and position of placed chips [0102 grid space of the stick layout representation, 0038 stick diagrams constrain the placement of devices, locations for pins, 0047-0053 a given state, reward; FIG. 11];
computing the number of occupied matrix elements based on the size of the chip [0102 grid space of the stick layout representation, 0038 stick diagrams constrain the placement of devices, locations for pins, 0047-0053 a given state, reward; FIG. 11, 0165-0166 matrix operations]; and
marking all occupied elements with 1 and other elements with 0 in the view mask [0043 one-hot encoded].
As per claim 8, the method of claim 1, wherein extracting local and global features from masks by convolutional neural networks comprises:
extracting local features from masks by convolutional neural networks with small kernels [0002 dependent on technology node, 0052-0053 kernel-based convolutional operator, 0058 features are collected, 0160-0161 Cooperative Groups, enables programmers to define groups, within local context, and global synchronization];
extracting global features from masks by convolutional neural networks with large kernels [0002 dependent on technology node, 0052-0053 kernel-based convolutional operator, 0058 features are collected, 0160-0161 Cooperative Groups, enables programmers to define groups, within local context, and global synchronization]; and
merging local and global features by convolutional neural networks [0002 dependent on technology node, 0058 features are collected, 0160-0161 Cooperative Groups, enables programmers to define groups, within local context, and global synchronization, FIG. 11].
As per claim 9, the method of claim 8, wherein merging local and global features by convolutional neural networks comprises:
generating two position masks from the features of placed chips and the next two chips to be placed [0102 grid space of the stick layout representation, 0038 stick diagrams constrain the placement of devices, locations for pins, 0039 double patterning, 0047-0053 a given state, reward, two is considered a design choice, FIG. 11];
acquiring the local and global feature maps respectively [0160-0161 Cooperative Groups, enables programmers to define groups, within local context, and global synchronization, FIG. 11];
merging features by convolutional neural networks with a 1x1 kernel from a concatenated feature map [0043, 0052-0053 kernel-based convolutional operator, FIG. 11];
removing all impossible positions according to the corresponding position mask [0049 reward, congestion, pin placement optimality, 0075 optimize a scoring function]; and
computing the probability action matrix by a softmax layer [Softmax layer 1116 in FIG. 11].
As per claim 10, the method of claim 1, wherein selecting the placement position by merged features and congestion threshold comprises:
sampling one place position from the probability matrix with the corresponding probability [0072 probability distribution is sampled, 0165-0166 matrix operations, FIG. 11];
computing the congestion after taking this placement action at the position [0049 reward, congestion, 0075 congestion estimation];
re-sampling several place positions and computing the corresponding congestion if the congestion is greater than the congestion threshold [0099-0102 search for minimum routes, characterized by its observation space, action space, internal states, rewards, and done condition];
selecting the position that has the minimum wirelength while meeting congestion requirements [0077 generates device placements and pin assignments, to identify minimum routes]; and
placing the chip at the selected position and moving to the next placement step [0049 reward, congestion, pin placement optimality, 0075 optimize a scoring function].
Claim 6 is rejected under 35 U.S.C. 103 as being unpatentable over Ren as applied to claim 1 above, and further in view of Z. Guo et al. [“Ultrafast CPU/GPU Kernels for Density Accumulation in Placement”].
As per claim 6, Ren teaches the method of claim 4, wherein generating two wire masks from the features of placed chips and the next two chips to be placed comprises:
acquiring the size and position of placed chips [0047-0053 a given state, reward];
acquiring the size of the next two chips to be placed [0047-0053 a given state, reward, two is considered a design choice];
computing the wirelength increase when placing a chip in different positions [0049 reward, congestion, pin placement optimality, 0075 optimize a scoring function]; and
filling the wirelength increase in corresponding position of wire masks [0049 reward, congestion, pin placement optimality, 0075 optimize a scoring function].
However, Ren does not teach bounding box. Z. Guo et al. teach a chip placement method comprising acquiring each bounding box range for pins belonging to the same wire [Abstract, section II. Bounding box, Fig. 1 density, Fig, 5 density collections].
Thus, given the rejection under 35 U.S.C. 112(b), 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 because compared to kernels used in state-of-the-art placers, we achieved up to 22x speed-up on CPU and 64x on GPU [section V. Conclusion].
Claims 1-5 and 7-10 are rejected under 35 U.S.C. 103 as being unpatentable over R. Cheng et al. [“On Joint Learning for Solving Placement and Routing in Chip Design”].
As per claim 1, R. Cheng et al. teach a chip placement method, comprising the steps of:
determining the order of placement by features of the chip [page 2 DRL agent places sequentially, sequentially arranged],
generating pix-level masks [Figure 1 (a) chip canvas] from the status of placed chips and the next two chips to be placed [Figure 2 as indicated by (3), page 4 Reward policy network learns to maximize the expected reward from placing prior chips and improves placement quality over episodes],
extracting local and global features from the masks by convolutional neural networks [page 1 neural network, global embedding and node level embedding, page 5 Figure 3(a), both global embedding from CNN and detailed node embedding from GNN, multi-view embedding model is able to synthetically explore global and node level information], and,
selecting the placement position by merged features and congestion threshold [page 1, section 1 Introduction, objective of placement is to minimize PPA without violating constraints such as density and congestion, page 4 Reward policy network learns to maximize the expected reward from placing prior chips and improves placement quality over episode, which is updated, section 3.3 cost functions with both wirelength and congestion].
Thus, given the rejection under 35 U.S.C. 112(b), 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 because the reinforcement learning paradigm involves a multi-view embedding model to encode both global graph level and local node level information [Abstract].
As per claim 2, the method of claim 1, wherein determining the order of placement by the features of the chip comprises:
extracting the number of pins, the area and the number of chips connected to each chip [section 1 Introduction hypergraph H = (V,E), chip canvas, global embedding and node level embedding information, Figure 1(a) broadly indicates pins, netlist];
computing scores by linear weighting of extracted features [section 3.3 cost functions, hyperparameter that weights the relative importance according to the settings of a given chip]; and
achieving placement order by sorting the scores [section 3.3 P denotes the placement solution].
As per claim 3, the method of claim 2, wherein computing scores by linear weighting of extracted features comprises:
acquiring the hyperparameter for each weight of each feature [section 3.3 hyperparameter that weights the relative importance according to the settings of a given chip]; and
calculating the weighted sum as score for each chip [section 3.3 cost functions, weights the relative importance according to the settings of a given chip].
As per claim 4, the method of claim 1, wherein generating pix-level masks from the status of placed modules and the next two modules to be placed comprises:
generating two position masks from the features of placed chips and the next two chips to be placed [Figure 1 chip canvas, Figure 2(a), Figure 3, two is a design choice];
generating two wire masks from the features of placed modules and the next two modules to be placed [Figure 1 chip canvas, Figure 2(b), Figure 3, two is a design choice]; and
generating one view mask from the features of placed modules [Figure 6 visualization].
As per claim 5, the method of claim 4, wherein generating two position masks from the features of placed chips and the next two chips to be place comprises:
acquiring the size and position of placed chips [section 3.2 size n x n, page 4 Reward policy network learns to maximize the expected reward from placing prior chips];
acquiring the size of the next two chips to be placed [page 4 Reward policy network learns to maximize the expected reward from placing prior chips and improves placement quality over episode, which is updated];
calculating all possible positions of the chip that will not overlap with the already placed chips with the next two chips to be placed separately [page 4 Reward policy network learns to maximize the expected reward from placing prior chips and improves placement quality over episode, which is updated];
marking all possible positions with 1 and other positions with 0 in the position masks [page 4 State paragraph we model the chip canvas as a binary image].
As per claim 7, the method of claim 4, wherein generating one view mask from the features of placed chips comprises:
acquiring the size and position of placed chips [section 3.2 size n x n, page 4 Reward policy network learns to maximize the expected reward from placing prior chips];
computing the number of occupied matrix elements based on the size of the chip [section 3 State binary image 1 denotes position has been occupied, Action n x n canvas]; and
marking all occupied elements with 1 and other elements with 0 in the view mask [page 4 State paragraph we model the chip canvas as a binary image].
As per claim 8, the method of claim 1, wherein extracting local and global features from masks by convolutional neural networks comprises:
extracting local features from masks by convolutional neural networks with small kernels [page 1 neural network, node level embedding, page 5 Figure 3(a), detailed node embedding from GNN, multi-view embedding model is able to synthetically explore global and node level information];
extracting global features from masks by convolutional neural networks with large kernels [page 1 neural network, global embedding, page 5 Figure 3(a), global embedding from CNN, multi-view embedding model is able to synthetically explore global and node level information]; and
merging local and global features by convolutional neural networks [page 1 neural network, global embedding and node level embedding, page 5 Figure 3(a), both global embedding from CNN and detailed node embedding from GNN, multi-view embedding model is able to synthetically explore global and node level information].
As per claim 9, the method of claim 8, wherein merging local and global features by convolutional neural networks comprises:
generating two position masks from the features of placed chips and the next two chips to be placed [Figure 1 chip canvas, Figure 2(a), Figure 3, two is a design choice];
acquiring the local and global feature maps respectively [page 1 neural network, global embedding and node level embedding, page 5 Figure 3(a), both global embedding from CNN and detailed node embedding from GNN, multi-view embedding model is able to synthetically explore global and node level information];
merging features by convolutional neural networks with a 1x1 kernel from a concatenated feature map [section 3.2 both global and detailed node embeddings are fused to generate a probability distribution over actions];
removing all impossible positions according to the corresponding position mask [section 3.2 multi-view embedding model is able to explore global and node level information, page 4 Reward policy network learns to maximize the expected reward from placing prior chips and improves placement quality over episode, which is updated]; and
computing the probability action matrix by a softmax layer [softmax is inherent to a neural network for the final layer, Figure 2 final state, Figure 3].
As per claim 10, the method of claim 1, wherein selecting the placement position by merged features and congestion threshold comprises:
sampling one place position from the probability matrix with the corresponding probability [section 3.3.2 in each time step];
computing the congestion after taking this placement action at the position [section 3.3 congestions];
re-sampling several place positions and computing the corresponding congestion if the congestion is greater than the congestion threshold [section 4.3 RL agent generates intermediate macro placement];
selecting the position that has the minimum wirelength while meeting congestion requirements [section 3.3 cost functions with both wirelength and congestion]; and
placing the chip at the selected position and moving to the next placement step [section 4.3 gradient-based optimization placer to obtain complete placement solution].
Claim 6 is rejected under 35 U.S.C. 103 as being unpatentable over R. Cheng et al. as applied to claim 1 above, and further in view of Z. Guo et al. [“Ultrafast CPU/GPU Kernels for Density Accumulation in Placement”].
As per claim 6, R. Cheng et al. teach the method of claim 4, wherein generating two wire masks from the features of placed chips and the next two chips to be placed comprises:
acquiring the size and position of placed chips [section 3.2 size n x n, page 4 Reward policy network learns to maximize the expected reward from placing prior chips];
acquiring the size of the next two chips to be placed [page 4 Reward policy network learns to maximize the expected reward from placing prior chips and improves placement quality over episode, which is updated];
acquiring half-perimeter wirelength [page 3 Wirelength section]
computing the wirelength increase when placing a chip in different positions [section 3.3 Wirelength]; and
filling the wirelength increase in corresponding position of wire masks [section 3.3 cost function with wirelength and congestion].
However, R. Cheng et al. do not teach bounding box. Z. Guo et al. teach a chip placement method comprising acquiring each bounding box range for pins belonging to the same wire [].
Thus, given the rejection under 35 U.S.C. 112(b), 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 because compared to kernels used in state-of-the-art placers, we achieved up to 22x speed-up on CPU and 64x on GPU [section V. Conclusion].
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. See, for example, Y.-H. Huang et al. [“Routability-Driven Macro Placement with Embedded CNN-Based Prediction Model”] at Abstract, Figs. 2-6, Section II. A. and B., Section III.A.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to LEIGH M GARBOWSKI whose telephone number is (571)272-1893. The examiner can normally be reached M-F 9-5 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, Jack Chiang can be reached at 571-272-7483. 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.
/LEIGH M GARBOWSKI/Primary Examiner, Art Unit 2851
Prosecution Insights