Patent Publication Number: US-9898567-B2

Title: Automatic layout modification tool with non-uniform grids

Description:
CROSS REFERENCE TO RELATED APPLICATION 
     This application claims the benefit of Indian Provisional Application No. 1027/CHE/2014, filed on Feb. 28, 2014, which is incorporated by reference herein in its entirety. 
     BACKGROUND 
     1. Field of Art 
     The disclosure generally relates to the field of electronic design automation (EDA), and more specifically to methods and apparatuses for automatic legalization of an integrated circuit layout on non-uniform grids. 
     2. Description of the Related Art 
     Advancements in process technology have impacted integrated circuit manufacturing in at least two key ways. Firstly, scaling of device geometry achieved through sub-wavelength lithography has facilitated the packing of more devices on a chip. Secondly, different fabrication process recipes have enabled the manufacturing of heterogeneous devices with different threshold and supply voltages on the same die. A consequence of these improvements, however, has been an explosion in the number of design rules that need to be obeyed in the layout. Instead of simple width and spacing rules, modern fabrication technologies prescribe complex contextual rules that have to be obeyed for manufacturability. The increase in the number of rules has complicated the task of creating design rule clean layouts, i.e., layouts that do not have design rule violations. Creating design rule clean layouts for digital circuit designs can be facilitated by the use of standard cell layouts as building blocks, and placement and routing tools that are extended to address the design rules. 
     Unfortunately, this approach may not be applicable to analog, mixed signal and RF circuit designs. Layouts for such designs are typically created manually using layout editors, and, because of the number and complexity of the design rules, checking and fixing (i.e., legalizing) them can become a laborious process. 
     Advanced processes (22 nanometers (nm) and below) bring new challenges to layout designs. These advanced processes employ restrictive design rules (RDR) where all shapes in some layers (especially polysilicon) have the same orientation, the same width, and the same pitch. To define where layout objects can be placed in a layer, grids can be specified for each layer in the layout. The grids could be specified in a horizontal, a vertical or both directions to define positional values. Unlike a single manufacturing grid in older processes, these RDRs impose layer specific grids. Thus, layouts now need to obey multiple grid constraints. Furthermore, the grids need not be uniform for a layer, but rather different grid pitches could be defined for the same layer at different locations in the design. The non-uniformity of the grids may arise out of design methodologies. For such layers, in addition to uniform grids, centerlines of rectangular portions of layout shapes may need to be incident on non-uniform grids (i.e., tracks). Similarly, via centers may need to be located at the intersection of the tracks of their corresponding bottom and top layers. 
     Therefore, there is a need for an improved concept providing a robust solution to the problem of layout editing, in a manner that avoids and fixes non-uniform grid constraints with a minimal perturbation from the original form. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
       The disclosed embodiments have other advantages and features which will be more readily apparent from the detailed description, the appended claims, and the accompanying figures (or drawings). A brief introduction of the figures is below. 
         FIG. 1  illustrates one embodiment of an electronic design automation (EDA) design flow. 
         FIGS. 2A and 2B  illustrate examples of layouts before and after legalization with uniform grids. 
         FIGS. 2C and 2D  illustrate examples of layouts before and after legalization with non-uniform grids. 
         FIGS. 3A and 3B  illustrate examples of Boolean variables for a left edge and a right edge of a layout rectangle. 
         FIG. 4  illustrates an example of Boolean implication graph. 
         FIG. 5  illustrates an embodiment of a method for legalizing a layout with the non-uniform grids. 
         FIG. 6  illustrates an embodiment of processing the set of layout constraints using Boolean variables. 
         FIG. 7  illustrates one embodiment of a method for resolving infeasibility by a constraint relaxation process. 
         FIG. 8  illustrates one embodiment of a method for optimizing a layout using a standard linear program solver. 
         FIG. 9  illustrates one embodiment of components of an example machine able to read instructions from a machine-readable medium and execute them in a processor (or controller). 
         FIG. 10  illustrates one embodiment of a layout correction system for legalizing a layout with the non-uniform grids. 
     
    
    
     DETAILED DESCRIPTION 
     The Figures (FIGS.) and the following description relate to preferred embodiments by way of illustration only. It should be noted that from the following discussion, alternative embodiments of the structures and methods disclosed herein will be readily recognized as viable alternatives that may be employed without departing from the principles of what is claimed. 
     Reference will now be made in detail to several embodiments, examples of which are illustrated in the accompanying figures. It is noted that wherever practicable similar or like reference numbers may be used in the figures and may indicate similar or like functionality. The figures depict embodiments of the disclosed system (or method) for purposes of illustration only. One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles described herein. 
     Configuration Overview 
     One embodiment of disclosed configurations includes a method (and system) for automatic layout modification with non-uniform grids to be used in a process of design and fabrication of an integrated circuit. The disclosed configuration can be employed in electronic design automation (EDA) software in the process of design of an integrated circuit. 
     The disclosed configuration enables automatic mechanisms of identifying layout constraints of layout objects and resolving the layout constraints using Boolean variables. One example configuration comprises generating a set of layout constraints based on a plurality of non-uniform grids. The set of layout constraints includes, for example, design rule check constraints and gridding requirements, where gridding requirements are requisites for a layout object to align to a grid. In addition, the configuration processes the set of layout constraints to a feasible form in which the layout object can be modified to satisfy the set of layout constraints. The configuration processes the set of layout constraints using the Boolean variables by (i) assigning the Boolean variables to layout variables that identify a position of a layout object, (ii) determining whether the set of layout constraints is infeasible using the Boolean variables, and (iii) responsive to the set of layout constraints determined to be infeasible, identifying an infeasible layout constraint from the set of layout constraints, the infeasible layout constraint causing the set of layout constraints to be infeasible, and relax the identified infeasible layout constraint for the set of layout constraints to be in the feasible form. Additionally, the configuration generates an output circuit layout, for display to a user, by solving the set of layout constraints in the feasible form with a standard linear program solver. 
     With the disclosed configuration, layout objects in a layout are automatically corrected to solve layout constraints. A layout object herein refers to a representation of a position and geometry of any circuit or routing element to be laid in order to construct a circuit. A layout variable herein refers to a positional value of a layout object. In addition, the disclosed configuration identifies infeasible layout constraints from a set of layout constraints by generating a Boolean implication graph based on the Boolean variables of the each of the layout variables, and checking for (or determining) satisfiability of the Boolean implication graph. The Boolean implication herein refers to a logical implication such that one condition leads to another condition (i.e., a→b). The satisfiability in terms of mathematical logic herein refers to a condition that one can find a binary assignment to the Boolean variables in a formula (or a statement) such that the formula (or the statement) evaluates to true. In addition, feasibility herein refers to a condition where a solution exists that satisfies all the set of layout constraints. Hence, infeasibility (or infeasible) herein refers to a condition that is not feasible. 
     In one example embodiment, a representation of a layout object is processed to assign variables to horizontal and vertical edges of layout edges. Using the assigned variables, a constraint graph is generated to indicate constraints (e.g., DRC constraints) applied to the layout object, where each constraint models a design rule across two layout edges. Due to conflicts in different constraints, the constraint graph could be infeasible (i.e., there is no solution to satisfy the constraints). Infeasibility of the constraint graph can be detected by, for example, performing Bellman Ford longest path run and finding positive cycles in the constraint graph. If a positive cycle is detected, then the infeasibility is resolved by relaxing one or more constraints in the positive cycle or replacing a value of the layout constraint restricting the layout object to be placed to a less restrictive value. Detecting whether the constraint graph is infeasible and relaxing one or more constraints can be iterated until no positive cycles are found in the constraint graph. 
     In the example embodiment, a range for each layout edge variable is computed to enable modeling of the gridding requirements. For computation of these ranges, forward and backward runs of layout aware Bellman Ford longest path algorithm may be implemented. The forward run provides one extreme value (e.g., leftmost position) for each layout positional variable, and the backward run provides another extreme value (e.g., rightmost) for each layout positional variable. In one approach, the longest path runs are performed in a manner that these ranges are as small as possible. 
     In the example embodiment, once the ranges are computed for each layout variable, valid grid positions in these ranges are identified. Each grid position is modeled by a Boolean variable. Each constraint in the infeasibility resolved constraint graph is converted into a set of Boolean implications using the ranges of the corresponding layout variables. Collectively the set of Boolean implications is checked for satisfiability using a 2SAT solver. The 2SAT solver computes Strongly Connected Components (SCC) and determines whether a SCC contains a Boolean variable and its compliment in it. The SCC containing a Boolean variable and its compliment indicates infeasibility in the gridding requirements. The infeasibility in the gridding requirements is resolved by relaxing the grid constraint (e.g., either locking the layout edge to its current value of the gridding requirement, or dropping the gridding requirement on it). Detecting whether the gridding requirements is infeasible and relaxing the gridding requirements are iterated to resolve all gridding infeasibilities. 
     In the example embodiment, the output representation of the layout compliant with DRC constraints and gridding requirements on non-uniform grids is generated based at least in part on the Boolean variables. In one aspect, a minimum perturbation objective function is modeled using these Boolean variables. The overall Boolean implications are then modeled as a linear program (which is guaranteed to be feasible) and solved. The solution of linear program results into binary (or Boolean) values for Boolean variables. The solution of linear program is then transformed back to layout positional values for each variable. An output representation of the layout is generated using the transformed layout positional values, where the output representation of the layout is compliant with DRC constraints and grid requirements. 
     Overview of EDA Design Flow 
     Referring now to  FIG. 1 , illustrated is a flowchart  100  illustrating the various operations in the design and fabrication of an integrated circuit. This process starts with the generation of a product idea  110 , which is realized during a design process that uses EDA software  112 . When the design is finalized, it can be taped-out  140 . After tape-out  140 , a semiconductor die is fabricated  150  to form the various objects (e.g., gates, metal layers, vias) in the integrated circuit design. Packaging and assembly processes  160  are performed, which result in finished chips  170 . 
     The EDA software  112  may be implemented in one or more computing devices. For example, the EDA software  112  is stored as instructions in the computer-readable medium which are executed by a processor for performing operations  114 - 132  of the design flow, which are described below. This design flow description is for illustration purposes. In particular, this description is not meant to limit the present disclosure. For example, an actual integrated circuit design may require a designer to perform the design operations in a different sequence than the sequence described herein. 
     During system design  114 , designers describe the functionality to implement. They can also perform what-if planning to refine the functionality and to check costs. Note that hardware-software architecture partitioning can occur at this stage. Example EDA software products from Synopsys, Inc. of Mountain View, Calif. that can be used at this stage include: Model Architect®, Saber®, System Studio®, and Designware® products. 
     During input netlist design  115 , the designers construct an input netlist of an intended circuit (or system). The input netlist design  115  may include different steps for digital circuit logic design  117  and analog/mixed signal/RF circuit schematic design  118 . In case of digital circuit logic design  117 , circuit components and configurations may be automatically obtained via logic design and functional verification step, and synthesis and design for test step. During the logic design and functional verification step, VHDL or Verilog code for modules in the circuit is written and the design is checked for functional accuracy. More specifically, the design is checked to ensure that it produces the correct outputs. Example EDA software products from Synopsys, Inc. of Mountain View, Calif. that can be used at this stage include: VCS®, Vera®, 10 Designware®, Magellan®, Formality®, ESP® and Leda® products. 
     During the synthesis and design for test step, VHDL/Verilog code is translated to an input netlist. This input netlist can be optimized for the target technology. Additionally, tests can be designed and implemented to check the finished chips. Example EDA software products from Synopsys, Inc. of Mountain View, Calif. that can be used at this stage include: Design Compiler®, Physical Compiler®, Test Compiler®, Power Compiler®, FPGA Compiler®, Tetramax®, and Designware® products. 
     In case of analog/mixed signal/RF circuit schematic design  118 , the input netlist of the intended circuit (or system) including circuit components and configurations (e.g., active and passive components, connections, ports and etc.) is manually constructed. The input netlist can be manually coded in a vendor specific or neutral netlist format. Alternatively, the input netlist can be constructed as a schematic using a tool that (i) provides a visual representation of a schematic of a circuit and (ii) extracts an input netlist according to the schematic. In addition, an input netlist obtained from the analog/mixed signal/RF circuit schematic design maybe combined with another input netlist obtained from the digital circuit logic design  117 . Example EDA software products from Synopsys, Inc. of Mountain View, Calif. that can be used at this stage include: Galaxy Custom Designer® SE and Laker products. 
     During netlist verification  120 , the input netlist from the input netlist design  115  is checked for compliance with design requirements or specifications. For digital circuits and systems design, the input netlist is checked for timing constraints and for correspondence with the VHDL/Verilog source code. In case of analog/mixed signal/RF circuits the input netlist is simulated with a circuit simulator to check whether design requirements and specifications are met. In case the design requirements or specifications are not met, the designers may return to the system design  114  or the input netlist design  115  and repeat the process. Example EDA software products from Synopsys, Inc. of Mountain View, Calif. that can be used at this stage include: Formality®, Primetime®, VCS®, HSPICE®, and Galaxy Custom Designer® SE products. 
     During physical design planning  122 , an overall floor plan for the chip is constructed and analyzed for timing and top-level routing. Example EDA software products from Synopsys, Inc. of Mountain View, Calif. that can be used at this stage include: Astro® and IC Compiler® products. 
     During physical implementation  124 , the placement (positioning of circuit elements) and routing (connection of the same) occur. For digital circuits, automatic place and route EDA tools are used. For analog/mixed signal/RF circuits layout editor tools are used. Example EDA software products from Synopsys, Inc. of Mountain View, Calif. that can be used at this stage include: the Astro®, IC Compiler®, Galaxy Custom Designer® and Laker LE products. 
     During analysis and extraction  126 , the circuit function is verified at a transistor level considering the placement and geometry of circuit elements, routing, and etc. In case the design requirements or specifications are not met, the designers may return to the system design  114 , the input netlist design  115  or the physical implementation  124  and repeat the process. Example EDA software products from Synopsys, Inc. of Mountain View, Calif. that can be used at this stage include: Astrorail®, Primerail®, Primetime®, and Star RC/XT® products. 
     During physical verification  128 , the design is checked to ensure correctness for: manufacturing, electrical issues, lithographic issues, and circuitry. Example EDA software products from Synopsys, Inc. of Mountain View, Calif. that can be used at this stage include the Hercules® product. 
     During resolution enhancement  130 , geometric manipulations of the layout are performed to improve manufacturability of the design. Example EDA software products from Synopsys, Inc. of Mountain View, Calif. that can be used at this stage include: Proteus®, Proteus®AF, and PSMGED® products. 
     During mask-data preparation  132 , the ‘tape-out’ data for production of masks to produce finished chips is provided. Example EDA software products from Synopsys, Inc. of Mountain View, Calif. that can be used at this stage include the CATS® family of products. 
     Embodiments of the present disclosure can be used during one or more of the above-described stages. Specifically, in some embodiments the present disclosure can be used in EDA software  112  that includes operations between physical implementation  124  and physical verification  128 . 
     Example Method for Automatic Layout Modification on Non-Uniform Grids 
     In the process of circuit layout and layout editing, limitations in lithography at 20 nm and below necessitate non-uniform grids. Layout shapes on a mask layer need to comply with the grids defined on that layer. A layout can be thought of as a collection of shapes in various mask layers. For a layout to be correctly fabricated it needs to also obey all the design rules like minimum width, minimum spacing, via sizes, minimum extension of metal over via, spacing between transistor diffusions, width of transistor gates, extension of wells over diffusions, etc. Layout legalization herein refers to a process of automatically modifying a layout to make it compliant with all layer specific non-uniform grids and design rules. Such legalization tools fracture layout shapes into rectangles. Each rectangle edge is considered as a positional variable (i.e., layout variable). Thus, each rectangle has four positional variables associated with it, two of each in the horizontal and the vertical directions. A constraint graph is built with each positional variable as a node, and each design rule as an edge. An edge denotes a manufacturing constraint between the associated layout positional variables. In conventional legalization methods, general design rule constraints are handled by a design rule check (DRC), in which the design rule constraints are formulated as difference constraints. For instance, such design rules correspond to technology-dependent rules like spacing rules in one layer or spacing rules between several layers or various context dependent rules comprising single or multiple layers. 
     However, conventional legalization approaches do not take non-uniform grids into an account. Therefore, a layout may not be fixed in a grid compliant way or may not be optimized with the conventional legalization methods. For example, in  FIGS. 2A and 2B , illustrated are a layout before and after legalizing with uniform grids. In  FIG. 2A , uniform grids G 1  to G 6  identify positional values in the layout. For example, a first polisilicon area  222  with a first diffusion area  224  form a first transistor  220 , and a second polisilicon area  232  with a second diffusion area  234  form a second transistor  230 . The second transistor  230  violates a gridding requirement (i.e., a requirement for a layout object to snap to a grid), because a center line of the second transistor  230  is not on one of uniform grids G 1  to G 6 . Preferably, the gridding requirement is satisfied while modifying the original layout by a minimal amount from an original spacing SP between the two transistors  220  and  230 . As a solution, the second transistor  230  may be positioned such that the center line of the second transistor  230  is incident on the grid G 5 , according to the uniform grids G 1  to G 6 . 
     In  FIGS. 2C and 2D , illustrated are layouts before and after legalization with non-uniform grids (i.e., tracks) according to a disclosed embodiment.  FIG. 2C  is similar to  FIG. 2A , except tracks T 1  to T 8  identify positional values in the layout. The uniform grids G 1 , G 2 , G 3 , G 4 , G 5  and G 6  correspond to the tracks T 1 , T 2 , T 3  T 4 , T 6 , and T 8  respectively. Hence, additional tracks T 5  and T 7  identify additional positional values. In  FIG. 2D , the layout is corrected such that the center line of the second transistor  230  is incident on the track T 5 . This resolves the gridding requirements while modifying the original layout by a minimal amount from an original spacing SP between the two transistors  220  and  230 . Here, legalizing a layout using non-uniformly spaced tracks resulted in the lesser amount of change compared to legalizing the same layout using uniform grids as in  FIG. 2B . 
     The general design rule constraints are of the form x i −x j ≧w ij , where x i  and x j  are the positional variables (i.e., layout variables) corresponding to two rectangle edges, and wij corresponds to the required distance between the variables to obey the particular design rule. This results in the following linear program: 
                 minimize   ⁢       ∑     i   =   1     N     ⁢           ⁢              x   i     -     x   j   0            ⁢           ⁢   subject   ⁢           ⁢   to   ⁢     :     ⁢           ⁢   A   ⁢     x   →           ≥   b     ,         
where {right arrow over (x)} is a column vector comprising of the variables corresponding to rectangle edges, x j   0  is the rectangle edge position in the input layout. The matrix A is the coefficient matrix for the constraints, where each row Ai represents a single constraint. The vector b represents the rule values. The term |x i −x j   0 | models perturbation on the input layout. The objective function minimizes total perturbation across all layout edges. The resulting problem can be solved by a standard linear program solver (herein also referred to as “a regular linear program solver”). However, a standard linear program solver only guarantees integral solution, when the matrix A is Totally Uni-Modular (TUM). In an advanced fabrication process, each mask layer can have its own grid which can be non-uniform. Therefore, for a layout with non-uniform grids, the matrix A is no longer Totally Uni-Modular. To produce the matrix A in a TUM form, Boolean variables can be used to represent layout variables on the non-uniform grids, according to the disclosed method.
 
     Referring to  FIG. 3A , illustrated are examples of Boolean variables for a left edge  350 A and right edge  360 A of a layout rectangle  300 A in a shaded region. The width of the layout rectangle  300 A represents a layout constraint  310 A. The layout constraint may be a DRC constraint or a gridding requirement (i.e., a requirement to snap a layout object on a grid). The layout constraint  310 A may represent a minimum or maximum spacing width between two layout variables, where one layout variable is the position of the left edge  350 A of the layout rectangle  300 A and the other layout variable is the position of the right edge  360 A of the layout rectangle  300 A. 
     The disclosed method finds out the ranges that each layout variable can take while still satisfying all the design rules as specified through the constraint graph. Within each range the available tracks are identified as valid positions for that layout variable. In  FIG. 3A , the left edge  350 A can be placed on any one of tracks T 31 , T 32 , and T 33 . Similarly, the right edge  360 A can be placed on any one of tracks T 34 , T 35 , and T 36 . The tracks T 31  to T 36  are layer specific non-uniform tracks, and each track is assigned a Boolean variable. For example, the tracks T 31 , T 32 , and T 33  are assigned to Boolean variables b 1 i, b 2 i, and b 3 i, and the tracks T 34 , T 35 , and T 36  are assigned to Boolean variables b 1 j, b 2 j, and b 3 j. Hence, the Boolean variables b 1 i, b 2 i, and b 3 i form one set and the Boolean variables b 1 j, b 2 j, and b 3 j form another set. If the left edge  350 A of the layout rectangle  300 A is positioned on the track T 31 , then as per the layout constraint  310 A the right edge  360 A of the layout rectangle  300 A should at least be positioned on the track T 34 , as indicated by a Boolean implication  131 . Likewise if the left edge  350 A of the layout rectangle  300 A is positioned on the track T 32 , then the right edge  360 A should at least be positioned on the track T 35 , as modeled by a Boolean implication  132 . Similarly, if the left edge  350 A is positioned on the track T 33 , then the right edge  360 A should at least be positioned on the track T 36 , as modeled by a Boolean implication  133 . In one implementation, if a Boolean variable for any track corresponding to the left edge  350 A of the layout rectangle  300 A is assigned a value ‘1,’ it implies that Boolean variables for tracks positioned to the left of the track corresponding to the left edge  350 A are also each assigned a value ‘1.’ If the layout edge is assigned on a specific track by the constraint solver then Boolean variables for tracks to the right of that track are each assigned a value ‘0.’ 
     For example, in  FIG. 3A , the left edge  350 A is positioned on the track T 32 , therefore the Boolean variable b 2 i is assigned a value ‘1.’ Hence, the Boolean variable b 1 j is assigned a value ‘1,’ and the Boolean variable b 2 i is assigned a value ‘0.’ Similarly, the right edge  360 A is positioned on the track T 35 , therefore the Boolean variables b 1 j, b 2 j, and b 3 j are assigned to ‘1,’ ‘1,’ and ‘0’ respectively. 
     In  FIG. 3B , illustrated is the Boolean variables of the layout rectangle  300 A after solving collection of the Boolean implications  131  to  133  in  FIG. 3A . If the Boolean variables b 1 i, b 2 i, b 3 i, b 1 j, b 2 j, and b 3 j are assigned values as ‘1,’ ‘0,’ ‘0,’ ‘1,’ ‘1,’ and ‘1,’ respectively, then a left edge  350 A of a layout rectangle  300 A is positioned on the track T 31  and a right edge  360 A of the layout rectangle  300 A is positioned on track T 36 . The representation of the Boolean values ‘1’ and ‘0’ are only one way of example of an embodiment, and can be represented in other forms. 
     As noted earlier, if a Boolean variable b p i is set to ‘1’ then all Boolean variables corresponding to locations on the left of the location corresponding to b p i are also set to ‘1.’ Let b p−1 i be a Boolean variable corresponding to a location that is to the immediate left of the location corresponding to Boolean variable b p i. Then b p i b→b p−1 i (→ stands for logical implication). Moreover, by skew symmetry, !b p−1 i→!b p i (“!” stands for logical not operation). These Boolean implications are collected in an “implications set”. Likewise each design rule is also modeled as a set of implications. In the example of  FIG. 3A  the implication  131  corresponds to b 1 i→b 1 j. Whether a satisfiable value assignment can be achieved on the implications set such that all implications are satisfied is equivalent to solving a satisfiability problem. Since each implication contains only two Boolean variables, a 2-Satisfiability (2SAT) problem needs to be solved. This also implies that determining whether a constraint system is consistent is equivalent to determining a satisfiable assignment on the corresponding implications set. In order to determine whether a satisfiable assignment exists, an implication graph is used. Each Boolean variable and its complement are represented by two separate vertices in the graph. Implications form edges between these vertices. 
     Referring to  FIG. 4 , illustrated is an example of a Boolean implication graph modeling a possible position of the layout object. In  FIG. 4 , implications I 41 , I 42  and I 43  correspond to bi 2 →bi 1 , bj 1 →bi 2 , and bj 2 →bj 1 , respectively. Additionally, implications I 44  and I 46  correspond to bi 1 →bj 1 , and bi 2 →bj 2 , respectively. By the skew symmetry, implications !I 41 , !I 42 , and !I 43  imply that !bi 1 →!bi 2 , !bi 2 →!bj 1 , and !bj 1 →!bj 2 , respectively. Further, implications !I 44  and !I 46  imply that !bj 1 →!bi 1 , and !bj 2 →!bi 2 , respectively. In addition, implications I 45  and !I 45  imply that bj 2 →!bj 2 , and !bi 1 →bi 1 , respectively. Boolean implications can be used to identify feasibility or infeasibility of the set of layout constraints by checking for (or determining) satisfiability using a 2SAT solver. Infeasible sets are identified by determining the Strongly Connected Components (SCCs) of the implication graph. If a literal and its complement are present in the same SCC then the logic is not 2-Satisfiable, else it is 2-Satisfiable. 
     Generally, the constraint set obtained from a realistic layout is often infeasible due to conflicts between complex rules and design intents, lack of leeway in moving shapes due to placed macros, locked shapes, and sometimes due to incomplete modeling. Therefore, it is advantageous to detect and resolve such infeasibilities and obtain a set of solvable constraints. Infeasibility in the constraint graph over layout positional variables can be detected as a positively weighted cycle in the constraint graph. These positively weighted cycles can be identified through longest path runs. Constraints in the positively weighted cycle are usually relaxed to make the cycle non positive and hence resolve the corresponding infeasibility. Once all positively weighted cycles are resolved, the corresponding linear program becomes feasible and can be optimized for minimum perturbation objective. 
     Inconsistencies in the constraints express themselves as positively weighted cycles. These positive cycles are detected by invoking a single source longest path algorithm, e.g., the Bellman-Ford algorithm. The algorithm is applied iteratively until all positive cycles are detected and resolved. Advantageously, the longest path algorithm can be implemented, which is very efficient in practice. 
     The disclosed method identifies and resolves infeasibilities in the presence of tracks.  FIG. 5  shows an example of a flow-chart implementing a legalization method according to the improved concept. First, an integrated circuit layout including a plurality of layout objects (e.g., islands) are provided in an input layout step  510 . As discussed above, such a circuit layout may be represented as a plurality of shapes or rectangles with positional variables (i.e., layout variables). Further, a set of layout constraints based on DRC and non-uniform grids are generated in step  520 . 
     In addition, the set of layout constraints are processed using Boolean variables in step  525  to a feasible form. To describe step  525  in detail, the set of layout constraints are checked for infeasibility (or feasibility) using the Boolean variables in step  530 . If the overall constraint set is determined to be infeasible  524  according to the set of variables, then infeasible layout constraints are identified from the set of layout constraints in step  535 . Moreover, the infeasible layout constraints are resolved by relaxing the layout constraint via a constraint relaxation process in step  540 . Hence, the relaxed layout constraint is checked again for the infeasibility in step  530 . Steps  530 ,  535  and  540  are performed iteratively, until the set of layout constraints is feasible. 
     If the overall constraint set is found feasible in the iterative process in step  525 , this set of constraints is provided to a standard linear program solver to optimize a layout, which becomes effective in step  550 . The result of the linear program solver represents the output layout (herein also referred to as an “output circuit layout”), which is provided in step  560 . The output layout may be provided for display to a user in a graphical representation as well. The output layout corresponds to a physical design of circuits to be fabricated. 
     Referring to  FIG. 6 , illustrated is an embodiment of a method for processing the set of layout constraints using the Boolean variables in step  525 . To check for infeasibility using the Boolean variables in step  530 , constraint ranges for the layout constraints are initialized in step  600 . In addition, the layout constraints generated in step  520  or step  540  are used to compute a constraint range for each layout constraint in step  610 . Additionally, each layout variable is assigned (i.e., associated with) a Boolean variable. In one example, this computation is done by using a longest path type computation from a left-most layout edge first, and then by using a longest path type computation from a right-most layout edge. In one embodiment, the longest path type computation may employ Layout-aware Bellman-Ford Algorithm (LABF). Alternatively, the longest path type computation may employ Bellman-Ford Algorithm (BF). Additionally, infeasibility of the set of layout constraints is determined, by checking whether the range computation terminates or not in step  620 . For example, if the range computation terminates, the constraints are feasible  522 . On the other hand, if the range computation does not terminate, the constraints are infeasible  524 . 
     In step  535 , the infeasible layout constraints are identified. Specifically, Boolean implications are built from the yet computed ranges in step  630 . Moreover, infeasible layout constraints are identified by checking for satisfiability using a 2SAT solver based on the Boolean implication graph in step  640 . The 2SAT solver provides Strongly Connected Components, where each component corresponds to infeasibility. Original layout constraints are identified as causes of infeasibility and certain constraints are relaxed as needed to resolve the infeasibility in step  540 . After all infeasibilities in the current iteration are resolved, range computation is reattempted in step  530 . If the range computation terminates, then the constraints are solvable using the standard linear program solver in step  550 . If the range computation does not terminate, then the process is repeated. 
     Referring to  FIG. 7 , illustrated is an embodiment of a method for resolving the infeasibility by the constraint relaxation process in step  540 . Once the infeasible layout constraints are identified in step  640 , a type of layout constraint for each of the infeasible layout constraints are identified in step  710 . For example, the layout constraints can be classified into two types: a gridding requirement and a DRC constraint. For an infeasible layout constraint with the gridding requirement, the gridding requirement is relaxed gradually in step  720 . In one approach, steps  720 ,  530  and  535  are repeated until the set of layout constraints are determined to be feasible  522 . If the set of layout constraints are still infeasible  524  after relaxing the gridding requirements in all layout objects, the design rule constraints are gradually relaxed through the repeated steps of  730 ,  530  and  535  until a feasible problem is obtained. Relaxing the gridding requirement in step  720  ahead of relaxing the DRC constraints in step  730  indicates a priority for DRC over grid snapping. Alternatively, relaxing the DRC constraints in step  730  may be performed ahead of the relaxing gridding requirement in step  720 . This indicates a priority for grid snapping over DRC. It is to be noted that, during the process, a gridding requirement, with any edge of a layout object which is already on the grid, is maintained without dropping. This ensures that additional gridding violations are not introduced in the already gridded layout edge. Likewise, a DRC constraint, with any edge of a layout object if satisfied, is maintained without relaxing. This again is to ensure that additional DRC violations are not introduced in an already DRC correct layout portion. 
     For feasibility, the total cycle weight needs to be made non-positive. This is achieved by reducing the weights of certain edges participant to the cycle. In other words, if the corresponding constraint value is larger than the associated layout value, it is diluted to the layout value. This dilution of constraints to input layout value is continued on other edges until the given cycle&#39;s weight becomes non-positive. 
     Resolution of positive cycles in this way has two interesting properties. First, if a constraint is not satisfiable, the input layout value is retained i.e., it is made no worse than how it started. Second, the input layout positions represent a feasible solution (albeit with relaxed or diluted constraints). Therefore, relaxing infeasible constraints to input layout value ensures termination of the infeasibility resolution step. 
     Referring to  FIG. 8 , illustrated is an embodiment of a method of optimizing the layout using the standard linear program solver in step  550 , with the feasible set of layout constraints from step  530 . With each layout variable associated with a Boolean variable in step  610  and Boolean implications obtained in step  630 , the Boolean implications can be re-written (or transformed) as linear difference constraints in step  810 . Moreover, the minimum perturbation objective function can also be re-written (or transformed) in terms of the Boolean variables in step  820 . For example, the minimum perturbation objective function component for variable x i  can be defined as: 
                      x   i     -     x   i   0            =     (         ∑     p   =   1       C   i       ⁢           ⁢       (     1   -     b   i   p       )     ⁢     δ   i   p         +       ∑     p   =       C   i     +   1              x   i            ⁢           ⁢       b   i   p     ⁢     δ   i   p           )                          x   i     -     x   i   0            =       (       -       ∑     p   =   1       C   i       ⁢           ⁢       b   i   p     ⁢     δ   i   p           +       ∑     p   =       C   i     +   1              x   i            ⁢           ⁢       b   i   p     ⁢     δ   i   p           )     .           
where x i  is a layout variable corresponding to a rectangle edge, and x i   0  is a rectangle edge position in the input layout. The variable b i   p  is the Boolean variable, and δ i   p  is the distance between p-th and (p−1)-th tracks. In addition, C i  is the index of the input layout location of variable and |x 1  is a set of layout variables. The total layout perturbation is the sum of perturbations for all layout variables. Because an edge can move in a one dimensional direction (e.g., horizontal or vertical direction) on the grid location, the above equation determines the perturbation from the current location based on the eventual output grid location that the positional variable would take.
 
     In general, possible lower and upper bounds for locations that layout variables can take may be generated using two BF runs. However, BF runs fail to include all the minimum perturbation points. In contrast, the disclosed method determines the lower and upper bounds for locations that layout variables can take using a modified BF algorithm called as Layout Aware Bellman Ford (LABF) algorithm. LABF ensures that all minimum perturbation points are included in the determined ranges. Additionally, LABF takes non-uniform grids into account. The essence of this algorithm is that a variable is perturbed if dictated by a constraint. To achieve this, unlike BF, the variables are initialized with their initial layout locations. In a forward run of LABF, a variable is updated when a constraint pushes it to the right. Note that unlike BF, a forward LABF run coupled with track aware rounding, generates the upper bound. The reverse LABF with graph edges and weight signs inverted, generates the lower bound. 
     For example, if layout variables x1, x2, x3, and x4 have layout locations 0, 50, 50, and 100 respectively with constraints x2−x1≧40, x3−x1≧40, x4−x2≧60, and x4−x3≧60. The edges (or bounds) generated by the forward and reverse BF runs are listed in columns 3 and 4 (labeled BF LB and BF UB) in Table 1. The edges generated by the forward and reverse LABF runs are labeled LABF LB and LABF UB and listed in columns 5 and 6 of Table 1. Note that the lower and upper bounds include the minimum perturbation points for each variable. 
     
       
         
           
               
               
               
               
               
               
             
               
                 TABLE 1 
               
               
                   
               
               
                 Variable 
                 Layout loc. 
                 BF LB 
                 BF UB 
                 LABF LB 
                 LABF UB 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
               
            
               
                 x1 
                 0 
                 0 
                 0 
                 −10 
                 0 
               
               
                 x2 
                 50 
                 40 
                 40 
                 40 
                 50 
               
               
                 x3 
                 50 
                 40 
                 40 
                 40 
                 50 
               
               
                 x4 
                 100 
                 100 
                 100 
                 100 
                 110 
               
               
                   
               
            
           
         
       
     
     In this example, the minimum perturbation solution is ‘0,’ ‘50,’ ‘50,’ and ‘110,’ for x1, x2, x3 and x4 respectively with a total perturbation of ‘10’ units. However, it is not possible to achieve this minimum perturbation using the ranges in columns labeled BF LB and BF UB in Table 1 while satisfying constraints. This is because probable minimum perturbation solution points ‘50,’ ‘50,’ and ‘110’ are missed out in ranges of variables x2, x3, and x4 respectively. 
     The edges generated by the forward and reverse LABF runs are listed in columns labeled LABF LB and LABF UB in Table 1. Note that the LABF UB provides minimum perturbation solutions with a perturbation of 10 units. Similarly, LABF LB provides minimum perturbation solutions if all variables are offset by 10 units. As a result, LABF according to the disclosed embodiment achieves a minimum perturbation. 
     Solving a linear optimization problem in terms of Boolean variables enables a constraint matrix A to be in a TUM form in step  830 . Therefore, efficiency is improved compared to implementing an integer linear program solver to fix a layout with non-uniform grids. Furthermore, a solution with the Boolean variables from the standard linear program solver in step  830  is translated to the positional values on the non-uniform grid in step  840 . 
     Beneficially, the disclosed configuration provides automatic design rule correction engines, which are an important aid in generating violation free layouts. The disclosed configuration efficiently identifies positional values utilizing Boolean representation. As a result, a constraint matrix can be formed in a TUM form, even with positional values on non-uniform grids. Hence, the disclosed configuration can efficiently solve a DRC correction problem on layouts with non-uniform grids using a simple linear program solver with minimum perturbation from an original layout. 
     The disclosed configuration becomes invaluable in an advanced process where non-uniform grids exist. For example in a FinFET process, transistors need to be aligned with the FIN locations, functioning as non-uniform grids. Without an ability to snap onto non-uniform grids as the disclosed embodiment, each FinFET has to be manually positioned to FINs appropriately according to DRC constraints. An attempt to edit a layout, in a local area of a large transistor network to fix a DRC constraint, can result in a series of incompliance with DRC constraints in large regions. Hence, the disclosed configuration improves efficiency in an integrated circuit design process by automatically modifying a layout with respect to non-uniform grids. 
     The advantages also include flexibility in integration with other existing EDA tools. For example, the disclosed configurations can also be integrated with a double pattern technology (DPT) fixing feature in Galaxy Custom Designer® or LAKER® from Synopsys, Inc., and be used in an advanced fabrication process that requires multiple patterns in the same layer. 
     Example System for Automatic Layout Modification on Non-Uniform Grids 
     Referring to  FIG. 10 , illustrated is a layout correction system  1020  for legalizing a layout with the non-uniform grids, according to one embodiment. The layout correction system  1020  receives an electronic representation of an input circuit layout  1010  (herein generally referred to as an “input layout  1010 ”) including layout objects, where the input layout  1010  that may fail one or more DRC constraints or gridding requirements. The layout correction system  1020  modifies the input layout  1010  to generate an electronic representation of an output circuit layout  1030  (herein generally referred to as an “output layout  1030 ”) that is compliant with the DRC constraints and the gridding requirements. 
     In one embodiment, the layout correction system  1020  includes a layout parsing module  1005 , a constraint generation module  1015 , a constraint process module  1025 , and an output layout generation module  1035 . Each of these components may be embodied as hardware, software, firmware or a combination thereof. Together, these components perform a layout correction to generate the output layout  1030  compliant with the DRC constraints and the gridding requirements. 
     The layout parsing module  1005  receives the input layout  1010  and identifies a layout object having any arbitrary shape in the input layout  1010 . In addition, the layout parsing module  1005  parses the layout object into one or more layout rectangles. In case the input layout  1010  is parsed into multiple rectangles already, the layout parsing module  1005  may be omitted. 
     The constraint generation module  1015  generates a set of layout constraints (DRC constraints and/or gridding requirements) for a layout object in the input layout  1010 . The constraint generation module  1015  generates the set of layout constraints based on the non-uniform grids. For example, the constraint generation module  1015  generates the gridding requirement enforcing a layout object to align to one of the plurality of non-uniform grids. 
     The constraint process module  1025  processes the set of layout constraints to a feasible form for the layout object to be capable of being modified to satisfy the set of layout constraints. As illustrated in  FIG. 10 , the constraint process module  1025  comprises an infeasibility determination module  1072 , a range identification module  1074 , a Boolean variable conversion module  1076 , an implication graph generation module  1078 , and a constraint relaxation module  1075 . Each of these components may be embodied as hardware, software, firmware or a combination thereof. 
     The range identification module  1074  identifies a possible range for an edge of a layout rectangle according to the DRC constraints and/or the gridding requirements. In one approach, the range identification module  1074  computes a range for each layout edge to be able to model the gridding constraint. For computation of these ranges, the range identification module  1074  employs forward and backward runs of Bellman Ford longest path algorithm. For example, the forward run provides one extreme value in one direction for each layout positional variable, and the backward run provides other extreme value in another direction for each layout positional variable. 
     The Boolean variable conversion module  1076  assigns Boolean variables to the layout variables. Each Boolean variable having a Boolean value is assigned to a corresponding layout variable having a numeric value. Accordingly, the Boolean variable conversion module  1076  converts layout variables to corresponding Boolean variables or Boolean variables to corresponding layout variables. 
     The implication graph generation module  1078  generates an implication graph based on layout constraints and Boolean variables. The implication graph generation module  1078  generates a Boolean implication graph based on Boolean variables having Boolean values. In addition, the implication graph generation module  1078  may generate an implication graph based on layout variables having numeric values. 
     The infeasibility determination module  1072  determines whether the set of layout constraints is infeasible. In one implementation, the infeasibility determination module  1072  includes a 2SAT solver  1082  configured to determine the infeasibility of the set of layout constraints using Boolean variables. In one aspect, the 2SAT solver  1082  computes Strongly Connected Components (SCC) of the Boolean implication graph and checks if an SCC contains a Boolean variable and its compliment in it. In case the SCC contains a Boolean variable and its compliment in it, the 2SAT solver  1082  determines the set of layout constraints is infeasible. Layout constraints containing the Boolean variables and their compliments in the SCC are identified as infeasible layout constraints. In another aspect, the infeasibility determination module  1072  uses an implication graph generated based on layout variables having numeric values for determining the infeasibility of the set of layout constraints. 
     If the set of layout constraints are determined to be infeasible, the constraint relaxation module  1075  relaxes the set of layout constraints to a feasible form. In one aspect, the constraint relaxation module  1075  relaxes the identified infeasible layout constraint for the set of layout constraints to be in the feasible form. For example, for an infeasible gridding requirement, the constraint relaxation module  1075  relaxes the gridding requirement by either locking the layout edge to its current grid value, or dropping the gridding requirement on it. Relaxing the set of layout constraints performed by the constraint relaxation module  1075  and determining whether the set of layout constraints is infeasible performed by the infeasibility determination module  1072  are iteratively performed until the set of layout constraints is feasible. 
     The output layout generation module  1035  generates the output circuit layout  1030  by solving the set of layout constraints in the feasible form from the constraint relaxation module  1075 . In one implementation, the output layout generation module  1035  includes a standard linear program solver  1032  configured to model a minimum perturbation objection function of a layout object into Boolean implications as a linear program. The output of the linear program solver  1032  is in Boolean variables that may be converted to corresponding layout variables at the Boolean variable conversion module  1076  to generate the final output layout  1030 . 
     Computing Machine Architecture 
       FIG. 9  is a block diagram illustrating components of an example machine able to read instructions from a machine-readable medium and execute them in a processor (or controller). The layout correction system  1020  is embodied as hardware, software, firmware or a combination thereof by a computer system  900 . Specifically,  FIG. 9  shows a diagrammatic representation of a machine in the example form of a computer system  900  within which instructions  924  (e.g., software) for causing the machine to perform any one or more of the methodologies discussed herein may be executed. In alternative embodiments, the machine operates as a standalone device or may be connected (e.g., networked) to other machines. In a networked deployment, the machine may operate in the capacity of a server machine or a client machine in a server-client network environment, or as a peer machine in a peer-to-peer (or distributed) network environment. 
     The machine may be a server computer, a client computer, a personal computer (PC), or any machine capable of executing instructions  924  (sequential or otherwise) that specify actions to be taken by that machine. Further, while only a single machine is illustrated, the term “machine” shall also be taken to include any collection of machines that individually or jointly execute instructions  924  to perform any one or more of the methodologies discussed herein. 
     The example computer system  900  includes a processor  902  (e.g., a central processing unit (CPU), a graphics processing unit (GPU), a digital signal processor (DSP), one or more application specific integrated circuits (ASICs), a main memory  904 , a static memory  906 , and a storage unit  916  which are configured to communicate with each other via a bus  908 . The processor  902  may include one or more processors. The storage unit  916  includes a machine-readable medium  922  on which is stored instructions  924  (e.g., software) embodying any one or more of the methodologies or functions described herein. The instructions  924  (e.g., software) may also reside, completely or at least partially, within the main memory  904  or within the processor  902  (e.g., within a processor&#39;s cache memory) during execution thereof by the computer system  900 , the main memory  904  and the processor  902  also constituting machine-readable media. 
     While machine-readable medium  922  is shown in an example embodiment to be a single medium, the term “machine-readable medium” should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, or associated caches and servers) able to store instructions (e.g., instructions  924 ). The term “machine-readable medium” shall also be taken to include any medium that is capable of storing instructions (e.g., instructions  924 ) for execution by the machine and that cause the machine to perform any one or more of the methodologies disclosed herein. The term “machine-readable medium” includes, but not be limited to, data repositories in the form of solid-state memories, optical media, and magnetic media. 
     Example Usage of the Automatic Layout Modification Tool 
     Once the design rules and grids/tracks are defined in the technology files needed by the disclosed automatic layout modification tool, the DRC correction and track snapping may be available in the layout editor. A user can launch the correction on the entire layout being edited or portions of it. The correction tool may be implemented in three modes: (1) Fix the entire layout (2) Fix the layout portion visible on the layout canvas (3) Fix the layout inside a user specified rectangular region of the visible layout. 
     Additional Configuration Considerations 
     It is noted that although the configurations as disclosed are in the context of EDA for integrated circuit design, the principles disclosed can be applied to an EDA for other hardware or software designs (e.g., printed circuit board design, mechanical structure design, construction blueprint design, 3-D printing design, and etc.) that can include locating positional values with non-uniform grids. Advantages of the disclosed configurations include efficiently identifying and solving infeasibility of set of constraints and using Boolean variables. Such usage of Boolean variables and implications enables a simple 2SAT solver to efficiently identify the infeasibility of set of constraints even with non-uniform structures. Once the infeasibilities are identified, the constraints can be systematically relaxed to obtain a feasible problem. Moreover, such usage of Boolean variables and implications allows constrained optimization problems with two variables per inequality and integrality requirements to be solved using a regular LP solver. 
     In addition, it is noted that the configurations described correspond to digital representations of physical designs, e.g., circuits manufactured on a chip. Accordingly, the disclosure herein corresponds with transformations associated with processes. 
     Throughout this specification, plural instances may implement components, operations, or structures described as a single instance. Although individual operations of one or more methods are illustrated and described as separate operations, one or more of the individual operations may be performed concurrently, and nothing requires that the operations be performed in the order illustrated. Structures and functionality presented as separate components in example configurations may be implemented as a combined structure or component. Similarly, structures and functionality presented as a single component may be implemented as separate components. These and other variations, modifications, additions, and improvements fall within the scope of the subject matter herein. 
     The various operations of example methods described herein, such as those performed by the compiler, may be performed, at least partially, by one or more processors that are temporarily configured (e.g., by software) or permanently configured to perform the relevant operations. Whether temporarily or permanently configured, such processors may constitute processor-implemented modules that operate to perform one or more operations or functions. The modules referred to herein may, in some example embodiments, comprise processor-implemented modules. 
     Similarly, the methods described herein may be at least partially processor-implemented. For example, at least some of the operations of a method may be performed by one or processors or processor-implemented hardware modules. The performance of certain of the operations may be distributed among the one or more processors, not only residing within a single machine, but deployed across a number of machines. In some example embodiments, the processor or processors may be located in a single location (e.g., within a home environment, an office environment or as a server farm), while in other embodiments the processors may be distributed across a number of locations. 
     The one or more processors may also operate to support performance of the relevant operations in a “cloud computing” environment or as a “software as a service” (SaaS). For example, at least some of the operations may be performed by a group of computers (as examples of machines including processors), these operations being accessible via a network (e.g., the Internet) and via one or more appropriate interfaces (e.g., application program interfaces (APIs).) 
     The performance of certain of the operations may be distributed among the one or more processors, not only residing within a single machine, but deployed across a number of machines. In some example embodiments, the one or more processors or processor-implemented modules may be located in a single geographic location (e.g., within a home environment, an office environment, or a server farm). In other example embodiments, the one or more processors or processor-implemented modules may be distributed across a number of geographic locations. 
     Unless specifically stated otherwise, discussions herein using words such as “processing,” “computing,” “calculating,” “determining,” “presenting,” “displaying,” or the like may refer to actions or processes of a machine (e.g., a computer) that manipulates or transforms data represented as physical (e.g., electronic, magnetic, or optical) quantities within one or more memories (e.g., volatile memory, non-volatile memory, or a combination thereof), registers, or other machine components that receive, store, transmit, or display information. 
     As used herein any reference to “one embodiment” or “an embodiment” means that a particular element, feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment. 
     Some embodiments may be described using the expression “coupled” and “connected” along with their derivatives. For example, some embodiments may be described using the term “coupled” to indicate that two or more elements are in direct physical or electrical contact. The term “coupled,” however, may also mean that two or more elements are not in direct contact with each other, but yet still co-operate or interact with each other. The embodiments are not limited in this context. 
     As used herein, the terms “comprises,” “comprising,” “includes,” “including,” “has,” “having” or any other variation thereof, are intended to cover a non-exclusive inclusion. For example, a process, method, article, or apparatus that comprises a list of elements is not necessarily limited to only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Further, unless expressly stated to the contrary, “or” refers to an inclusive or and not to an exclusive or. For example, a condition A or B is satisfied by any one of the following: A is true (or present) and B is false (or not present), A is false (or not present) and B is true (or present), and both A and B are true (or present). In addition, use of the “a” or “an” are employed to describe elements and components of the embodiments herein. This is done merely for convenience and to improve the clarity of this disclosure. This description should be read to include one or at least one and the singular also includes the plural unless it is obvious that it is meant otherwise. 
     Upon reading this disclosure, those of skill in the art will appreciate a method and system for an automatic layout modification tool with non-uniform grids using Boolean variables through the disclosed principles herein. Thus, while particular embodiments and applications have been illustrated and described, it is to be understood that the disclosed embodiments are not limited to the precise construction and components disclosed herein. Various modifications, changes and variations, which will be apparent to those skilled in the art, may be made in the arrangement, operation and details of the method and apparatus disclosed herein without departing from the spirit and scope defined in the appended claims.