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 .
This is response to Application 18/315,904 filed on 05/11/2023. Claims 1-20 are pending in the office action.
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.
Claim(s) 1-2, 4, 6-12, 14, and 16-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Mirhoseini et al., Chip Placement with Deep Reinforcement Learning, April 22, 2020, pages 1-15 in view of Hsu et al., (U.S. Pub. 2016/0335386).
As per claims 1 and 11: Mirhoseini teaches a learning-based (Reinforcement Learning (RL) (i.e., a neural network), of chip (IC) placement, comprising:
generating, using the neural network, a probability distribution over locations on a grid and aspect ratios of a macro (Mirhoseini, page 3, col. 2, 3.2. Overview of Our Approach, state transition, “probability distribution over next state”; page 6, 3.3.6 Density, “max density” (aspect ratios); 3.4, Action representation, “the probability distribution of place of current macro over the m x n grid”), wherein the grid represents the chip canvas and is formed by rows and columns of grid cells (Mirhoseini, page 3, col. 2, 3.2. Overview of Our Approach, state and action, “chip canvas”; page 5, col. 1-2, 3.3.2 selection of grid row and columns, “discretize the 2D canvas into grid cells”);
generating action masks for respective ones of the aspect ratios to block out a subset of unoccupied grid cells based on design rules that optimize macro placement (Mirhoseini, page 3, col. 2, 3.2 Overview of Our Approach, action, “hard constraints on density or blockages (i.e., block out)”; page 4, col. 2, 3.3 Reward, “we treat density as a hard constraint, masking out actions (grid cell to place node onto) whose density exceeds the target density”; page 8, col. 2, 4.3 Policy network update: Training Parameters, for policy optimization, also see fig. 2, mask (action)).
generating a masked probability distribution (i.e., masked policy 128 x 128 x1) by applying the action masks on the probability distribution (Mirhoseini, fig. 2, mask policy by applying the action mask, the policy and value networks then output a probability distribution over available placement locations and an estimate of the expected reward for the current placement, respectively); and
selecting a location on the grid for placing the macro cluster with a chosen aspect ratio based on the masked probability distribution (Mirhoseini, page 5, 3.3.2 selection of grid rows and columns; 3.3.3 section of macro-order; page 6, col. 1-2, 3.3.6 Density, “disallowing the policy network from placing macros in locations which would cause density to exceed the target).
Mirhoseini teach the RL agent (i.e., the policy network) placing macro one at a time. Once all macros are placed, the standard cells are placed using a force-directed method (Mirhoseini, page 4, col. 1, and fig. 1), but Mirhoseini, does not teach clustering the macros into a plurality of macro clusters.
Hsu teaches clustering the macros into a plurality of macro clusters (macro grouping procedure) (‘386, par. [0027] also see fig. 2, S220 and fig. 3A-3B, macro group MG1-MG8) and placing macro block into a selected candidate placement based on congression (‘386, fig. 1-2).
It would have been obvious to one of ordinary skill in the art at the time of the effective filling date of claimed invention to combine Hsu and Mirhoseini using Hsu’s macro group placement to modify Mirhosein’s placement method by placing macro one at the time, Hsu’s macro placement of all the macro blocks can provide an optimum blank space between the macro blocks to optimize routability and satisfy timing constraints for the IC and reducing cost of a place and route (APR) procedure as well as execution time (‘386, par. [0027]).
As per claims 2 and 12: Mirhoseini and Hsu teach wherein generating the action masks further comprises: detecting edge grid cells in a region of the grid, wherein each grid cell in the region is valid for placement (Mirhoseini, page 6, co. 1, “edge feature” and col. 2, “grid size”); and
removing non-edge grid cells from candidate grid cells to generate updated candidate grid cells (Mirhoseini, page 7, col. 2, edge update and edge embeddings, page 8, col. 1, removed the predict layer and then used it as the encoder component of the policy network).
As per claims 4 and 14: Mirhoseini and Hsu teach further comprising: clustering the macros having a same width and height and in a same hardware hierarchy group into a macro cluster (‘386, par. [0027] same hierarchy will be divide in the same macro group).
As per claims 6 and 16: Mirhoseini and Hsu teach wherein the neural network is a reinforcement learning (RL) neural network that receives a reward for placement of the macros on the grid (Mirhoseini, the abstract, page 3, 3. Method, 3.1., 3.1 Problem Statement), and wherein the reward is a measurement of wirelength and congestion of the placement (Mirhoseini, page 4, fig.1 and col. 2, 3.3 Reward, wirelength and congestion).
As per claims 7 and 17: Mirhoseini and Hsu teach further comprising: after placement of all of the macro clusters on the grid, applying a convex refiner to overlapping macro clusters to minimize a total macro displacement while satisfying a non-overlapping constraint for all of the macro clusters (Mirhoseini, page 3, col. 1, to define convex approximation of those functions and page 11, col. 2, “convex function).
As per claims 8 and 18: Mirhoseini and Hsu teach further comprising: after placement of all of the macro clusters on the grid, applying a rule-based refiner to minimize wasted areas between adjacent macro clusters and between a chip canvas boundary and each macro cluster (‘386, par. [0029], macro block exceeds boundary of the rectangle to be remove and determined the rectangle with the remaining macro block).
As per claims 9 and 19: Mirhoseini and Hsu teach further comprising: after placement of all of the macro clusters on the grid, applying a rule-based refiner to reserve channel space for each macro cluster (‘386, par. [0029], adjusted/refiner channel width between macro block).
As per claims 10 and 20: Mirhoseini and Hsu teach further comprising: after placement of all of the macro clusters on the grid (‘386, fig. 5A-5H), applying a rule-based refiner to enforce requirements of foundry process technologies with respect to spacing between adjacent macro clusters and spacing between a chip canvas boundary and the macro clusters (Mirhoseini, page 5, col .2, 3.3.5 routing congestion, The routed net occupies a certain amount of available routing resources (determined by the underlying semiconductor fabrication technology) for each grid cell which it passes through).
Allowable Subject Matter
Claims 3, 5, 13, and 15 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
The following is a statement of reasons for the indication of allowable subject matter:
As per claims 3 and 13: wherein generating the action masks further comprises: detecting one or more dead-space grid cells among the updated candidate grid cells, wherein placement of the macro cluster on any of the dead-space grid cells causes fragmentation of usable placement space in the grid; removing the one or more dead-space grid cells from the updated candidate grid cells to generate target grid cells; and generating an action mask that blocks out all grid cells in the grid except the target grid cells.
As per claims 5 and 15: wherein each macro is a leaf node in a tree structure that describes a hierarchical hardware design, the tree structure is partitioned into a plurality of hardware hierarchy groups with the number of macros in each hardware hierarchy group subject to an upper limit.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NGHIA M DOAN whose telephone number is (571)272-5973. The examiner can normally be reached Mon - Fri 7:00 AM - 5:00 PM.
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.
NGHIA M. DOAN
Primary Examiner
Art Unit 2851
/NGHIA M DOAN/Primary Examiner, Art Unit 2851