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 .
Specification
The disclosure is objected to because of the following informalities:
(Text within parentheses is either a missing or a corrected information to character(s) in bold.)
[0021 An(A) historical device placement may also be collected from a design library, … A set of devices and an(a) historical device placement for the set of devices can then be extracted from the GDSII files using this correspondence.
[0022] As discussed above, each data point in the library built in step 102 may comprise a set of devices for a custom design and an(a) historical device placement that has been generated for the set of devices.
[0023] In one example, an(a) historical device placement corresponding to a set of devices for a custom layout may be represented by an identifier that uniquely identifies the multi-row left-to-right relative placement of the set of devices.
Appropriate correction is required.
Claim Objections
Claim 5 objected to because of the following informalities:
(Text within parentheses is either a missing or a corrected information to character(s) in bold.)
The method of claim 1, wherein the machine learning model comprises a sequential neural network that has been trained on a plurality of data points, and wherein each of the data points represents an(a) historical device placement from the library of historical device placements and an(a) historical set of devices corresponding the historical device placement from the library of historical device placements.
Appropriate correction is required.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-8, and 11-20 are rejected under 35 U.S.C. 102(a(1) and (a)(2) as being anticipated by Regis Colwell et. al. (US 10628546 B1) hereinafter Colwell.
Regarding claim 1
Colwell discloses
A method comprising
acquiring, by a processing device, an input, where the input specifies a set of devices to be placed and routed for a circuit design
(Colwell, col. 4 line 67 – co. 5, line 3 “The layout recommender 109 receives schematics/layouts 111 from the user, and will use the predictors to generate a set of layout recommendations.”)
(Colwell, col. 3, line 7-8 “FIG. 6 illustrates an example pair of devices to place in a layout.”)
(Colwell, col. 21, line 29-36 “A computer program product embodied on a non-transitory computer readable medium, the computer readable medium having stored thereon a sequence of instructions which, when executed by a processor cause a set of acts, the set of acts comprising: loading electronic designs, the electronic designs comprising historical circuit schematics and corresponding historical physical layouts;”)
(Colwell, col. 20, line 40-48 “A method, comprising: loading electronic designs, the electronic designs comprising historical circuit schematics and corresponding historical physical layouts; implementing a machine learning process, wherein the machine learning process generates a plurality of different trained predictors from features and labels in the electronic designs, the plurality of different trained predictors for generating predictions to a plurality of routing steps,”)
executing, by the processing device and in response to the input, a machine learning model to compute a probability distribution function over a library of historical device placements that estimates a suitability of each historical device placement in the library of historical device placements for placing and routing the set of devices specified in the input
(Colwell, col. 20, lines 18-24 “Computer system 1400 may transmit and receive messages, data, and instructions, including program, e.g., application code, through communication link 1415 and communication interface 1414. Received program code may be executed by processor 1407 as it is received, and/or stored in storage device 1410, or other non-volatile storage for later execution.”)
(Colwell, col. 4, lines 22-24 “Therefore, the inventive system includes a training system that is employed to generate one or more Machine Learning (ML) models 106.”)
(Colwell, col. 4, lines 32-35 “The training data may include, for example, historical designs that have already been created for the placement of objects and instances in previous layouts.”)
(Colwell, col. 18, lines 25-34 “As shown in FIG. 8, machine learning is employed to guide the user through building of placements that is similar to placements that the system was trained on. At 802, a determination is made of the first (e.g., bottom row) in the design. This can be implemented by identifying the most probable row from devices connected to ground, e.g., using the appropriate decision module from FIG. 9. At 804, a determination is made whether the chosen row is acceptable to the user. If not, then at 806, another row is chosen and the process loops back to 504.”)
(Colwell, col. 18, lines 35-42 “At 808, a row is placed at the next layout position, e.g., starting from the bottom of the layout. Next, at 810, a probable first-level routing is identified for the row. The appropriate decision module(s) from FIG. 9 can be employed to implement these steps. At 812, a determination is made whether the identified routing is acceptable to the user. If not, then at 814, the next most probable routing is chosen and the process loops back to 812.”)
(Colwell, col. 6, lines 12-19 “The advantage of the FIG. 1A approach over the FIG. 1B approach is that the models are tuned for the individual user from the very beginning, so that more accurate predictions may be generated right away for the user of interest. The disadvantage with this approach is the challenge of being able to derive enough data from the model if the user does not have a sufficient amount of historical database of past designs to generate an accurate model.”)
and providing, by the processing device, graphical representations for a defined number of historical device placements from the library of historical device placements that are estimated to be suited for placing and routing the set of devices based on the probability distribution function.
(Colwell, col. 3, lines 40-44 “FIG. 1A illustrates an example system 100a which may be employed in some embodiments of the invention. System 100a includes one or more users that interface with and operate a computing system to control and/or interact with system 100a using a computing station 101.”)
(Colwell, col. 5, lines 4-9 “Various interfaces may be provided to control the operation of the system 100a. For example, a training interface 113 may be employed to control the operations of the training process, e.g., for selection and/or validation of training data. The layout interface 115 may be employed to control the operations of generating a recommended layout.”)
(Colwell, col. 6, lines 12-19 “The advantage of the FIG. 1A approach over the FIG. 1B approach is that the models are tuned for the individual user from the very beginning, so that more accurate predictions may be generated right away for the user of interest. The disadvantage with this approach is the challenge of being able to derive enough data from the model if the user does not have a sufficient amount of historical database of past designs to generate an accurate model.”)
(Colwell, col. 18, lines 25-34 “As shown in FIG. 8, machine learning is employed to guide the user through building of placements that is similar to placements that the system was trained on. At 802, a determination is made of the first (e.g., bottom row) in the design. This can be implemented by identifying the most probable row from devices connected to ground, e.g., using the appropriate decision module from FIG. 9. At 804, a determination is made whether the chosen row is acceptable to the user. If not, then at 806, another row is chosen and the process loops back to 504.”)
(Colwell, col. 18, lines 35-42 “At 808, a row is placed at the next layout position, e.g., starting from the bottom of the layout. Next, at 810, a probable first-level routing is identified for the row. The appropriate decision module(s) from FIG. 9 can be employed to implement these steps. At 812, a determination is made whether the identified routing is acceptable to the user. If not, then at 814, the next most probable routing is chosen and the process loops back to 812.”)
Regarding claim 2
Colwell teaches all aspects of claim 1 as disclosed above and further discloses
The method of claim 1, where the input comprises a vector, and the vector concatenates, for each device in the set of devices to be placed and routed: a tuple of numbers representing values of attributes of the each device and a numeric identifier of a unique connectivity graph that represents a connectivity of the each device.
(Colwell, col. 9, lines 16-24 “In some embodiments, a row region may be created and stored as an object (e.g., a physical object) that is associated with, for example, its identifier, the extent of the placement region or placement and route region, etc. In some other embodiments, a row region may be created and stored as a reference that is also associated with the same information as does the object. The object or reference of a row region may be stored in a data structure (e.g., a list, a table, a database table, etc.) for subsequent reuse.”)
(Colwell, col. 13, lines 42-49 “The process begins at 400, which identifies that the disclosed processing occurs for each layout to be trained upon. At 402, consideration is made of geometry for the layout. One or more electronic design databases may be accessed to retrieve the layout information, which include for example, geometric information regarding shapes for the objects placed onto a layout to implement a given electronic design.”)
(Colwell, col. 13, lines 22-31 “Embodiments of the present invention solve these problems by using domain knowledge and information found in the database storing that placement to extract the active devices in the circuit design. Then, each layout device can be associated with a schematic device. Other information can also be used, such as connectivity found in the full schematic. Since the database storing the design information already has much information in addition to the final layout, this information can be used to construct features and labels for the machine learning problem.”)
(Colwell, col. 14, lines 42-50 “At 424, associations between devices in the layout and schematic are used to augment the information with schematic information. Examples of feature information that may be extracted include the schematic position of the associated schematic device or the connectivity between the devices. Labels are extracted from the schematic, such as which devices are in proximity to each other in the schematic (e.g., to compare against device proximity in the layouts.”)
(Colwell, col. 16, lines 6-13 “In the training phase, at 702, features are extracted from each pair of devices. At 704, labels are also extracted for each pair of devices. In some embodiments, the following features extracted from the schematic data: (a) Connectivity; (b) Schematic position; (c) Device size; (d) Orientation; and/or (e) Device type. The specific steps to extract the features were described in the previous sections of this disclosure.”)
Regarding claim 3
Colwell teaches all aspects of claim 2 as disclosed above and further discloses
The method of claim 2, wherein the attributes comprise at least one of: whether the each device is an n-type metal oxide semiconductor device or a p-type metal oxide semiconductor device, a total channel width of the each device, a channel length of the each device, a number of fingers in the each device, a multiplier for the each device, or a number of vector bits in the each device.
(Colwell, col. 16, lines 6-13 “In the training phase, at 702, features are extracted from each pair of devices. At 704, labels are also extracted for each pair of devices. In some embodiments, the following features extracted from the schematic data: (a) Connectivity; (b) Schematic position; (c) Device size; (d) Orientation; and/or (e) Device type. The specific steps to extract the features were described in the previous sections of this disclosure.”)
(Colwell, col. 12, lines 19-25 “In this illustrated example, the NMOS (N-type Metal-Oxide-Semiconductor) device 310 in row 308 is shown to be in the permissible orientation of R0 (rotation by zero degree); and the PMOS (P-type Metal-Oxide-Semiconductor) device 320 in row 306 is shown to be in the permissible orientation of R270 (MY—mirrored around the Y axis).).”)
(Colwell, col. 15, lines 8-13 “Examples of individual instance features that may be extracted include: (a) name, (b) row (label), (c) columns (label), (d) numFins, (e) numFingers, (f) length, (g) Schematic Position, (h) Schematic orientation, and/or (i) device type. Row labels may be determined by analyzing completed layouts in the design database.”)
(Colwell, col. 10, line 60 – col. 11, line 2 “A plurality of characteristics, attributes, or configurations may be identified for the row region from the row templated identified or created. These characteristics, attributes, or configurations may include one or more of, for example, the number of rows in the row template, the reference grids, the positive or negative reference X grid offset, the positive or negative reference Y grid offset, the height of a row in the row template, one or more allowed types of circuit components or devices for a row in the row template, or one or more permissible orientations.”)
It 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 to consider all relevant data related to the device for optimum layout placement and routing.
Regarding claim 4
Colwell teaches all aspects of claim 2 as disclosed above and further discloses
The method of claim 2, wherein the vector is automatically constructed by the processing device when the processing device detects that a layout tool has been started on the set of devices and that the set of devices has not yet been placed or routed.
(Colwell, col. 6, lines 20-26 “The advantage of the FIG. 1B approach over the FIG. 1A approach is that an EDA provider of the layout tool can use a generic database of designs to provide a “starting point” for the training process for different users—even without gaining any access to the design trade secrets of its customers or even if the user does not have any/enough historical data that can be used.”)
(Colwell, col. 3, lines 3-6 “FIG. 4 shows an example flow chart for extracting features and labels from existing design data. FIG. 5 illustrates an example pair of devices for which features information is extracted.”)
(Colwell, col. 7, lines 16-19 “At 202, a plurality of features are extracted from design(s), where variable selection and/or attribute selection is performed. This step is performed to select the relevant set of features that are identified for model construction.”)
(Colwell, col. 9, lines 3-6 “An object may be created and stored in a data structure (e.g., a database) for the placement region or the place and route boundary as a “row region” in some embodiments.”)
(Colwell, col. 13, lines 37-41 “The user input includes a list of completed layouts to extract information from, where in some embodiments this list is the only user input that is required. Each layout is visited, active devices located, and labels and features are extracted.”)
(Colwell, col. 15, lines 8-12 “Examples of individual instance features that may be extracted include: (a) name, (b) row (label), (c) columns (label), (d) numFins, (e) numFingers, (f) length, (g) Schematic Position, (h) Schematic orientation, and/or (i) device type.”)
(Colwell, col. 16, lines 8-11 “In some embodiments, the following features extracted from the schematic data: (a) Connectivity; (b) Schematic position; (c) Device size; (d) Orientation; and/or (e) Device type.”)
(Colwell, col. 18, lines 15-20 “Module 930 pertains to routing decisions for a row, where at 932 the module 930 receives features of a row of devices, and at 934 determines configuration information for connecting devices in the row. This decision module inputs features of the current row and outputs a most probable routing given the history the system was trained on.”)
(Colwell, col. 18, lines 46-52 “The process then makes a determination, at 818, whether there are any additional devices to place in the layout. If so, then at 820, the next most probable row is selected, e.g., for devices “above” the previous row. The process then loops back to 804 and continues as described above. However, if there are no further devices to process, then the process ends at 822.”)
Regarding claim 5
Colwell teaches all aspects of claim 1 as disclosed above and further discloses
The method of claim 1, wherein the machine learning model comprises a sequential neural network that has been trained on a plurality of data points, and wherein each of the data points represents an historical device placement from the library of historical device placements and an historical set of devices corresponding the historical device placement from the library of historical device placements.
(Colwell, col. 4, lines 11-14 “In the approach of FIG. 1A, the individuated predictors are formed by having each user utilize that user's own historical set of designs to form individualized models for learning purposes. In effect, the historical design data 103 for user A will be used to generate a first individually trained model 106 for user A, while the historical design data for user B will be used to generate a second (separate) model for user B.”)
(Colwell, col. 4, lines 22-29 “Therefore, the inventive system includes a training system that is employed to generate one or more Machine Learning (ML) models 106. These ML models 106 pertain to various aspects of EDA design activities based at least on part upon existing schematics and layouts 103. Any suitable type of training may be applied to generate models 106. For example, “supervised training” is a type of ML training approach that infers a function from labeled training data.”)
(Colwell, col. 4, lines 32-38 “The training data may include, for example, historical designs that have already been created for the placement of objects and instances in previous layouts. Examples of such objects/instances include, for example, individual devices, device chains, multi-row groups of devices (e.g., a FigGroup/Modgen), custom cells, I/O pins, filler cells, and/or standard cells. A FigGroup is a grouping of circuit components used within certain applications, such as the Open Access database.”)
(Colwell, col. 5, lines 18-23 “The general idea is that in the approach of FIG. 1B, a common set of historical schematics/layouts 108 are employed for multiple users to generate a generic set of partially-trained models 169 that can then be used by the multiple different users to generate fully-trained models that are specific to each of the individual users.”)
(Colwell, col. 7, lines 31-34 “At 204, labels may be extracted from the existing designs. The models are trained by a combination of the training set and the training labels, where the labels often correlate to data for which a target answer is already known.”)
(Colwell, col. 17, lines 36-40 “This approach is particularly suitable if the amount of data is not large enough to apply sophisticated models such as deep learning, but where simple models such as logistic regression often cannot express important concepts adequately.”)
(Colwell, col. 17, “lines 63-67 “In embodiments of the invention, the placement of structures in a layout is based upon learned models that apply best practices and historical preferences of the users, and as such, generates more correct results with less required intervention from the user.”)
It 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 to consider an appropriate training model including sequential neural network.
Regarding claim 6
Colwell teaches all aspects of claim 1 as disclosed above and further discloses
The method of claim 1, wherein each historical device placement in the library of historical device placements comprises a device placement corresponding to a circuit design whose device placement was committed at a time prior to the acquiring.
(Colwell, col. 4, lines 32-35 “The training data may include, for example, historical designs that have already been created for the placement of objects and instances in previous layouts.”)
(Colwell, col. 6, lines 34-38 “The disadvantage of this approach is that if the user does have a usable database of historical data, then the training data extracted from the user's own data is likely to be much more accurate than training data extracted from a generic set of data.”)
Regarding claim 7
Colwell teaches all aspects of claim 1 as disclosed above and further discloses
The method of claim 1, wherein the defined number is configurable by a user.
(Colwell, col. 2, lines 30-34 “In some embodiments, the inventive concepts pertains to a system where users re-use patterns of layouts that have been previously implemented, and those previous patterns are applied to create recommendations in new situations.”)
(Colwell, col. 10, line 60 – col. 11, line 2 “A plurality of characteristics, attributes, or configurations may be identified for the row region from the row templated identified or created. These characteristics, attributes, or configurations may include one or more of, for example, the number of rows in the row template, the reference grids, the positive or negative reference X grid offset, the positive or negative reference Y grid offset, the height of a row in the row template, one or more allowed types of circuit components or devices for a row in the row template, or one or more permissible orientations.”)
(Colwell, col. 9, line 13-16 “The EDA module may also provide a default region that may be further customized or configured by a designer in some embodiments.”)
Regarding claim 8
Colwell teaches all aspects of claim 1 as disclosed above and further discloses
The method of claim 1, wherein the providing further comprising providing, for each historical device placement of the defined number of historical device placements, at least one of: a device match metric or a netlist match metric.
(Colwell, col. 7, lines 16-28 “At 202, a plurality of features are extracted from design(s), where variable selection and/or attribute selection is performed. This step is performed to select the relevant set of features that are identified for model construction. Any suitable approach may be employed to perform feature extraction, e.g., filter methods, wrapper methods, and/or embedded methods. For example, filter methods may be performed to reduce the overall amount of data within the model by determining the features which may statistically affect predictive/historical outcomes, where a statistical measure is employed to assign a scoring to each feature and the features are ranked by the score and either selected to be kept or removed from the dataset.”)
Regarding claim 11
Colwell teaches all aspects of claim 1 as disclosed above and further discloses
The method of claim 1, further comprising:
receiving, by the processing device, a signal indicating a user selection of one of the defined number of historical device placements
and loading, by the processing device in response to the signal, the one of the defined number of historical device placements in a symbolic editor canvas for the circuit design.
(Colwell, col. 4, line 67 – col. 5, line 3 “The layout recommender 109 receives schematics/layouts 111 from the user, and will use the predictors to generate a set of layout recommendations.”)
(Colwell, col. 18, “At 922, module 920 receives feature data for two rows of devices, and at 924, determines which of the rows is placed above/beneath the other row.”)
(Colwell, col. 18, line 46-47 “The process then makes a determination, at 818, whether there are any additional devices to place in the layout.”)
(Colwell, col. 5, lines 23-27 “This is quite different from the approach of FIG. 1A, where each user's own historical data is employed from the beginning to generate user-specific models that are individualized for that user.”)
(Colwell, col. 17, lines 63-67 “In embodiments of the invention, the placement of structures in a layout is based upon learned models that apply best practices and historical preferences of the users, and as such, generates more correct results with less required intervention from the user.”)
(Colwell, col. 8, line 66 – col. 9, line 13 “To address shortcomings of conventional approaches for placing instances of standard cells and custom blocks in a placement layout or floorplan, various embodiments described herein identify a placement region or a place and route boundary in a layout canvas or a floorplan. An object may be created and stored in a data structure (e.g., a database) for the placement region or the place and route boundary as a “row region” in some embodiments. A row region may represent a geometric area of the layout or floorplan in the canvas and may be identified in a variety of different manners. For example, a user may specify a placement region or place and route region in a layout canvas or a floorplan, and an EDA module (e.g., a placement module) may create a row region representing the extent of the specified placement region or place and route region. “)
Regarding claim 12
Colwell teaches all aspects of claim 1 as disclosed above and further discloses.
The method of claim 1, wherein the executing comprises filtering the library of historical device placements to remove from consideration by the machine learning model any historical device placements in the library of historical device placements that a user has indicated should not be considered.
(Colwell, col. 7, lines 16-28 “At 202, a plurality of features are extracted from design(s), where variable selection and/or attribute selection is performed. This step is performed to select the relevant set of features that are identified for model construction. Any suitable approach may be employed to perform feature extraction, e.g., filter methods, wrapper methods, and/or embedded methods. For example, filter methods may be performed to reduce the overall amount of data within the model by determining the features which may statistically affect predictive/historical outcomes, where a statistical measure is employed to assign a scoring to each feature and the features are ranked by the score and either selected to be kept or removed from the dataset.”)
(Colwell, col. 13, lines 50-51 “At 404, pruning is applied to remove information that would be irrelevant or of little value to the training process.”)
Regarding claim 13
Colwell discloses
A system comprising: a memory storing instructions
(Colwell, col. 22, lines 26-28 “15. A system for implementing design data for electronic designs, comprising: a memory for storing a sequence of instructions;”)
and a processing device coupled with the memory and to execute the instructions, the instructions when executed cause the processing device to
(Colwell, col. 22, lines 28-30 “… and a processor that executes sequence of instructions to cause a set of acts, the set of acts comprising:”)
build a library of historical device placements, where each data point in the library comprises a set of devices for a circuit design and an historical device placement that was generated for the set of devices
(Colwell, col. 22, lines 31-33 “loading electronic designs, the electronic designs comprising historical circuit schematics and corresponding historical physical layouts;”)
(Colwell, col. 4, lines 32-38 “The training data may include, for example, historical designs that have already been created for the placement of objects and instances in previous layouts. Examples of such objects/instances include, for example, individual devices, device chains, multi-row groups of devices (e.g., a FigGroup/Modgen), custom cells, I/O pins, filler cells, and/or standard cells. A FigGroup is a grouping of circuit components used within certain applications, such as the Open Access database.”)
and train a machine learning model, using the library of historical device placements, to compute a probability distribution function over the library of historical device placements that estimates a suitability of each historical device placement in the library of historical device placements for placing and routing a set of devices for a new circuit design.
(Colwell, col. 4, lines 22-24 “Therefore, the inventive system includes a training system that is employed to generate one or more Machine Learning (ML) models 106.”)
(Colwell, col. 4, lines 32-35 “The training data may include, for example, historical designs that have already been created for the placement of objects and instances in previous layouts. Examples of such objects/instances include, for example, individual devices, device chains, multi-row groups of devices (e.g., a FigGroup/Modgen), custom cells, I/O pins, filler cells, and/or standard cells. A FigGroup is a grouping of circuit components used within certain applications, such as the Open Access database.”)
(Colwell, col. 19, lines 14-22 “As each recommender gives probabilistic recommendations (e.g. the answer to should these two instances be placed in the same row is not yes or no, it is: 90.3% yes/9.7% no, and—the system is chaining these recommendations together), this permits the system to provide multiple recommendations with different confidence levels. The user's selection to the multiple recommendations can be fed back into the models (e.g., using online learning) to update future recommendations.”)
(Colwell, col. 18, lines 15-20 “Module 930 pertains to routing decisions for a row, where at 932 the module 930 receives features of a row of devices, and at 934 determines configuration information for connecting devices in the row. This decision module inputs features of the current row and outputs a most probable routing given the history the system was trained on.”)
(Colwell, col. 6, lines 1-4 “The layout recommender 150 will receive schematics/layouts from the users/customers for new designs, and will use the predictors to generate a set of layout recommendations for each user.”)
Regarding claim 14
Colwell teaches all aspects of claim 13 as disclosed above and further discloses
The system of claim 13, where at least one data point in the library is automatically collected in response to the processing device detecting that a user of an analog design tool has committed new placement pieces into a main layout for circuit design that is under development.
(Colwell, col. 18, lines 46-52 “The process then makes a determination, at 818, whether there are any additional devices to place in the layout. If so, then at 820, the next most probable row is selected, e.g., for devices “above” the previous row. The process then loops back to 804 and continues as described above. However, if there are no further devices to process, then the process ends at 822.”)
Regarding claim 15
Colwell teaches all aspects of claim 13 as disclosed above and further discloses
The system of claim 13, wherein the machine learning model comprises a sequential neural network model.
(Colwell, col. 4, lines 22-29 “Therefore, the inventive system includes a training system that is employed to generate one or more Machine Learning (ML) models 106. These ML models 106 pertain to various aspects of EDA design activities based at least on part upon existing schematics and layouts 103. Any suitable type of training may be applied to generate models 106. For example, “supervised training” is a type of ML training approach that infers a function from labeled training data.”)
It 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 to consider an appropriate training model including sequential neural network model.
Regarding claim 16
Colwell discloses
A non-transitory computer readable medium comprising stored instructions, which when executed by a processing device, cause the processing device to
(Colwell, col. 21, lines 29-33 “A computer program product embodied on a non-transitory computer readable medium, the computer readable medium having stored thereon a sequence of instructions which, when executed by a processor cause a set of acts, the set of acts comprising:”)
acquire an input, where the input specifies a set of devices to be placed and routed for a circuit design
(Colwell, col. 4 line 67 – co. 5, line 3 “The layout recommender 109 receives schematics/layouts 111 from the user, and will use the predictors to generate a set of layout recommendations.”)
(Colwell, col. 3, line 7-8 “FIG. 6 illustrates an example pair of devices to place in a layout.”)
(Colwell, col. 21, line 29-36 “A computer program product embodied on a non-transitory computer readable medium, the computer readable medium having stored thereon a sequence of instructions which, when executed by a processor cause a set of acts, the set of acts comprising: loading electronic designs, the electronic designs comprising historical circuit schematics and corresponding historical physical layouts;”)
(Colwell, col. 20, line 40-48 “A method, comprising: loading electronic designs, the electronic designs comprising historical circuit schematics and corresponding historical physical layouts; implementing a machine learning process, wherein the machine learning process generates a plurality of different trained predictors from features and labels in the electronic designs, the plurality of different trained predictors for generating predictions to a plurality of routing steps,”)
execute, in response to the input, a machine learning model to compute a probability distribution function over a library of historical device placements that estimates a suitability of each historical device placement in the library of historical device placements for placing and routing the set of devices specified in the input
(Colwell, col. 20, lines 18-24 “Computer system 1400 may transmit and receive messages, data, and instructions, including program, e.g., application code, through communication link 1415 and communication interface 1414. Received program code may be executed by processor 1407 as it is received, and/or stored in storage device 1410, or other non-volatile storage for later execution.”)
(Colwell, col. 4, lines 22-24 “Therefore, the inventive system includes a training system that is employed to generate one or more Machine Learning (ML) models 106.”)
(Colwell, col. 4, lines 32-35 “The training data may include, for example, historical designs that have already been created for the placement of objects and instances in previous layouts.”)
(Colwell, col. 18, lines 25-34 “As shown in FIG. 8, machine learning is employed to guide the user through building of placements that is similar to placements that the system was trained on. At 802, a determination is made of the first (e.g., bottom row) in the design. This can be implemented by identifying the most probable row from devices connected to ground, e.g., using the appropriate decision module from FIG. 9. At 804, a determination is made whether the chosen row is acceptable to the user. If not, then at 806, another row is chosen and the process loops back to 504.”)
(Colwell, col. 18, lines 35-42 “At 808, a row is placed at the next layout position, e.g., starting from the bottom of the layout. Next, at 810, a probable first-level routing is identified for the row. The appropriate decision module(s) from FIG. 9 can be employed to implement these steps. At 812, a determination is made whether the identified routing is acceptable to the user. If not, then at 814, the next most probable routing is chosen and the process loops back to 812.”)
(Colwell, col. 6, lines 12-19 “The advantage of the FIG. 1A approach over the FIG. 1B approach is that the models are tuned for the individual user from the very beginning, so that more accurate predictions may be generated right away for the user of interest. The disadvantage with this approach is the challenge of being able to derive enough data from the model if the user does not have a sufficient amount of historical database of past designs to generate an accurate model.”)
and provide graphical representations for a defined number of historical device placements from the library of historical device placements that are estimated to be suited for placing and routing the set of devices based on the probability distribution function.
(Colwell, col. 3, lines 40-44 “FIG. 1A illustrates an example system 100a which may be employed in some embodiments of the invention. System 100a includes one or more users that interface with and operate a computing system to control and/or interact with system 100a using a computing station 101.”)
(Colwell, col. 5, lines 4-9 “Various interfaces may be provided to control the operation of the system 100a. For example, a training interface 113 may be employed to control the operations of the training process, e.g., for selection and/or validation of training data. The layout interface 115 may be employed to control the operations of generating a recommended layout.”)
(Colwell, col. 6, lines 12-19 “The advantage of the FIG. 1A approach over the FIG. 1B approach is that the models are tuned for the individual user from the very beginning, so that more accurate predictions may be generated right away for the user of interest. The disadvantage with this approach is the challenge of being able to derive enough data from the model if the user does not have a sufficient amount of historical database of past designs to generate an accurate model.”)
(Colwell, col. 18, lines 25-34 “As shown in FIG. 8, machine learning is employed to guide the user through building of placements that is similar to placements that the system was trained on. At 802, a determination is made of the first (e.g., bottom row) in the design. This can be implemented by identifying the most probable row from devices connected to ground, e.g., using the appropriate decision module from FIG. 9. At 804, a determination is made whether the chosen row is acceptable to the user. If not, then at 806, another row is chosen and the process loops back to 504.”)
(Colwell, col. 18, lines 35-42 “At 808, a row is placed at the next layout position, e.g., starting from the bottom of the layout. Next, at 810, a probable first-level routing is identified for the row. The appropriate decision module(s) from FIG. 9 can be employed to implement these steps. At 812, a determination is made whether the identified routing is acceptable to the user. If not, then at 814, the next most probable routing is chosen and the process loops back to 812.”)
Regarding claim 17
Colwell teaches all aspects of claim 16 as disclosed above and further discloses
The non-transitory computer readable medium of claim 16, wherein the instructions further cause the processing device to filter the library of historical device placements to remove from consideration by the machine learning model any historical device placements that a user has indicated should not be considered.
(Colwell, col. 7, lines 16-28 “At 202, a plurality of features are extracted from design(s), where variable selection and/or attribute selection is performed. This step is performed to select the relevant set of features that are identified for model construction. Any suitable approach may be employed to perform feature extraction, e.g., filter methods, wrapper methods, and/or embedded methods. For example, filter methods may be performed to reduce the overall amount of data within the model by determining the features which may statistically affect predictive/historical outcomes, where a statistical measure is employed to assign a scoring to each feature and the features are ranked by the score and either selected to be kept or removed from the dataset.”)
(Colwell, col. 13, lines 50-51 “At 404, pruning is applied to remove information that would be irrelevant or of little value to the training process.”)
Regarding claim 18
Colwell teaches all aspects of claim 16 as disclosed above and further discloses
The non-transitory computer readable medium of claim 16, wherein the machine learning model comprises a sequential neural network that has been trained on a plurality of data points, and wherein each of the plurality of data points represents an historical device placement from the library of historical device placements and an historical set of devices corresponding to the historical device placement from the library of historical device placements.
(Colwell, col. 4, lines 11-14 “In the approach of FIG. 1A, the individuated predictors are formed by having each user utilize that user's own historical set of designs to form individualized models for learning purposes. In effect, the historical design data 103 for user A will be used to generate a first individually trained model 106 for user A, while the historical design data for user B will be used to generate a second (separate) model for user B.”)
(Colwell, col. 4, lines 22-29 “Therefore, the inventive system includes a training system that is employed to generate one or more Machine Learning (ML) models 106. These ML models 106 pertain to various aspects of EDA design activities based at least on part upon existing schematics and layouts 103. Any suitable type of training may be applied to generate models 106. For example, “supervised training” is a type of ML training approach that infers a function from labeled training data.”)
(Colwell, col. 4, lines 32-38 “The training data may include, for example, historical designs that have already been created for the placement of objects and instances in previous layouts. Examples of such objects/instances include, for example, individual devices, device chains, multi-row groups of devices (e.g., a FigGroup/Modgen), custom cells, I/O pins, filler cells, and/or standard cells. A FigGroup is a grouping of circuit components used within certain applications, such as the Open Access database.”)
(Colwell, col. 5, lines 18-23 “The general idea is that in the approach of FIG. 1B, a common set of historical schematics/layouts 108 are employed for multiple users to generate a generic set of partially-trained models 169 that can then be used by the multiple different users to generate fully-trained models that are specific to each of the individual users.”)
(Colwell, col. 7, lines 31-34 “At 204, labels may be extracted from the existing designs. The models are trained by a combination of the training set and the training labels, where the labels often correlate to data for which a target answer is already known.”)
(Colwell, col. 17, lines 36-40 “This approach is particularly suitable if the amount of data is not large enough to apply sophisticated models such as deep learning, but where simple models such as logistic regression often cannot express important concepts adequately.”)
(Colwell, col. 17, “lines 63-67 “In embodiments of the invention, the placement of structures in a layout is based upon learned models that apply best practices and historical preferences of the users, and as such, generates more correct results with less required intervention from the user.”)
It 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 to consider an appropriate training model including sequential neural network.
Regarding claim 19
Colwell teaches all aspects of claim 16 as disclosed above and further discloses
The non-transitory computer readable medium of claim 16, wherein the instructions further cause the processing device to: a. receive a signal indicating a user selection of one of the defined number of historical device placements
and load, in response to the signal, the one of the defined number of historical device placements in a symbolic editor canvas for the circuit design.
(Colwell, col. 4, line 67 – col. 5, line 3 “The layout recommender 109 receives schematics/layouts 111 from the user, and will use the predictors to generate a set of layout recommendations.”)
(Colwell, col. 18, “At 922, module 920 receives feature data for two rows of devices, and at 924, determines which of the rows is placed above/beneath the other row.”)
(Colwell, col. 18, line 46-47 “The process then makes a determination, at 818, whether there are any additional devices to place in the layout.”)
(Colwell, col. 5, lines 23-27 “This is quite different from the approach of FIG. 1A, where each user's own historical data is employed from the beginning to generate user-specific models that are individualized for that user.”)
(Colwell, col. 17, lines 63-67 “In embodiments of the invention, the placement of structures in a layout is based upon learned models that apply best practices and historical preferences of the users, and as such, generates more correct results with less required intervention from the user.”)
(Colwell, col. 8, line 66 – col. 9, line 13 “To address shortcomings of conventional approaches for placing instances of standard cells and custom blocks in a placement layout or floorplan, various embodiments described herein identify a placement region or a place and route boundary in a layout canvas or a floorplan. An object may be created and stored in a data structure (e.g., a database) for the placement region or the place and route boundary as a “row region” in some embodiments. A row region may represent a geometric area of the layout or floorplan in the canvas and may be identified in a variety of different manners. For example, a user may specify a placement region or place and route region in a layout canvas or a floorplan, and an EDA module (e.g., a placement module) may create a row region representing the extent of the specified placement region or place and route region. “)
Regarding claim 20
Colwell teaches all aspects of claim 16 as disclosed above and further discloses
The non-transitory computer readable medium of claim 16, wherein each historical device placement in the library of historical device placements comprises a device placement corresponding to a circuit design whose device placement was committed at a time prior to the input being acquired by the processing device.
(Colwell, col. 4, lines 32-35 “The training data may include, for example, historical designs that have already been created for the placement of objects and instances in previous layouts.”)
(Colwell, col. 6, lines 34-38 “The disadvantage of this approach is that if the user does have a usable database of historical data, then the training data extracted from the user's own data is likely to be much more accurate than training data extracted from a generic set of data.”)
Allowable Subject Matter
Claim 9-10 allowed.
The following is a statement of reasons for the indication of allowable subject matter:
Regarding claim 9
Colwell teaches all aspects of claim 8 as disclosed above.
Neither Colwell nor any other prior art teaches
The method of claim 8, wherein the device match metric comprises a percentage that indicates a degree of match between devices in the set of devices specified in the input and devices in the each historical device placement of the defined number of historical device placements.
Regarding claim 10
Colwell teaches all aspects of claim 8 as disclosed above.
Neither Colwell nor any other prior art teaches
The method of claim 8, wherein the netlist match metric comprises a percentage that indicates a degree of match between a graph of a netlist corresponding to the set of devices specified in the input and a graph of a netlist corresponding to the each historical device placement of the defined number of historical device placements.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to RAYAPPU SOUNDRANAYAGAM whose telephone number is (571)272-0629. The examiner can normally be reached Mon-Fri:8:00AM-5:00PM.
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.
/R.S./Examiner, Art Unit 2851
/JACK CHIANG/Supervisory Patent Examiner, Art Unit 2851
Prosecution Insights