REGISTER  |  SIGN IN
United States Patent5984510
Guruswamy , ; et al.November 16, 1999
Title
Automatic synthesis of standard cell layouts
Abstract
A method for automatically synthesizing standard cell layouts(170) given a circuit netlist, a template describing the layout style and a set of process design rules (136) starts by numerating an ordered sequence of physical netlists from the logical netlist(138). Next, a netlist is selected from the ordered sequence of physical netlists (140). Components are placed according to the selected physical netlist (144). The components are routed to implement interconnections specified by the netlist (154). The components are compacted (156). A next netlist is selected from the ordered sequence of physical netlists. The steps of placing, routing and compacting the components are repeated. The layout with the smallest width is selected(166). Finally, ies, contacts and vias are added and notches filled (170) to improve yield and performance of the circuit.
Inventors:Guruswamy; Mohan (Austin, TX), Dulitz; Daniel Wesley  (Port Madilda, PA), Maziasz; Robert L.  (Austin, TX), Raman; Srilata  (Austin, TX), Chiluvuri; Venkata K. R.  (Austin, TX), Berens; Andrea  (Austin, TX)
Assignee:Motorola Inc. (Austin, TX)
Appl. No.:740720
Filed:November 1, 1996
Current U.S. Class:716/2 716/9 
Current International Class:G06F 17/50 (20060101)
Field of Search:364/488,489,490,491,578
U.S. Patent Documents
4630219December 1986DiGiacomo et al.
5097422March 1992Corbin, II et al.
5463563October 1995Bair et al.
5625568April 1997Edwards et al.
5633807May 1997Fishburn et al.
5666288September 1997Jones et al.
5701255December 1997Fukui
5726902March 1998Mahmood et al.
5737236April 1998Maziasz et al.
5764533June 1998DeDood
Other References
Chao C.Chen and Shau-Lim Chow,"The Layout Synthesizer:An Automatic Netlist-to-Layout System," in Proc. 26th ACM/IEEE Design Automation Conf., Jun. 1989, pp. 232-238. .
Chong-Leong Ong, Jeong-Tyng Li and Chi-Yuan Lo, "GENAC An Automatic Cell Synthesis Tool," in Proc. 26th ACM/IEEE Design Automation Conf., Jun. 1989, pp. 239-244. .
C.W.Kapral, J.J-Y, Chen, J. Chen,J. Do, and C.R.Fawcett, "Layout Synthesis:An Automatic Cell Generator", Silicon Compiler Systems. no date, no pg #s. .
Virtuoso Layout Synthesizer (LAS) User Guide Version 4.2-Cadence Design Systems, Oct. 1991. .
M.Lefebvre and D.F.Skoll,"Picasso II:A CMOS leafe cell synthesis system," in Proc .of International Workshop on Layout Synthesis, pp. 207-219, 1992..~
Primary Examiner: Teska; Kevin J.
Assistant Examiner: Garbowski; Leigh Marie
Attorney, Agent or Firm:Hayden; Bruce E.
Parent Case Text


CROSS REFERENCE TO RELATED APPLICATIONS

This application is related to our commonly assigned copending United States patent applications entitled:

"METHOD AND APPARATUS FOR FORMING REDUNDANT VIAS BETWEEN CONDUCTIVE LAYERS OF AN INTEGRATED CIRCUIT" by Gabriel Bracha et. al., U.S. patent application Ser. No. 08/535,427 Aug. 25, 1998; filed Sep. 28, 1995, now U.S. Pat. No. 5,798,937.

"METHOD AND APPARATUS FOR DESIGNING AN INTEGRATED CIRCUIT" by Larry G. Jones et al., and U.S. Pat. No. 5,666,288 Sep. 9, 1997;

"APPARATUS AND METHOD FOR AUTOMATED TRANSISTOR AND COMPONENT FOLDING TO PRODUCE OPTIMIZED CELL STRUCTURE" by Robert Maziasz et al., and U.S. patent application Ser. No. 08/597,788 filed Feb. 7, 1996;

"APPARATUS AND METHOD FOR AUTOMATICALLY PLACING TIES AND CONNECTION ELEMENTS WITHIN AN INTEGRATED CIRCUIT" by Mohan Guruswamy et al., U.S. patent application Ser. No. 08/597,768 filed Feb. 7, 1996;

"APPARATUS AND METHOD FOR THE AUTOMATIC DETERMINATION OF A STANDARD LIBRARY HEIGHT WITHIN AN INTEGRATED CIRCUIT DESIGN" by Robert Maziasz et al., and U.S. Pat. No. 5,737,236 Apr. 7, 1998;

"AUTOMATIC LAYOUT SUBSTRATE AND WELL TIE STYLE SELECTION" by Mohan Guruswamy et. al., U.S. patent application Ser. No. 08/740,768 filed Nov. 1, 1996;

"AUTOMATIC LAYOUT TRANSISTOR PLACEMENT" by Robert Maziasz et. al., U.S. patent application Ser. No. 08/740,772 filed Nov. 1, 1996;

"AUTOMATIC ROUTING SPACE AND DIRECTION DETERMINATION" by Srilata Raman et. al., U.S. patent application Ser. No. 08/740,724 filed Nov. 1, 1996;

"AUTOMATIC LAYOUT WIRE MINIMIZATION FOR GRIDDED PORTS" by Venkata Chiluvuri et. al., U.S. patent application Ser. No. 08/740,724 filed Nov. 1, 1996;

"AUTOMATIC LAYOUT TRANSISTOR STACKING" by Robert Maziasz et. al., U.S. patent application Ser. No. 08/740,772 filed Nov. 1, 1996;

"AUTOMATIC LAYOUT STANDARD CELL ROUTING" by Srilata Raman et. al., U.S. patent application Ser. No. 08/740,721 filed Nov. 1, 1996;

"AUTOMATIC LAYOUT TIE FILLING" by Daniel Dulitz, U.S. patent application Ser. No. 08,740,771 filed Nov. 1, 1996;

"AUTOMATIC LAYOUT CONTACT AND VIA FILLING" by Daniel Dulitz, U.S. patent application Ser. No. 08/740,770 filed Nov. 1, 1996;

"AUTOMATIC LAYOUT NOTCH FILLING" by Daniel Dulitz, U.S. patent application Ser. No. 08/740,769 filed Nov. 1, 1996;

"AUTOMATIC LAYOUT I/O PORT PLACEMENT" by Srilata Raman et. al., U.S. patent application Ser. No. 08/740,723 filed Nov. 1, 1996;

"SEMICONDUCTOR DEVICE USING DIODE PLACE-HOLDERS AND METHOD OF MANUFACTURE THEREOF" by Daniel R. Cronin, et. al., U.S. patent application Ser. No. 08/740,766 filed Nov. 1, 1996.
Claims

We claim:
1. A method of synthesizing a layout of a circuit from a logical netlist and a set of constraints,
said method comprising the steps of:
a) deriving a plurality of physical netlists from the logical netlist;
b) following step (a) enumerating an ordered sequence of physical netlists from the plurality of physical netlists, wherein the ordered sequence of physical netlists is determined by an estimated physical dimension of the cell layout;
c) following step (b), selecting a first netlist from the ordered sequence of physical netlists as a selected physical netlist;
d) placing a plurality of layout elements according to the selected physical netlist and the set of constraints,
e) routing the plurality of layout elements to implement a plurality of interconnections specified by the logical netlist,
f) testing for a termination condition, and
g) if the termination condition in step f) was not met, selecting a next netlist from the ordered sequence of physical netlists as the selected physical netlist and repeating steps d) through g).

2. The method of claim 1 which further comprises:
h) compacting the plurality of layout elements according to the set of constraints.

3. The method of claim 2 wherein step h) comprises the following substeps:
1) compacting the plurality of layout elements preferentially in a vertical dimension,
2) if a height of a cell produced in substep (1) is greater than a standard cell height, selecting a next netlist from the ordered sequence of physical netlists as the selected physical netlist and repeating steps d) through h),
3) compacting the plurality of layout elements preferentially in a horizontal dimension,
4) if a height of the cell produced in substep (3) is less than or equal to the standard cell height and a width of the cell produced in substep (3) is less than a width of the cell produced in substep (1), selecting a cell produced in substep (3) as a compacted cell, and
5) otherwise selecting a cell produced in substep (1) as the compacted cell.

4. The method of claim 3 further comprising the following substep:
6) adding location constraints to individual layout elements to create a standard cell.

5. The method of claim 4, wherein substep (6) comprises constraining a cell height to the standard cell height.

6. The method of claim 5, wherein substep (6) further comprises constraining all layout elements on a well layer to lie within the well height from a defined location relative to an edge of a cell.

7. The method of claim 3 wherein substep (1) comprises the steps of:
compacting the plurality of layout elements in a vertical dimension and subsequently compacting the plurality of layout elements in a horizontal dimension.

8. The method of claim 3 wherein substep (3) comprises the steps of:
compacting the plurality of layout elements in a horizontal dimension, and subsequently compacting the plurality of layout elements in a vertical dimension.

9. The method of claim 3, further comprising:
i) receiving an effort level, wherein:
substeps (2) through (4) are not performed when the effort level is low.

10. The method of claim 2 which further comprises:
i) Placing one of the plurality of layout elements to implement a subset of interconnections specified by the logical netlist.

11. The method of claim 10 wherein step (h) comprises the steps of:
1) adding one or more of the plurality of layout elements to interconnect adjacent layout elements on a same net,
2) adding one or more of the plurality of layout elements that allow a router to interconnect layout elements that are on a layer not used by the router, and
3) adding one or more of the plurality of layout elements to interconnect high priority layout elements with a minimum wire length and a minimum number of layer changes.

12. The method of claim 2 wherein steps d, e, f, and h are performed on a persistent layout database.

13. The method of claim 1 which further comprises:
h) Placing one of the plurality of layout elements to implement a subset of interconnections specified by the logical netlist.

14. The method of claim 1 which further comprises:
h) Creating in a persistent database a plurality of layout objects specified in the selected physical netlist.

15. The method of claim 1 wherein step (d) comprises the steps of
1) automatically placing an abstract representation of a primary layout object in order to optimize a placement of the primary layout object subject to an estimated location of a secondary layout object and an estimated location of a tertiary layout object,
2) automatically placing an abstract representation of the secondary layout object in order to optimize a placement of the secondary layout object subject to an actual location of the primary layout object and the estimated location of the tertiary layout object, and
3) automatically placing an abstract representation of the tertiary layout object in order to optimize a placement of the tertiary layout object subject to the actual location of the primary layout object and an actual location of the secondary layout object.

16. The method of claim 15 wherein:
primary layout objects comprise active devices,
secondary layout objects comprise ports and contacts, and
tertiary layout objects comprise antenna diodes and well and/or substrate ties.

17. The method of claim 1, wherein step (d) comprises:
placing a layout element so that a cell height is equal to the standard cell height.

18. The method of claim 17, wherein step (d) further comprises placing all layout elements on a well layer within the well height from a defined location relative to an edge of a cell.

19. The method of claim 18, wherein substrate and well ties are added to enhance yield of the layout.

20. The method of claim 18, wherein redundant layout elements are added to enhance yield of the layout.

21. The method of claim 18, wherein rows of polysilicon lines are added to enhance yield of the layout.

22. The method of claim 18, wherein layout elements are added to eliminate notches in the layout.

23. The method of claim 1, wherein step (e) is performed by an area router.

24. The method of claim 1 wherein steps (d) and (e) are performed on a persistent layout database.

25. The method of claim 24 wherein:
the persistent layout database contains:
a geometric boundary of each layout element,
a type of each layout element, and
a plurality of sets of layout elements, wherein each set comprises layout elements that will be interconnected to each other in a subsequent step.

26. The method of claim 1, comprising the additional step of:
h) Adding layout elements to increase yield and performance of a final layout.

27. The method of claim 1, wherein step (b) comprises enumerating a plurality of foldings of a logical netlist.

28. The method of claim 1, wherein the termination condition of step (g) is that no untried physical netlist could be narrower than a cell already produced.

29. The method of claim 1, wherein the termination condition of step (g) is that a cell no taller than a standard cell height has been produced.

30. The method of claim 1 further comprising the steps of:
h) generating a transistor placement file from the layout;
i) creating a set of one or more masks from the transistor placement file; and
j) fabricating a plurality of integrated circuits from the set of one or more masks.

31. A method of synthesizing a layout for a circuit from:
a physical netlist and
a plurality of high level constraints, said method comprising the steps of:
a) Enumerating an ordered sequence of sets of constraints from the plurality of high level constraints;
b) Following step (a) selecting a first set of constraints from the ordered sequence of sets of physical constraints as a selected set of constraints;
c) Placing a plurality of layout elements according to a logical netlist and the selected set of constraints,
d) Routing the plurality of layout elements to implement a plurality of interconnections specified by the physical netlist,
e) Testing for a termination condition, and
f) If the termination condition in step (e) was not met, Selecting a next set of constraints from the ordered sequence of sets of constraints as the selected set of constraints and repeating steps (c) through (f).

32. The method of claim 31, wherein a constraint enumerated in step (a) is a constraint on a height or a width of a layout.

33. The method of claim 31, wherein at least two of the sets of constraints enumerated in step (a) differ in a number of rows in which layout elements may reside.

34. A data processing system for synthesizing a layout of a circuit from:
a logical netlist and
a set of constraints, said data processing system comprising:
a) deriving a plurality of physical netlists from the logical netlist;
b) following step (a), enumerating an ordered sequence of physical netlists from the plurality of physical netlists, wherein the ordered sequence of physical netlists is determined by an estimated physical dimension of the cell layout;
c) means for selecting a first netlist from the ordered sequence of physical netlists as a selected physical netlist following step (b);
d) means for placing a plurality of layout elements according to the selected physical netlist and the set of constraints,
e) means for routing the plurality of layout elements to implement a plurality of interconnections specified by the logical netlist,
f) means for testing for a termination condition, and
g) if the termination condition in means (f) was not met, means for selecting a next netlist from the ordered sequence of physical netlists as the selected physical netlist and repeating means (d) through (g).

35. Computer software for synthesizing a layout of a circuit from:
a logical netlist and
a set of constraints, said computer software comprising:
a) deriving a plurality of physical netlists from the logical netlist;
b) following step (a), enumerating an ordered sequence of physical netlists from the plurality of physical netlists, wherein the ordered sequence of physical netlists is determined by an estimated physical dimension of the cell layout;
c) a set of computer instructions for following step b, selecting a first netlist from the ordered sequence of physical netlists as a selected physical netlist;
d) a set of computer instructions for placing a plurality of layout elements according to the selected physical netlist and the set of constraints,
e) a set of computer instructions for routing the plurality of layout elements to implement a plurality of interconnections specified by the logical netlist,
f) a set of computer instructions for testing for a termination condition, and
g) a set of computer instructions for if the termination condition in set (f) was not met, selecting a next netlist from the ordered sequence of physical netlists as the selected physical netlist and repeating sets (d) through (g).

36. A computer readable medium containing the computer software in claim 35 encoded in a machine readable format.

37. A method of manufacturing the computer readable medium in claim 36 which comprises:
encoding the computer software in machine readable format on the computer readable medium.

38. A method of selecting a physical netlist for synthesizing a layout of a circuit from a logical netlist said method comprising the steps of:
a) deriving a plurality of physical netlists from the logical netlist;
b) following step (a), enumerating an ordered sequence of physical netlists from the plurality of physical netlists, wherein the ordered sequence of physical netlists is determined by an estimated physical dimension of the cell layout
c) following step (b), selecting a first netlist from the ordered sequence of physical netlists as a selected physical netlist.
Description
TECHNICAL FIELD OF THE INVENTION

This invention relates generally to the design and manufacture of integrated circuitry and more particularly to an apparatus and method for producing optimized cell structures.

BACKGROUND OF THE INVENTION

A common method of designing an integrated circuit (IC) in a semiconductor design requires that an integrated circuit designer first provide a library of computer stored circuit cells and a behavioral circuit model describing the functionality of the integrated circuit. The circuit cells typically include fundamental logic gates such as OR, NAND, NOR, AND, XOR, inverter, and like logical cells with an array of logic gate sizes. These cells also include sequential circuit elements such as latches and flip-flops for memory requirements. Generally, the library of computer stored circuit cells are generated by a layout designer manually. Because this process is time consuming and error prone, prior art methods and apparatus have been developed to automate this procedure.

FIG. 1 illustrates a methodology and apparatus implemented in these prior art systems. Typical prior art implementations include the Virtuoso Layout Synthesizer (LAS) tool from Cadence, the Auto Layout tool from Mentor Graphics, the Custom Cell Synthesizer (CCS) tool from MCC, and a Cadabra tool. The methodology implemented by prior art implementations will now be discussed in greater detail and with reference to FIG. 1.

A prior art implementation 10 includes step 12 whereby an external user provides a netlist and template. The netlist comprises a set of circuit primitives such as transistors and diodes, their sizes, and interconnections. The template describes the physical form of a standard circuit cell. The template may contain cell height, supply rail size, etc.

Next, in step 14, components of the netlist are placed in an appropriate location. Each of the components is then connected to one another in channel routing step 16. A resulting layout is subsequently compacted in step 18. Lastly, a layout designer is required to determine whether a resulting layout meets the template specified in initial step 12. Thus, in step 19, a layout designer must determine whether or not a cell height is met, whether there is proper density among the elements of the layout, and whether well height (abutment) constraints are met. Furthermore, if the layout designer determines that these constraints are not met, the layout designer must determine which parameters of the template specified in step 12 must be modified in order to generate a compliant layout. This often requires that the layout must be hand edited to meet these constraints. Each of the steps of the prior art implementation will now be discussed in greater detail.

In the first step 12, in which an external user provides a netlist and template, prior art implementation required that a physical netlist, and not a logical netlist, be provided. A physical netlist is one in which there is a one-to-one correspondence between devices specified in the netlist and the transistors implemented in a final layout. A physical netlist is different than a logical netlist which only specifies a function to be performed and is not optimized to meet the template requirements. Stated another way, a physical netlist requires user optimization before being provided to a next step in the prior art component placement step (step 14).

Because user optimization, or hand drafted optimization, is required, prior art implementations require a significant amount of time to simply generate one physical layout. In a slight improvement over the previously described prior art techniques, some prior art implementations provide semi-automatic means for translating logical netlists into physical netlists. However, even these slight improvements require user direction to specify a maximum transistor size. This user direction requirement again adds additional time to the layout process and introduces an increased likelihood in layout errors. As well, these prior art techniques have the undesired side effect of creating unnecessary interconnects between nodes guaranteed to be at a same electrical potential because of a manner in which a physical netlist is generated by such techniques.

In step 14 of the prior art implementation, the netlist components are placed in a two dimensional array to minimize certain cost metrics, where the cost metric is a quality indicator for the placement. Generally, a two-dimensional array is comprised of one row of N-type transistors and one row of P-type transistors. Typical cost metrics include wire length and cell height and width estimates. While a two-dimensional array is generally used, the two-dimensional array does not always give optimal results for each type of netlist. For example, because of a linear flow implemented within most prior art implementations, a cell placement selected during execution of step 14 is never modified automatically regardless of its effectiveness in satisfying a template requirement. Also, the prior art does not perform vertical alignment of transistors of the same type (P or N) in order to minimize wire length. Furthermore, prior art implementations tend to emphasize the minimization of interconnection lengths between the transistors forming the cell, but not the Channel Density (defined below). It should be noted that Channel Density should be minimized to minimize cell height. By minimizing interconnection length, prior art techniques fail to minimize a height of the cell.

In addition to the disadvantages delineated above, the method by which prior art implements step 14, component placement, also has several drawbacks. Included in these drawbacks is a method by which prior art places ties in the layout to satisfy latch-up rules. It should be noted that after transistors are placed, prior art implementations must place "merged ties" to connect a source or drain of the transistor to a power or ground source supply. Prior art implementations are only able to place ties at the certain specified locations and are not able to implement ties at optimal locations. Furthermore, it should be noted that even the requirement that the ties be placed at certain locations and provide certain connections between a transistor and a supply source utilizes only an ad hoc process which provides no optimization.

In addition to placing ties, prior art implementations also place ports during step 14. During the port placement step, an area in a cell is reserved to allow the cell to communicate with other cells by providing via sites or another form of interface. As with the tie placement operations, prior art implementations do not optimize placements of ports to provide maximum area utilization. Such port placement step is critical because if the port placement step is performed in an inefficient manner, block area routing will be adversely affected.

Additionally, in recent years, antenna diodes are being implemented by manual layout insertion to provide a contact from a metal layer to a Diffusion layer of a device for manufacturing purposes. This contact provides a path for charge generated in long metal lines during manufacturing to be dissipated without damaging a transistor gate or other circuit implemented on a semiconductor substrate. No prior art techniques currently available provide a method for automatically placing antenna diodes using computer software tools to create a cell layout.

In next step 16, interconnects between components are routed by the prior art implementations. Most prior art techniques implement a channel routing methodology which reflects an attempted solution to a classic layout optimization problem which has been studied extensively. Channel routing is a methodology implemented by prior art systems in which the channel is defined to be a region between a row of N-type transistors and P-type transistors. In performing routing between the two types of transistors, the channel routing implemented by prior art implementations fails to effectively utilize the region lying outside the channel between the two transistors. For example, the region on top of transistors could be used to route metal wires, and the region below the metal supply rails could be used for polysilicon connections. This is not done in the prior art. Additionally, in prior art implementations, the routing direction for each layer is predetermined and may not be modified during channel routing step 16. This fixed routing direction leads to one of the main disadvantages of using a channel router because it results in an increased number of contacts and vias that have adverse effects on area, electrical performance, and yield. Note that some prior art implementations augment channel routing with various ad hoc heuristic methods. However, these fail to overcome the fundamental disadvantage noted above.

In additional to channel routing, some prior art implementations implement an area routing technique. Area routing involves using an entire area of the layout to connect the components and does not limit it to a transistor channel. While the second prior art technique may provide more optimal results, prior art implementations have failed to provide a good solution for selectively increasing an area in which the routing may fail. Additionally, in prior art implementations of area routing, a routing direction is fixed for each layer. As with the channel routing implementations, this fixed directionality adversely affects the optimal nature of the routing operation.

After components are placed and interconnects are routed, layout compaction step 18 is implemented. While most prior art implementations include a layout compaction step, this step is not provided to optimize a well height and a cell height requirement. Some prior art implementations simply ignore the well height requirement problem, while other prior art implementations have attempted to provide well height support by implementing a fixed rectangular well region during a layout compaction step. However, this second technique is not optimal because it limits a height of each of the N-type and P-type transistors. If height requirements are not exceeded, a resulting circuit will not be optimal and will require a greater amount of area to implement. In addition to not adequately providing support for well height requirements, prior art implementations also fail to make efforts to compact a cell layout differently to obtain a narrower cell within a standard cell height.

In other prior art implementations, a two-dimensional compaction operation is implemented. In this process, both the height and the width of the cell are compacted simultaneously. While this methodology may provide a more optimal result, it is computationally intensive and therefore, is unable to optimize larger standard cells. Furthermore, an external user is unable to explore additional options because of the longer run time resulting from the computationally intensive procedure. Therefore, the user is often unable to explore additional placement and routing options which may prove to be optimal. Another drawback of the second implementation of a layout compaction step is that it requires a layout to be sub-divided into columns prior to the compaction step. While this procedure works for current placements of transistors, it is infeasible to use where the transistor placement is modified in a certain manner. For example, when the placement consists of both horizontal and vertical alignments of transistors, the two-dimensional compaction process will result in an erroneous compaction operation. Stated another way, the second two dimensional compaction methodology is not a general purpose compaction procedure.

Finally, after prior art implementations have been used to place components, route connections between the components, and compact that layout, a layout designer is required to inspect the layout and determine in an ad hoc manner whether the layout satisfies the template specified in step 12 and whether the layout is of good quality. For example, in step 19, the layout designer must determine whether or not cell and well height requirements are met, whether port placement is optimized, whether there is good density among the components, and whether or not an abutment requirement is met. Furthermore, the layout designer must determine whether or not the resulting layout satisfies all design rules. If any of these requirements are not satisfied, the layout designer must determine which input to the template must be modified to achieve certain goals. For example, such goals may include a smaller cell height or a cell which has different port placements. Furthermore, layout designers are unable to change routing direction or Tie Style unless they chose to do so manually using a layout editor. Lastly, it should be noted that in some prior art implementations, even steps 14, 16, and 18 are not automatic and the layout designer must come in at each point and make changes to control each tool. This hand editing step requires layout expertise and increases a latency related to a layout development time.

Therefore, it is desirable to have a methodology that may produce standard cell layouts in a fully automatic manner where the resulting layout complies with design rules and the required template, and has a good density.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram that illustrates a cell layout generation system in accordance with a prior art implementation;

FIG. 2 is a block diagram that illustrates the cell layout generation system in accordance with one embodiment of the present invention;

FIG. 3 is a block diagram that illustrates a design flow in accordance with one embodiment of the present invention;

FIG. 4 is a flowchart that illustrates a methodology for generating and laying out standard cells in accordance with the cell generation system of FIG. 2;

FIG. 5 is a block diagram that illustrates integrated circuit fabrication in accordance with one embodiment of the present invention;

FIG. 6 is a block diagram that illustrates a General Purpose Computer;

FIG. 7 is a flowchart that illustrates component placement in accordance with a preferred embodiment of the present invention;

FIG. 8 is a flowchart that illustrates component placement in accordance with a second embodiment of the present invention;

FIG. 9 is a block diagram that illustrates layout compaction in accordance with one embodiment of the present invention;

FIGS. 10 through 12 are flowcharts that illustrate Abstract Active Device Placement 172 in accordance with one embodiment of the invention illustrated in FIG. 7;

FIGS. 13 and 14 are block diagrams that illustrate channel routing and Channel Routing Density in accordance with one embodiment of the invention;

FIGS. 15 and 16 are flowcharts that illustrate Abstract Active Device Placement 172 in accordance with an alternative embodiment of the invention illustrated in FIG. 7;

FIGS. 17 and 18 are circuit layouts illustrating a cost function in accordance with the method of FIGS. 10 et seq.;

FIG. 19 is a flowchart that illustrates the operation of Abstract Port Placement shown in step 174 in FIG. 7;

FIG. 20 is an example illustrating the cost factor of determining horizontal overlap of P and N-net spans in accordance with the method of FIG. 19;

FIG. 21 is a cell layout 2620 showing the concept of "staggering" in connection with step 2612 and 2614 of FIG. 19;

FIGS. 22 and 23 are different views of an illustrative port and Antenna Diode connected by a Metal-1 wire;

FIG. 24 is a flowchart that illustrates the operation of Abstract Diode Placement shown in step 176 in FIG. 7;

FIG. 25 is a block diagram showing a sample layout used to illustrate the operation of method of FIG. 24;

FIG. 26 is a transistor level circuit layout that illustrates what can happen when diode placement is performed after compaction;

FIG. 27 is a transistor level circuit layout of a standard cell in which antenna diodes have been added by operation of the diode placement modules illustrated in FIG. 24;

FIGS. 28, 29, 30, 31, and 33 are flowcharts that illustrate routing steps 152 and 154 of one embodiment of the invention illustrated in FIG. 4;

FIG. 32 is a circuit layout that illustrates operation of Expand Routing Channel functionality illustrated in FIG. 31;

FIGS. 34 through 37 are Standard cell layouts that illustrate the layout compaction process.

FIG. 38 is a flowchart that illustrates the operation of compaction, step 156.

FIG. 39 is a flowchart that illustrates operation of compaction in a selected direction of step 2504.

FIG. 40 is a flowchart that illustrates the operation of Minimize Wire Length function, step 2518.

FIG. 41 is a flowchart that illustrates Find Local Slack routine in step 2532.

FIG. 42 is a flowchart that illustrates the operation of the Calculate On-Grid Slack routine in step 2538.

FIG. 43 is a layout example for illustrating graph representation of layout in step 2512.

FIG. 44 is a Constraint-Graph representation of layout shown in FIG. 43, steps 2512, and 2514.

FIG. 45 is a table that illustrates the vertex weights and grid requirements corresponding to the vertices shown in FIG, 44.

FIG. 46 through 48 are simple layouts that illustrate some of the advantages of moving On-Grid elements during step 2518.

FIGS. 49 and 50 are Standard cell layouts that illustrate the benefits of wire minimization with On-Grid Ports.

FIG. 51 is a flowchart that illustrates notch, tie, and contact filling in accordance with the present invention;

FIG. 52 is a flowchart that illustrates notch filling in accordance with the present invention;

FIG. 53 is a diagram that illustrates layout to shape conversion in accordance with the present invention;

FIG. 54 is a flowchart that illustrates finding blockages step 2026 in FIG. 52;

FIG. 55 is a diagram that illustrates finding blockages step 2026 in FIG. 52;

FIG. 56 through 59 are diagrams that illustrate a series of resultant shapes generated from a series of individual shapes in accordance with the present invention;

FIG. 60 is a layout diagram used to define further terminology consistent with method 2024 illustrated in FIG. 52;

FIG. 61 is a flowchart that illustrates filling simple notches in accordance with the present invention;

FIG. 62 is a layout diagram that illustrates the effects of the simple notch filling method 2082 in FIG. 61;

FIG. 63 is a flowchart that illustrates filling straits in accordance with the present invention;

FIG. 64 is a diagram that illustrates the operation of strait filling illustrated in FIG. 63;

FIG. 65 is a flowchart that illustrates isthmus filling in accordance with the present invention;

FIG. 66 is a diagram that illustrates the operation of isthmus filling illustrated in FIG. 65;

FIG. 67 is a flowchart that illustrates island filling in accordance with the present invention;

FIG. 68 is a flowchart that illustrates a method of calculating a derived blockage;

FIG. 69 is a diagram that illustrates a case in which derived blockages are beneficial;

FIG. 70 is a flowchart that illustrates method 2013 in accordance with the present invention;

FIG. 71 is a diagram that illustrates a series of shapes derived from a specific semiconductor layout;

FIG. 72 is a flowchart that illustrates converting layouts into power shapes;

FIG. 73 is a diagram that illustrates the intersection of two layers;

FIG. 74 is a flowchart that illustrates finding basic blockages in accordance with the present invention;

FIG. 75 is a diagram that illustrates the implementation of the method of FIG. 74 as relating to various shapes;

FIG. 76 is a flowchart that illustrates in greater detail a portion of FIG. 70;

FIG. 77 is a flowchart that illustrates in greater detail a portion of FIG. 70;

FIG. 78 is a diagram that illustrates a sequence of shapes used in implementation of the method of FIG. 77 as relating to various shapes;

FIG. 79 is a flowchart that illustrates in greater detail a portion of FIG. 76;

FIG. 80 is a flowchart that illustrates in greater detail a portion of step 2013 of FIG. 79;

FIG. 81 is a diagram that illustrates a representative implementation of FIG. 80;

FIG. 82 is a flowchart that illustrates in greater detail a portion of FIG. 70 for finding and removing long ties;

FIG. 83 is a diagram that illustrates the effects of implementing a portion of the method of FIG. 82;

Prior art FIG. 84 is a cross sectional view of a covered via;

Prior art FIG. 85 is a cross sectional view of an uncovered via;

Prior art FIG. 86 is a cross sectional view of an uncovered via that is misaligned;

FIG. 87 is a flowchart that illustrates a method of filling contacts and vias in accordance with the present invention;

FIG. 88 is a flowchart that illustrates an expanded portion of the flow of FIG. 87;

FIG. 89 is a flowchart that illustrates the generation of an Existing Shape in accordance with the method of FIG. 88;

FIG. 90 is a diagram that illustrates the generation of a Top Invalid Shape in accordance with the method of FIG. 88;

FIG. 91 is a diagram that illustrates the generation of an Top Valid shape in accordance with the method of FIG. 88;

FIG. 92 is a diagram that illustrates the generation of a Bot Invalid Shape in accordance with the method of FIG. 88;

FIG. 93 is a flowchart that illustrates a portion of the flow of FIG. 87 in expanded form;

FIG. 94 is a diagram that illustrates the generation of a Might Cut shape in accordance with the method of FIG. 88;

FIG. 95 is a diagram that illustrates the generation of a Can Cut shape in accordance with the method of FIG. 88;

FIG. 96 is a diagram that illustrates the generation of a Bot Valid shape in accordance with the method of FIG. 88;

FIG. 97 is a flowchart that illustrates a portion of the flow of FIG. 87 in expanded form;

FIG. 98 is a cross sectional view of a CMOS transistor;

FIG. 99 is a flowchart that illustrates tie placement within an integrated circuit in accordance with one embodiment of the invention;

FIG. 100 illustrates a portion of an integrated circuit that has had its ties placed in accordance with the method of FIG. 99;

FIG. 101 is a flowchart that illustrates an alternative method for automatically placing ties within an integrated circuit;

FIG. 102 illustrates examples of several possible spacing rules in accordance with the method of FIG. 99;

FIG. 103 is a diagram showing a sample standard cell layout with different Substrate and Well Tie Styles;

FIG. 104 is a flowchart that illustrates Substrate and Well Tie Style Selection in accordance with the method of FIG. 4;

FIG. 105 illustrates the tie style selection matrix in the preferred embodiment.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENT

The present invention provides an apparatus and method for synthesizing mask geometry for standard cells and macro cells from a logical circuit netlist given a standard-cell style and technology parameters (design rules). By using the automatic synthesis of layout for standard cells from a logical netlist, generation of specialized libraries tailored to the requirements of individual design projects and specific standard-cell blocks may be rapidly implemented. Additionally, the use of libraries with gate sizes that closely match circuit needs results in more efficient area, power, and speed optimizations. Furthermore, this automatic synthesis allows for the generation of designs using new process technologies more rapidly. Such rapid turnaround is increasingly important in the semiconductor industry where the timing of market introductions is often critical.

In a following description of the present invention, a system environment in which the invention will be implemented will first be discussed. This discussion will be followed by a general description of the cell layout generator of the present invention. Subsequently, selected topics which further clarify portions of the cell layout generator will be described in greater detail. The topics are organized as follows:

I. Cell Layout Generation System Environment

II. Overview of Cell Layout Generator

III. Selected Topics

A. High Density Transistor Placement

B. Transistor Stacking

C. Input/Output Port Placement

D. Diode Placement

E. Performance Driven Routing Flow

F. Routing Space and Direction Determination

G. Wire Minimization for Gridded Ports

H. Notch, Tie, and Contact Filling Flow

I. Notch Filling

J. Tie Filling

K. Contact and Via Filling

L. Automatic Tie Placement

M. Substrate and Well Tie Style Selection

IV. Conclusion

I. Cell Layout Generation System Environment

FIG. 2 is a block diagram that illustrates a layout generation system 100 in accordance with one embodiment of the present invention. As illustrated in FIG. 2, process design rules, stored in a disk file 102, are provided to a cell layout generator 110. Additionally, a netlist of cells stored in disk file 104, and a library style template stored in disk file 106 are also provided to cell layout generator 110. Cell layout generator 110 processes each of the parameters and values to generate layout 112. To provide a basic background for the present invention, each of the input process design rules, netlist of cells, and library style template will be described in further detail.

Process design rules in disk file 102 include a minimum width of the different layers used in a layout of a cell as well as spacing requirements associated with those layers. The process design rules also specify electrical characteristics such as resistance and capacitance for each layer. The netlist of cells stored in data file 104 includes a list of transistor and signals connected to each of those transistors. Furthermore, the netlist of cells stored in disk file 104 specifies the size of transistors implemented in the layout and the input/output (I/O) signal ports. It should be noted that the list of transistors specified in the netlist of cells represents a logical, and not a physical, netlist. Thus, the present invention only requires that the connections which should be made be specified, and does not require an actual physical netlist. The library style template stored in disk file 106 includes required cell height, required well height, and the dimensions and locations of the supply sources, or rails, of the cell layout. Additionally, there are other styles specified in the template; however, these are not specified herein for brevity's sake and it should be realized that additional styles may be implemented even though they are not discussed in detail herein.

Before describing the functionality of cell layout generator 110 in greater detail, a system in which cell layout generator 110 is implemented will be described. This system is illustrated in greater detail in FIG. 3. The content of a generic cell library stored in a disk file 134 and a register transfer level (RTL) description, also known as a behavioral description, stored in disk file 132 are provided to a logic synthesis tool 114. The generic cell library 134 provides descriptions of the basic building blocks of any design. Logic synthesis tool 114 generates a gate level description of the circuit indicated in the RTL description. Together with the RTL description, logic synthesis tool 114 generates a gate level block netlist 115. Block netlist 115 uses the cells provided by the generic cell library stored in disk file 134 to implement the behavior of the circuit to be designed. Block netlist 115 is provided to a library definition tool 116. In library definition tool 116, portions of block netlist 115 are combined to form a new hybrid set of cells. The new set of cells is represented by a hybrid netlist referred to as an optimized block netlist 117. Optimized block netlist 117 is provided to a place and route, parasitic extraction, and timing verification tool 128. From library definition tool 116, the optimized block netlist 117 is provided to a global size optimization tool 118. In global size optimization tool 118, the size of the individual transistors in the optimized block netlist is altered to satisfy the performance requirements specified in the RTL description provided by disk file 132. Global size optimization tool 118 subsequently provides a size netlist 119 to a power rail optimization tool 120. Power rail optimization tool 120 decides the dimension of the supply rail for each of the cells to be generated based on the current requirements for the optimized block netlist 117. The power calculated by power rail optimization tool 120 together with a sized netlist generated by global size optimization tool 118 are both provided to cell pitch optimization tool 122 to determine an optimal cell height. Once the optimal cell height is known together with the sized netlist, cell layout generation may begin.

The cell layout generation tool 110 is illustrated further in FIG. 4 and will subsequently be described in greater detail. After a layout is generated by cell layout generator 110, resistance and capacitance of all electrical nodes within that layout are extracted by extraction tool 124. This extracted information is provided to characterization tool 126 where the power consumption and performance of each circuit in the block netlist 117 is determined and provided as an optimized block library 127. The optimized block library 127 is provided to Place and Route, Parasitic Extraction, and Timing Verification tools 128. Place and Route, Parasitic Extraction, and Timing Verification tools 128 generate a physical implementation of a desired circuit. The physical design is stored in disk file 130. From tools 128, net parasitics are extracted and provided to a global size optimization tool 118. Global size optimization tool 118 uses the net parasitics to resize a netlist to further optimize performance of the physical design 130.

FIG. 5 is a block diagram that illustrates integrated circuit fabrication utilizing the cell layout generation tool 110 further illustrated in FIG. 4. The cell layout generator 110 uses cell netlists 104 to generate a standard cell library 92. Each standard cell library 92 member was generated from one of the cell netlists 104. A high level design tool 94 is used to generate a RTL circuit description 132. A logic synthesis tool 114 combined with a Place and Route, Parasitic Extraction, and Timing Verification tools 128 generates a physical design 130 from the standard cell library 92 and the RTL description 132.

The physical design file 130 includes integrated circuit dimensions, element dimensions, and element locations within the integrated circuit. The physical design file 130 locates elements and connections within a two-dimensional substrate area of an integrated circuit die. Preferably, the physical design file 130 includes physical structure for performing the functions of an integrated circuit design from which the physical design file was derived. The physical design 130 is converted 96
into a set of masks 97 corresponding to the layers in the physical design file 130. The masks 97 are used to fabricate 98 integrated circuits 99. Note that the elimination of steps 116 through 126 between Logic Synthesis 114 and Place and Route, etc. tools 128 from FIG. 3 is an alternate embodiment that does not provide the benefits disclosed in commonly assigned copending patent U.S. patent application Ser. No. 08/426,211 entitled: "METHOD AND APPARATUS FOR DESIGNING AN INTEGRATED CIRCUIT" by Larry G. Jones et al.

The methods taught herein are used to generate CAD (computer aided design) data files which contain information regarding the integrated circuit and placement of gates, transistors, and the like in the integrated circuit. These files are then used to form lithographic masks which are then used to form a plurality of integrated circuits on a plurality of wafers using an integrated circuit fabrication facility. The design phase is taught in "Principles of CMOS VLSI Design: A Systems Perspective", by N. H. E. Weste and K. Eshragian in the the VLSI Series by Addison-Wesley, 1985. The mathematical basis for many of the techniques are taught in "Combinatorial Algorithms for Integrated Circuit Layout" by Thomas Lengauer, copyright 1990, published by John Wiley and Sons. Fabrication techniques are outlined in "Silicon Processing for the VLSI Era, Volume 1: Process Technology", by Wolf and Tauber, copyright 1986, published by Lattice Press. Process integration is taught by the second book in the series: "Silicon Processing for the VLSI Era, Volume 2: Process Integration", by Wolf, copyright 1990, published by Lattice Press.

FIG. 6 is a block diagram illustrating a General Purpose Computer 20 used to execute cell layout generator 110. The General Purpose Computer 20 has a Computer Processor 22, and Memory 24, connected by a Bus 26. Memory 24 includes relatively high speed machine readable media such as DRAM, SRAM, ROM, FLASH, EEPROM, and bubble memory. Also connected to the Bus are Secondary Storage 30, External Storage 32, output devices such as a monitor 34, input devices such as a keyboard (with mouse) 36, and printers 38. Secondary Storage 30 includes machine readable media such as hard disk drives, magnetic drum, and bubble memory. External Storage 32 includes machine readable media such as floppy disks, removable hard drives, magnetic tape, CD-ROM, and even other computers, possibly connected via a communications line. The distinction drawn here between Secondary Storage 30 and External Storage 32 is primarily for convenience in describing the invention. As such, it should be appreciated that there is substantial functional overlap between these elements. Executable versions of computer software 33, such as the cell layout generator 110 can be written to, and later read from External Storage 32 and loaded for execution directly into Memory
24, or stored on Secondary Storage 30 prior to loading into Memory 24 and execution. Also preferably stored on either Secondary Storage 30 or External Storage 32 are Process Design Rules 102, Cell Netlists 104, Library Style Templates 106, Optimized Block Library 127, Physical Design file 130, Generic Library 134, RTL Description file 132, and Standard Cell Library 92.

II. Overview of Cell Layout Generator

FIG. 4 illustrates cell layout generator 110 of the present invention in greater detail. In first step 136, a netlist, a layout template and process design rules are provided from an external memory source (not illustrated herein). The netlist, layout template and process design rules are the same as those previously described as described in FIGS. 2 and 3. Furthermore, it should be noted that cell layout generator 110 of the present invention includes additional template constraints which are not supported by prior art implementations. These new template constraints include port location designation, substrate and well tie styles, and diode styles.

Next, in step 138, a physical representation of the netlist is enumerated. In step 138, the logical input netlist provided in step 136 is transformed into several physical netlists which are functionally similar, but structurally distinct. For example, the physical netlist may include a different number of transistors or connections. The logical input netlist may be transformed into the physical netlist by a process commonly known as transistor folding, or by unfolding, or by other processes known in the art. Each of these folded netlists will produce a different cell layout structure. These folded netlists are then ordered based on increasing estimated cell widths and processed by succeeding stages in cell layout generator 110.

Furthermore, when physical representations of the netlist are enumerated, the present invention uniquely allows for vertical stacking of the same type of transistor. For example, two N-type transistors may be stacked upon each other and then be followed by a P-type transistor. Additionally, both N-type and P-type transistors may be vertically stacked. Therefore, it should be noted that two N-type transistors may be stacked with two P-type transistors. Furthermore, it should be noted that two N-type transistors may be stacked between P-type transistors, or vice versa. This ability to vertically stack transistors of the same type increases the flexibility of the present invention in laying out cell structures. The greater flexibility translates to greater density and more narrow cells which are often sought in cell layout designs.

In subsequent step 140, a physical implementation is selected by cell layout generator 110. Once each of the folded netlists are ordered, cell layout generator 110 selects a cell structure which is most likely to comply with a specified cell height as determined by the template input in step 136. Cell layout generator 110 moves from a first one of the folded netlist to a next in the order established in step 138 until the best compliant layout is determined.

In a next step 142, database objects are created by generating an actual physical layout of the transistors specified by the folded netlist. It should be noted that there are many different types of objects which may be created. For example, there are active devices such as transistors, and there are also ports, diodes, and ties. Additionally, other objects not specifically discussed herein may also be created by this invention.

After the database objects are created, transistor placement is performed in step 144. Transistors are ordered in a two-dimensional array to minimize an inner connection length and cell area required in the layout. Also in step 144, a simulated annealing based approach for cell layouts, which have cell architectures not previously explored by automatic layout synthesis tools, may be used. The methodology used in step 144 supports a variety of layout styles such as multiple rows of transistor regions and transistor regions with vertically stacked devices (as previously discussed). Furthermore, in addition to minimizing a length of interconnects used in this transistor placement step, the present invention also minimizes channel density such that routing density is also reduced.

Component placement step 144 will now be described in greater detail. Basically, component placement step 144 includes steps necessary for placement of active devices such as transistors, and other devices such as ports, diodes, and ties. In general, component placement step 144 is implemented to minimize an interconnection density and length between each of the aforementioned components. Component placements step 144 is illustrated in greater detail in both FIG. 7 and FIG. 8.

FIG. 7 illustrates a first embodiment of component placement step 144. In first step 172 of FIG. 7, steps for abstract active device placement are executed. During abstract active device placement, active devices such as transistors are placed in a two-dimensional array to minimize the interconnection length and cell area. Another important factor which is considered during this step is the minimization of Channel Density. During this abstract step 172, the order of the transistors is primarily determined, but the actual physical coordinates of those transistors are not determined. Subsequently, in step 174, an abstract port placement step is executed. In this step, ports for both input and output signals are placed in locations which minimize the length of their interconnection to gates, sources, and/or drains of transistors. It should be noted that ports are placed after the active devices are placed because ports must be connected to active devices and that connection won't be known before the active devices themselves are placed.

Abstract diode placement is implemented in step 176. During this step, it should be noted that diodes are usually placed near input ports. Therefore, after the input port is placed, a diode may then be placed as close as possible to the input port. Subsequently in steps 175 and 173, active devices and the ports are absolutely placed. During this absolute placement step, both active devices and ports are given actual geometric locations. With respect to active devices, a geometric location is determined on the basis of a location of contacts in the cell layout. If a contact is located between two active devices, a greater distance is required between the two active devices. Similarly, if no contact is located between the two active devices, a shorter distance may be used. As previously mentioned, once the geometric location of the active device is determined, the placement of the port can be calculated because it must be as close as possible to the active device to which it connects to. Furthermore, in this step, a vertical spacing between active devices, such as transistors, is decided on the basis of Channel Density determined during the steps executed during abstract active device placement in step 172.

Subsequently, absolute diode placement is executed in step 177. This step is executed at this point because the absolute location of the input ports has been determined. Next, abstract tie placement is performed at step 178. Once transistors or active elements are placed, the locations of power and ground connection to the source and drains of transistors are known, and these locations are helpful in abstract placement of substrate and well ties. In absolute tie placement step 179, the actual geometric co-ordinates are assigned to ties based on the geometric locations of transistors and their source/drain connections. Furthermore, to ensure sufficient room for ties at appropriate locations, tie placement is performed before a general routing stage. If necessary, a subsequent router step may be used to solve a problem of interconnecting well or substrate ties to power or ground supply rails.

A primary objective of tie placement step 178 is to determine a set of substrate and well tie locations that will produce design rule compliant layouts at the end of a cell layout synthesis. A secondary objective is to minimize an impact of routing, power and ground signals to well and substrate ties on a layout area.

FIG. 8 illustrates an alternate embodiment of component placement step 144. It should be noted that each of the components utilized in cell layout synthesis has a different priority level when determining their respective placement locations. In one embodiment of the implementation of the invention described herein, active devices such as transistors have the highest priority. Therefore, components such as transistors should be placed before any other components. Secondary components include ports, and therefore, ports should be placed after transistors are placed but before any other type of component is placed in the layout. Lastly, components such as diodes and ties are placed. These elements are placed only after active elements and ports have been placed in a cell layout. This priority scheme is inherent in the methodology illustrated in FIG. 8. For example, abstract placement of component types is performed first in step 180. Within step 180, active elements will be placed first, ports will be placed second, and each will be followed by other components such as diodes and ties. Components are then absolutely placed in step 182. At this point, each of the components is given its exact geometric location within the cell layout. Again, the priority scheme described above is implemented. Therefore, active elements are placed first, followed by ports, and then, diodes and ties. At that point, in step 184, the methodology implemented in FIG. 8 determines whether or not more component types should be placed. If no more components should be placed, the placement step is done. If more components should be placed, the placement methodology repeats, performing steps 180-184 for the additional components needing placement.

After the components are placed, pre-routing is performed as step 152. In pre-routing step 152, sources and drains of adjacent transistors which receive the same signal are connected with Diffusion wiring. Diffusion contacts are also added to the source and drain connections if other connections to non-adjacent gates, sources, or drains are required.

Subsequently, area routing is performed as step 154. In area routing step 154, all of the signals connecting the active devices, ports, diodes, and ties are routed in accordance with the layers specified in a template provided in step 136. Each routing layer is given preference in wiring direction and cost parameters to control wiring length and a number of vias. In the area routing technique implemented by the present invention, routing is accomplished by a combination of maze search, layer assignment, and rip-up-and-reroute heuristics.

After connections between the transistors, ports, diodes, and ties are completed, a resulting layout must be compacted to provide for the most efficient area utilization possible. Compaction is accomplished in step 156. FIG. 9 illustrates layout compaction step 156 in greater detail. The layout compactor implemented in FIG. 9 is a one-dimensional constraint-graph based algorithm. It compacts a layout first in one dimension (say X) and then in a second dimension (say Y). One of the characteristics of the graph based approach implemented in FIG. 9 is that results in the first compaction direction are usually better than results in the second direction.

Template constraints are then added as step 190 of FIG. 9. These constraints include cell height, well height, an X and Y grid for a bounding box, an X and Y grid for input and output ports, and the distance of power and/or ground rails from a cell boundary. After the template constraints are added in step 190, compaction is performed as step 191.

After the first compaction step 191 is executed, the resulting layout is tested to determine whether or not the required cell height is met. If the cell height is not met, the program flow reverts to step 140. If the cell height is met, a second compaction step is performed as step 193. This compaction step 193 is in an opposite direction from the first compaction direction executed in step 191. For example, if in step 191, compaction was attempted in a YXY sequence, then compaction is executed in an XYX sequence in step 193. It should be noted that it is important to compact in a Y direction first because if a layout resulting from a compaction in the Y direction does not meet a required cell height, a layout resulting from a first compaction in the X direction will not be within a required cell height specification. Assuming that cell height is met in both the compaction steps 191 and 193, the narrowest cell generated in steps 191 and 193 is selected in step 194. After the narrowest cell is chosen in step 194, program flow reverts to step 158 in FIG. 4. In step 158, the layout area of critical interconnects are analyzed for performance. In general, larger area of certain layout elements, such as Diffusion or polysilicon, indicates slower circuit performance which may be unacceptable. If this is the case with the layout chosen in step 194, the layout is reverted back to step 152, with the same component placement as before. Modified steps of pre-routing step 152, area routing step 154 and layout compaction step 156 are attempted until a satisfactory layout is obtained in step 160.

The cell with a lowest width is then determined in step 166. This cell is determined from all physical implementations generated from steps 144 through step 160. After the cell with the lowest width is determined, a step of tie, contact, and notch filling is executed.

Tie, contact, and notch filling is then performed as step 168. Tie filling step 168 may be required to be executed as compaction step 156 does not guarantee satisfaction of tie-coverage design rules. Step 168 is designed to add substrate and well tie Diffusion wherever possible without violating design rules. This step enhances tie coverage and performance of the final layout without increasing cell area. Finally, notch and contact filing are performed. Notch filling adds geometry to prevent internal and external notch errors. Contact filling identifies Diffusion areas that can accommodate metal contacts in order to minimize resistance and increase circuit performance.

As a result of executing each of steps 136 through 168, a cell layout is generated in step 170. It should be noted that the methodology disclosed herein is a fully automated process and does not require external user intervention or manual manipulation of the layout design. As such, both latency associated with layout development and overhead costs are also significantly decreased.

III. Selected Topics

A. High Density Transistor Placement

The process of transistor-level layout synthesis includes a step of placing transistors. This step is included in component placement step 14 of prior art FIG. 1. During the step of placing transistors, a horizontal and vertical location, as well as an orientation, of each transistor must be determined. The transistors are subsequently interconnected by the routing of wires which may be implemented as metal, polysilicon, or another conductive substance. A very substantial fraction of the area consumed by a cell layout consists of area occupied only by these conductive wires. Therefore, the size of a cell with a given transistor placement may be accurately estimated before routing only by accurately estimating the overall routing area of the cell. Additionally, local routing is important to measure because it also affects the size and performance of the cell which is laid out. The measurements used to estimate local routing area include the vertical alignment of transistor terminals that are electrically connected, as well as the measurements of the number of drain-source connections which are connected by Diffusion abutment. The latter measurements are especially important in two-terminal connections.

Many prior art solutions have attempted to find transistor placement that results in minimum cell area. Traditionally, the best estimator of layout width is the number of Diffusion breaks in a transistor placement; similarly, the best estimator of layout height includes the channel routing density of the placement. Therefore, the transistor placement minimization problem is to minimize a cost function that includes the number of Diffusion breaks and channel routing density. However, prior art solutions have recognized that this process of minimizing such a cost function is computationally intractable when a deterministic algorithm is used, even for series-parallel circuits. For more information see the article entitled, "Minimum Area Layout of Series-Parallel Transistor Networks is NP/Hard" by Chakravarty et al. published in IEEE Transactions on Computer-Aided Design, Vol. CAD-10, pgs. 943-949, July 1991. Prior art solutions have basically taken three different approaches to solve problems associated with generating transistor placements which result in minimum area cells. In a first prior art solution, a restricted version of the problem is solved with a deterministic algorithm. Such algorithms can find minimum width layouts. Additionally, such algorithms can find a minimum height in restricted cases. For example, a transistor placement algorithm described in "Layout Minimization of CMOS Cells" by applicant Robert L. Maziasz and John P. Hayes allows for the minimum height for a multi-gate series-parallel circuit for a given placement of the gates to be found. In addition, for up to 5 gates, this method by Maziasz and Hayes may be extended to find a gate placement that yields an optimal height for the cell by trying all permutations of the gates. However, this prior art implementation is too computationally expensive beyond this number of gates and heuristic methods must be employed.

A second prior art approach uses optimization techniques such as iterative improvement with multiple starts or simulated annealing. These prior art methods employ transistor moves that generate only legal or feasible placements. These optimization methods inherently have the potential to find globally optimal solutions; however, when the search space is highly restricted, the final solution may not be globally optimal, because some placements are not reachable or are only reachable with great difficulty from a given initial placement. Restricting the search space reduces the number of candidate placements whose cost needs to be evaluated; therefore, this restriction allows such methods to use the traditionally inefficient method of calculating channel routing density, called the left edge algorithm (LEA). This prior art placement approach cannot find a globally optimal solution because all solutions are not reachable. An example of this prior art method is reported in "A multiple row-based layout generator for CMOS cells" by G. Lakhani and S. Rao, published in the Proceedings of the International Symposium on Circuits and Systems, pgs. 1697-1700, 1990, which uses iterative improvement with multiple starts for multiple rows of transistors. Another example is described in "Efficient area minimization for dynamic CMOS circuits" by B. Basaran and R. Rutenbar, published in the Physical Design Workshop, pgs. 150-153, 1996, which uses simulated annealing for a single row of transistors. A third example is described in "CMOS leaf-cell design using simulated annealing" by Q. Wu and T. Sloane and is published in the Proceedings of the Midwest Symposium on Circuits and Systems, pgs. 1516-1519, 1992, which uses simulated annealing for multiple rows of cells, not transistors.

A third prior art approach also uses iterative improvement with multiple starts or simulated annealing, but relaxes the constraint that only legal placements be generated. Such relaxation techniques typically assign a high cost to such illegal placements so that none are present in the final solution. The result is that all placements are more easily reachable from a given initial placement, so that a globally optimal solution can be found. However, the search space is greatly increased, so that the prior art solution did not deem it computationally feasible to estimate routing area by using channel routing density, since the traditional LEA method is computationally expensive. Therefore, an inferior but computationally more efficient routing estimator was used, namely total wire length. This prior art approach finds a globally optimal solution to an inaccurate cost function. An example of this approach is provided in an article entitled, "Optimal CMOS Cell Transistor Placement: A Relaxation Approach" by A. Stauffer and R. Nair, published in the Proceedings of the International Conference On Computer-Aided Design, pgs. 364-367, November, 1988, which uses either iterative improvement with multiple starts, or simulated annealing, for multiple rows of transistors.

In summary, none of the methods disclosed in the prior art implementations efficiently find minimum width and minimum height layouts for general circuits of arbitrary size. Therefore, layouts produced by prior art methods are usually significantly larger than necessary.

The present invention provides a method for placing transistors which employs a relaxation version of the optimization method previously referred to as simulated annealing. This simulated annealing optimization method using relaxation techniques allows very near optimal solutions to comparatively complex problems to be determined. Unlike other prior art implementations which used such a technique, the present invention uses accurate and computationally efficient routing estimation methods to find optimal or very near optimal width and height solutions to the transistor placement problem. The transistor placement technique of the present invention will now be described in greater detail.

The present invention may be used to implement abstract active device placement step 172 of FIG. 7. It should be noted that the present invention which will be subsequently described provides a method for transistor placement in a traditional two-row layout style. While a two-row layout is a primary context for implementation of the method for transistor placement described herein, other layout styles may also be used. During a following discussion, the term two-row layout style will be used to describe a layout style in which two Diffusion regions, one a P-type and one an N-type, are placed with routing in-between each of the two Diffusion regions to form interconnects between transistors. Routing can also occur over the active devices as well as in the regions above and below them. Other layout styles, which will subsequently be described in greater detail, include a stacked layout style. In the stacked layout style, a plurality of rows of N-type Diffusion regions and/or a plurality of rows of P-type Diffusion regions are provided. There are local interconnects between the plurality of rows of N-type Diffusions and there are local connects between the plurality of rows of P-type Diffusion regions. Furthermore, in the stacked layout style, there are global connections between the plurality of rows of N-Diffusion regions and the plurality of rows of P-Diffusion regions. With the environment in which the present invention will be implemented, provided above, a description of methodology of the present invention will subsequently be described. The preferred embodiment uses two rows of P-Diffusion regions and two rows of N-Diffusion regions.

During execution of the methodology of the present invention, a folded transistor-level net list is provided to step 172. Subsequently, in step 802, the present invention performs random initial transistor placement. During this random initial transistor placement in step 802, transistors are placed without regard for an optimal placement solution. Subsequently, in step 804, the present invention incrementally modifies the initial placement by moving a set of contiguous transistors. Prior to performing the move operation, a move type is selected as well as a size of the move window. A move type which may be selected in the present embodiment of the invention disclosed herein is one of an H1 or an H2 move, although it is not limited to these move types. An H1 move swaps a transistor in a left-most position with a transistor in a right-most position. Similarly, an H1 move swaps a transistor in a left-most minus 1 position with a transistor in a right-most minus 1 position. This swapping process may also be referred to as reflection. A second type of move operation implemented by the present invention is referred to as an H2 move. During execution of an H2 move, two rows of transistors are reflected about a vertical axis which is located at a mid-point of the move window. The type of move operation which is executed is randomly selected. Additionally, the width of the move window is also arbitrarily selected between a maximum and a minimum move window size. The maximum and minimum window side are experimentally determined.

A legal placement is one in which horizontally adjacent source/drain terminals of horizontally adjacent transistors are electrically connected in the circuit. Legal moves always generate legal placements. Illegal moves relax this constraint and generate illegal placements, in which horizontally adjacent source/drain terminals of horizontally adjacent transistors are not electrically connected in the circuit. A explicit Diffusion break is required to be inserted in between such pairs of transistors to prevent their neighboring terminals from electrically shorting together. The present invention allows illegal moves to be selected. Since a given transistor placement typically contains both transistors and explicit Diffusion breaks, these breaks are moved in between such illegal placements during the transistor placement process, as a consequence of the move process. Once moved into such a position, explicit breaks will typically remain in between illegal placements, since such illegal placements are assigned a very high cost.

After the move type and the move window size are determined, the present invention executes a function to evaluate cost of the move step 806. The Evaluate Cost of Move function, step 806, is illustrated in greater detail in FIG. 11. Note that the cost of the move can be determined before making the actual move.

Before beginning a more detailed description of step 806, a description of the methodology used to calculate Column Density and Channel Routing Density will be described in greater detail. For use and understanding the concepts of Column Density and Channel Routing Density, refer to FIG. 13. As illustrated in FIG. 13, a P-type Diffusion region 1100 implements P-transistors A, B, C, and D. Also, N-type Diffusion region 1102 implements N-transistors C, B, D, and A. To calculate a Column Density, corresponding transistors in each of the P-type region 1100 and the N-type region 1102 are theoretically connected via dotted lines. If columns are then viewed, a number of horizontal lines crossing each column determines a Column Density. For example, the column which includes P-type transistor A and N-type transistor C, includes two horizontal lines. Therefore, a corresponding Column Density is 2. Similarly, the column including P-type transistor C and N-type transistor D, includes 3 horizontal lines. Therefore, the corresponding Column Density is equal to 3. A Channel Routing Density corresponding to the circuit illustrated in FIG. 13 is the maximum of all the Column Density values. The terms, Column Density and Channel Routing Density will subsequently be used during a discussion of the methodology of the present invention.

Referring again to FIG. 11, in step 900, a new Column Density is calculated for the transistors included in the Move Window determined in step 804. The Column Density count for the Move Window is subsequently calculated in step 902. The Column Density count value indicates the number of columns which have a certain column density. For example, if a Move Window includes four columns and two of those columns have a Column Density of two (2), one column has a Column Density of three (3), and the fourth column has a Column Density of one (1), the Column Density count value would indicate that there are two columns having a count density of 2, one column having a count density of 3, and one column having a column density of 1. Additionally, in step 902, the maximum Column Density before the move operation is executed is saved in step 902, and maximum Column Density after the move operation is executed are saved. In step 904, the maximum Column Density value after the move is compared with the Channel Routing Density of the whole layout, and not merely to the Channel Routing Density of the transistors within the Move Window. If the maximum Column Density after the move is greater than the channel routing density, a new channel routing density is set to the maximum Column Density after the move in step 906. It should be noted that the maximum Column Density after the move operation and the maximum Column Density before the move operation apply only to the columns included within the Move Window.

If the maximum Column Density after the move operation is not greater than the channel routing density, step 908 is executed. In step 908, it is determined whether or not the maximum Column Density before the move operation is executed is equal to the channel routing density. If the maximum Column Density before the move is equal to the channel routing density, a new channel routing density value is set to a largest non-zero Column Density in a step 912. The largest non-zero Column Density value corresponds to a largest Column Density value of the largest Column Density in the entire layout and not merely the move window. However, if the maximum Column Density before the move is not equal to the channel routing density, the new channel routing density is set to the old channel routing density in step 910.

When determining a value of the new channel routing density, it should be noted that the present invention includes a method for efficiently calculating the largest Column Density without exclusively considering a Column Density of all columns of the layout. An example of execution of evaluate cost of moves step 806 is illustrated in FIG. 14. Referring to Case 1 of FIG. 14, Column Densities for the Move Window are calculated before and after a move operation. In Case 1, an overall Channel Routing Density increases. In the first column, the Column Density before the move was equal to 2 and the Column Density after the move was equal to 1. Additionally, in the second column, the Column Density before the move was equal to 2 and the Column Density after the move operation was executed is equal to 3. Furthermore, the largest Column Density outside the Move Window is equal to 2.

The chart included in FIG. 14 indicates a Column Density count value for each case. Before the move operation, 3 columns with column density equal to 2 are shown for the entire layout. After the move operation is executed, the count density of each column in the layout is again calculated. After the move, there is one column having a Column Density of 1, one column having a Column Density of 2, and one column having a Column Density of 3. Because the Channel Routing Density is determined to be the maximum of all Column Densities, the Channel Routing Density increases to 3 after the move operation is executed in Case 1. It should be emphasized that the Channel Routing Density is calculated by looking only at the changes in Column Density of the columns included in the Move Window. This results in a calculation of Channel Routing Density which is much more efficient than any implemented by prior art implementations.

Case 2 in FIG. 14 illustrates a case in which the Column Density of the first column is equal to 2 before a move operation and is equal to 1 after the move operation. Additionally, in Case 2, the Column Density of the column before the move operation is executed is equal to 2 and the Column Density of the second column is equal to 3 after the move operation. Furthermore, in Case 2, the highest column density outside the Move Window is equal to 4. In Case 2, therefore, the Channel Routing Density remains at the highest Column Density value both before and after the move operation. Thus, the move operation has no effect on the Channel Routing Density. Referring to the chart indicating a column density count value for Case 2, it should be noted that the layout includes two columns which have a Column Density of 2 and one column which has a Column Density of 4 before the move operation. After the move, the layout includes one column which has a Column Density of 1, one column which has a Column Density of 3, and one column which has a Column Density of 4.

Case 3 illustrates an example in which the first column has a Column Density of 2 before the move and a Column Density of 1 after the move operation is executed. Additionally, the second column has a Column Density of 2 before the move operation is executed and a Column Density of 1 after the move operation is executed. The highest Column Density outside the Move Window is 2 for the layout illustrated in Case 3. As with previous Case 2, the channel routing density of Case 3 is not affected by the move operation because the highest Column Density outside the window is the same as or higher than the highest Column Density within the Move Window.

Case 4 illustrates a situation in which the column density of the first column is equal to 2 before a move operation is executed and is equal to 1 after the move operation is executed. Case 4 also illustrates that a second column has a column density of 2 before the move operation is executed and a column density of 1 after the move operation is executed. Outside The Move Window, the highest Column Density is equal to 1. Therefore, after the move operation, the Channel Routing Density changes from 2 to 1.

To understand how the example illustrated in FIG. 14 corresponds to the methodology implemented in FIG. 11, it should be noted that the new Column Density values computed in step 900 correspond to the Column Density values illustrated in Cases
1-4 after a move operation is executed. Furthermore, the maximum Column Density before the move operation value of step 902 corresponds to a maximum Column Density of all columns implemented within a Move Window before the move operation is executed. Additionally, it should be noted that the maximum Column Density after the move operation value of step 902 corresponds to a maximum Column Density value of all columns implemented within the Move Window after the move operation is executed. The Channel Routing Densities of steps 904 and 908 correspond to the Channel Routing Density before the move operation as illustrated in FIG. 14. The new Channel Routing Density value of steps 906, 910, and 912 of FIG. 11 correspond to the Channel Routing Density value after the move operation of FIG. 14.

When executing step 912, the new Channel Routing Density value may be calculated using the Column Density count value chart illustrated in FIG. 14. The new Channel Routing Density value is equal to a largest index having a non-zero Column Density. To determine the largest index with a non-zero Column Density Value, the entries in the Column Density count chart of FIG. 14 may be referred to. First, the entries in the Column Density count chart at an index corresponding to the channel routing density must be reviewed. Subsequently, the index is decremented until the first non-zero count is found. As an example, refer to Case 4 of FIG. 14. In this case, the Channel Routing Density value corresponded to two (2) before the move operation was executed. Referring to the Column Density Count chart at index 2, it should be observed that the count is later equal to zero. Therefore, the index is decremented to 1 and the chart is evaluated to determine that the index 1 is the largest index with a non-zero count value of three(3). Therefore, the new Channel Routing Density equals the index 1. Furthermore, in viewing FIG. 11 and FIG. 14 together, it should be noted that case 1 of FIG. 14 corresponds to step 906 of FIG. 11. Similarly, Case 2 of FIG. 14 corresponds to step 910 of FIG. 11. As well, Cases 3 and 4 of FIG. 14 correspond to step 912 of FIG. 11.

Referring again to FIG. 10, it should be noted that FIG. 11 only provides a methodology for evaluating a cost associated with increased channel routing density. It should also be noted that the cost associated with the move operation also reflect breaks in Diffusion regions, a horizontal wire length, a cell width, and a cell height. Calculation of each of these additional cost metrics is well known in the data processing art and will not be described in greater detail herein.

After step 806 is executed and the cost of a move operation is evaluated, the present invention must determine whether or not the move operation should be implemented in step 808. Step 808 is illustrated in greater detail in FIG. 12. In a step
1000, a change in cost, or delta cost, is calculated as the cost of the layout after the move operation less the cost of the layout before the move operation. In step 1002, it is determined whether or not the delta cost is less than zero. If the delta cost (.DELTA.C) is less than zero, the move operation is accepted or implemented. However, if the delta cost (.DELTA.C) value is not less than zero, a function of the delta cost (.DELTA.C) and the temperature (T) is calculated in step 1004. In the algorithm of the present invention, the temperature (T) is a parameter which is used to control the convergence of the algorithm to an optimal layout solution. The temperature (T) parameter is initially set to a value which allows a very high percentage of move operations to be accepted. The temperature (T) is subsequently lowered successively. The temperature (T) parameter is decreased, typically, by multiplying it by a number less than 1 until the algorithm of the present invention converges. Referring again to FIG. 12, the function F (.DELTA.C, T) of step 1004 may be represented by Equation 1:

The output (f) of F (.DELTA.C, T) is a number between zero (0) and one (1). Subsequently, in step 1006, a random number generator generates a random number (r) between zero (0) and one (1). In step 1008, the random number (r) generated in step
1006 is compared with the value of the function (f) of step 1004. If the random number (r) generated is less than the value of the function (f), the move operation is accepted in step 1010. However, if the random number (r) generated in step 1006 is greater than or equal to the value of the function (f) generated in step 1004, the move operation is rejected.

Note there that in the preferred embodiment, a "pseudo" random number generator is utilized. The advantage of this over a truly random number generator is reproducibility. One key element here is the apparent randomness of the random number generator. Therefore, a truly random number generator would generate acceptable results, at the cost of reproducibility. For these reasons, the above described Simulated Annealing techniques are considered to be non-deterministic algorithms, despite the use of a reproducible random number generator.

If the move operation is rejected, the program flow returns to a step 804 where a new move is selected. However, if the move operation is accepted, the move operation is performed in step 810 and costs associated with the move operation are updated in step 812.

Subsequently, it must be determined whether or not the algorithm implemented by the present invention has converged or "frozen" in step 814. A number of different methods of determining whether the system has reached a global minimum exist. For example, in the preferred embodiment, if a given minimum number of moves have been accepted or a maximum number of moves has been exceeded, the previously discussed temperature (T) parameter is multiplied by a value (A) (alpha), which is a number between zero and 1. If the maximum number of operations has been exceeded for preselected number of successive temperatures, T, the system is considered frozen and operation of the program terminates. If not, program control is returned to step 804 where a new move window is selected. Upon termination, the output is the transistor placement with a lowest cost of all placements generated.

In addition to calculating costs associated with channel routing density, the present invention also utilizes other parameters in determining the cost value. In addition to calculating channel routing density, a horizontal local routing metric is used to decrease the number of small Diffusion abutments. Such small Diffusion abutments connect exactly 2-terminals by placing the drain and source terminals of transistors in the cell horizontally adjacent to each other and by connecting the two terminals using a Diffusion wire. The result of using such abutments is that no metal or Diffusion contact is required. Therefore, a minimum distance between the two transistors is roughly reduced to half compared to a Diffusion abutment requiring a contact. Additionally, parasitic capacitance is reduced considerably. During cost determination, the number of small Diffusion abutments in each row is computed and used to more accurately determine cell width.

A vertical local routing metric included in the present invention involves vertical gate terminal alignment and vertical drain and source terminal alignment. The methodology of the present invention computes a number of such alignments and tries to maximize them. Such alignments result in denser layouts since straight wires without layer changes may be used to make these aligned connections.

The optimization methodology of the present invention enables transistors to be placed in significantly smaller layouts for circuits than any other prior art placement algorithm. Additionally, the present invention does so in a time efficient manner. It should also be noted that the implementation of the invention described herein is provided by way of example only.

B. Transistor Stacking

As previously described, the process of transistor-level layout synthesis includes a step of placing transistors. This step involves determining the horizontal and vertical location, as well as the orientation, of each transistor. The transistors are subsequently interconnected by the routing of conductive wires.

Traditionally, the transistors of a cell are placed in two horizontal rows, one for P-type transistors, and the other for N-type transistors. However, in standard cell design, where all cells have the same standard cell height, some cells can be made narrower by altering the cell architecture. Multiple horizontal adjacent rows may be used for both P-type and N-type transistors. This cell architecture allows transistors of a given type to be vertically aligned, or "stacked".

Prior art transistor placement methods have used various forms of such "stacked" cell architecture. For example, a program called Excellerator allows stacking of an arbitrary number of vertical transistors, but it restricts stacking to transistors that share a common transistor gate signal. The Excellerator program performs transistor stacking before transistors are connected by Diffusion wires to form chains. In a second prior art methodology, a system called in TOPOLOGIZER allows stacking of transistors with arbitrary connections. The methodology implemented TOPOLOGIZER does stacking during transistor placement, but uses an approach which does not include measurement of routing area in the cell height calculation. Therefore, the results of TOPOLOGIZER are usually far from optimal. Another transistor placement program, PAMS, provides for transistor stacking at the same time as transistor placement. The PAMS system, however, did not employ horizontal Diffusion abutment. Later, the CETUS program was provided that performs restrained stacking as a post-placement step in which P-N transistor pairs were stacked in the inner rows based on transistor sizes and local routing density.

The prior art implementations described above either fail to use the most accurate cost metrics, channel routing density, and Diffusion abutments, or allow only a restricted form of stacking; therefore, they fail to find a near optimal solution to the problem they are attempting to solve.

In contrast, the present invention provides a methodology which implements an unrestricted stacked placement of transistors that minimizes the best metrics of cell area, including channel routing density, horizontal Diffusion abutments, and local routing density.

The transistor placement algorithm of the present invention employs a relaxation version of the optimization method referred to as simulating annealing. The Simulated Annealing methodology is a general optimization technique that is able to find very near optimal solutions to combinatorial problems. The present invention utilizes the Simulated Annealing methodology to stack transistors by incorporating vertical transistor moves and local routing metrics between stacked transistors. Through the use of this methodology, the present invention produces high quality stacked transistor placements.

FIG. 15 illustrates a second embodiment of abstract active device placement step 172. Prior to beginning step 172, a folded transistor-level net list is provided thereto. In step 1302, transistors to implement the cell are randomly placed in an initial step. Subsequently, in step 1304, a move operation is selected. Before implementing the move operation, however, the cost of the move operation is evaluated in step 1306. Each of steps 1304 and 1306 are illustrated in greater detail in FIG.
16.

In FIG. 16, a move operation is selected in step 1304. The move operations which may be selected include H2, H1, H4, and V2 move operation. Additionally, it should be noted that additional move operations may be implemented as desired by the system designer. In determining the operation executed by each of the move operations, it should be noted that the "H" in the move name indicates that a horizontal move occurs and the "V" indicates that a vertical move occurs. Furthermore, the number associated with the letters "H" and "V" indicate the number of rows of Diffusion regions, or transistors, involved in the move operation. As previously described, when executing a move operation, a reflection operation is executed such that a transistor in the left most position of the Move Window is transferred to the right most position of the move window. And the transistor in the right most position of the Move Window is transferred to the left most position of the Move Window. Similarly, depending on the window size, the transistor in the right most position minus one (1) is swapped with the transistor and the left most position minus one (1). Each of the move operations executed in step 1304 is implemented to allow the corresponding transistors to be configured for an optimal local connection. As previously mentioned, the "local connection" in stacked transistor placement refers to the connection between two rows of transistors of the same type.

After a move operation is selected in step 1304, the quality of the placement which will result from the move operation is evaluated in order to determine whether to accept or reject the proposed move. This evaluation step is executed in step
1306. In the first portion of step 1306, general cost metrics are evaluated, as shown in step 1324. It should be noted that the general cost metrics evaluated herein corresponds to the general cost metrics previously mentioned in Section A: High Density Transistor Placement. In the second portion of step 1306, cost metrics associated with evaluating stacking transistor placements are evaluated, as shown in step 1326. In evaluating stacking cost metrics, gate matches and mismatches, drain and source matches and mismatches, and vertical wire length parameters are evaluated.

To evaluate gate matches and mismatches and drain/source matches and mismatches, the numbers of matches and a number of mismatches are calculated. It should be noted that gate matches occur when transistor gate terminals electrically connected may be placed in a straight vertical line between two rows of transistors of the same type. Conversely, gate mismatches occur when electrically connected gates may not be placed in a straight vertical line between two same type transistor rows. Likewise, drain/source matches occur when the drains or sources of two transistors can be connected in such a straight line. Conversely, drain/source mismatches occur when drains or sources of two transistors in adjacent same type Diffusion regions may not be so connected.

In evaluating the aforementioned stacking cost metrics, each of the metrics is weighted by a predetermined factor to indicate its relative importance in the transistor placement algorithm. A cost associated with evaluating stacking metrics may be written as:

In one embodiment of the present invention, the weighting constants K.sub.1 to K.sub.n respectively have the values of K.sub.1 =-1300, K.sub.2 =2100, K.sub.3 =-1100, K.sub.4 =1200, K.sub.5 =10. In the present embodiment of the invention, the stacking cost metrics associated with gate matches and mismatches and drain/source matches and mismatches are calculated by: 1. identifying all cases of local routing configurations: 2. identifying beneficial local routing configuration cases: 3. rating only the beneficial local routing configuration cases according to the relative benefit: and 4. assigning costs based on the relative position of these beneficial local routing configuration cases.

FIG. 17 illustrates an example wherein the beneficial local routing configuration cases have been identified, rated, and assigned costs. Referring to FIG. 17, Case 1 indicates a transistor configuration which has a total match count of 1, a total mismatch count of 1, and a cost of -100. The match count is a gate match and the mismatch count is a drain/source mismatch. Case 2 illustrates a system in which there are 2 matches, 1 mismatch, and a cost of -100. Of the matches, both are matches between the drain/source regions of the transistors. The mismatch is a result of gate mismatch. In Case 3, there are 2 matches, 1 mismatch, and an associate cost of -1200. Note that while the match and mismatch numbers of Case 2 are the same as Case 3, the type of match, specifically a gate match, in Case 3, makes Case 3 a much more attractive local routing solution. In Case 4, it should be noted that there are no mismatches even though the two transistors are not actually connected because one of the transistors is connected to a reference voltage supply rail. When one of the transistor is connected to a reference voltage supply rail, it is not included as a mismatch. Case 5 illustrates an optimal solution which has an associated cost of -3500 because it has no mismatches, 2 drain/source matches, and 1 gate match.

Referring again to FIG. 15, after the cost of the move operation is calculated in step 1306, step 1308 determines whether or not the proposed move operation should be accepted. Step 1308 is implemented in a similar manner to step 808 of FIG. 10. If the move operation should not be executed, program control is returned to Select Move step 1304. If the move operation is accepted, the move operation is performed in step 1310. Subsequently, the associated costs are updated to reflect the move operation in step 1312. After the costs are updated, it must be determined whether the stacked placement methodology should be terminated in step 1314. This step corresponds to step 814 of FIG. 10. If the move operation should not be terminated, program flow returns to Select Move step 1304. If the stacking placement algorithm of the present invention should be terminated, the transistors have been placed in an optimal manner.

FIG. 18 illustrates an example of the stacking placement methodology implemented in the present invention. In the original placement which corresponds to initial placement step 1302, there are no matches, 6 mismatches, and a vertical wire length
14. A V2 move is subsequently selected in step 1304. After the V2 move, there are still no matches, but the number of mismatches has been reduced to 4 and the vertical wire length has been reduced to 10. Subsequently, the methodology of the present invention implements an H1 move. As a result of the H1 move, there are now 3 matches, only 1 mismatch, and a vertical wire length of 10. Thus, it may be seen that the invention provides an efficient methodology for optimizing a layout operation.

Through the use of the move operation and metric calculations described above, the stacking transistor placement algorithm of the present invention results in significantly smaller stacked transistor layouts for circuits which are provided in a time efficient manner. Since the general stacking operation, described above in Section A: High Density Transistor Placement Algorithm, is performed concurrently with the stacking transistor placement, both methodologies may be implemented to provide an optimal solution for any type of layout which is implemented.

C. Input/Output Port Placement

A description will now be given of the Abstract Port Placement shown in step 174 in FIG. 7. Traditionally Abstract Port Placement has been done either manually or by software. When done manually, Abstract Port Placement was done in a very time consuming, slow way. Manual placement of ports required that designers be able to comply with all required design rules and requires tremendous amounts of time for moderately large scale integrated circuits.

When Abstract Port Placement has been accomplished in the past by using software, it was typically done in the context of standard cells and typically involved only boundary port placement. A boundary port is a port which is placed always at a boundary of a cell in a cell layout. Since the only type of ports supported were boundary ports, software routines which were able to do boundary port placement were relatively straight forward and simple to implement. One disadvantage with the known commercially available layout tools has been that port assignment could be done only at a cell boundary, and thus port assignments for locations internal to cells was either not possible, or required significant amounts of manual intervention.

As technology has developed, and more than two metal layers have become common, it is now possible to route multiple metal layers over cells. The existence of three or more metal layers in semiconductor processes results in standard cells that can be placed adjoining each other and thereby reduces or eliminates dedicated routing channels which used to be required to exist between standard cells when two or fewer metal layers were used. As a result of using additional metal layers, access to abutting cells is preferably accomplished by internal port capability rather than boundary port capability. Previously sophisticated "place and route" tools have been able to locate in a very limited way internal port assignment. However, in order to have this capability, a programmer had to tell the "place and route" software in advance where acceptable port placement locations were in the layout, and in the internal portion of a cell for an internal port.

One commercially available "place and route" tool performing minimal port placement is "Gards" from Silver Lisco. Another commercially available "place and route" tool that has been able to do minimal internal port assignment is "ArcCell" from ArcSys. The ArcCell tool was able to find previously defined locations for internal ports as well as find any other available ports. One disadvantage with the ArcCell tool however has been that it required that a layout designer would have previously set enough room aside for any internal ports placed, and had to basically plan where the internal ports were going to be located in the cells. With all of that information, the ArcCell software could do some minimal internal port placement.

More recently in an article entitled, "Efficient Standard Cell Generation When Diffusion Strapping Is Required" by Guan and Sechen in the Fifth ACM/SIGDA Physical Design Workshop dated 1996, a description of a cell layout synthesis tool was provided. The Guan and Sechen tool was capable of doing internal port placement. However, their design was a modular design and had a restricted standard cell layout style. As a result there was little flexibility and inefficient utilization of space. The cell layout synthesis tool taught by Guan and Sechen scanned from one side of a layout cell to another. The methodology was to place transistors, route the cell, place the port to the left of gate signals until an output signal in the cell is met and put the internal ports to the right of the output signal on the right side of the gate signals. As a result of this uniform methodology, access to the internal ports was limited to no more than two directions.

Shown in FIG. 19 is a flow chart of the Abstract Port Placement methodology in step 174 in FIG. 7. FIG. 19 illustrates the internal port placement in accordance with the present invention. After starting with step 2602 the method shown in FIG.
19 is implementable in a layout software tool for transistor-level layout synthesis. First, active devices are placed, step 2604. In the preferred embodiment, the active devices occupy a multiple of three columns. The active devices are typically placed in the layout as columns and rows of active devices. In the preferred embodiment, two routing tracks are provided for placement of ports between two adjacent rows of active devices in step 2606.

In step 2608, an assignment of ports to a row and a "coarse" column is made based on a lowest cost factor. A cost factor determination is made in the assignment of a port to a "coarse" column based upon a number of cost factors. A first cost factor is the Column Routing Density. The density within each of the columns of active devices is determined and the least dense column is preferred in determining where internal ports are assigned. The second cost factor determination first involves an understanding of the concept of net spans. As mentioned above there is a plurality of rows and columns of active devices formed. Within each row there may be two or more active devices connected by a port net.

Shown in FIG. 20 is an example illustrating the cost factor of determining horizontal overlap of P and N-net spans. FIG. 20 illustrates two rows 2650, 2652 of active devices which also form columns. In the first row 2650, the first three active devices are connected together to form a P-net span 2654. In the second row of active devices 2652 which are formed of N-channel devices in a preferred form, the second 2642, third 2644, and fourth 2646 columns of N-channel devices are connected together to form an N-net span 2656. Shown by two columns designated as columns shown in FIG. 20 are columns B 2642 and C 2644 designated by a hashing. These two columns are columns that fall within the overlapping net span 2648. As a result of the overlap, these two columns 2642, 2644 would be preferred among the four illustrated columns 2640, 2642, 2644, 2646 as the two columns in which an internal port should be assigned for the illustrated connected nets. It should be noted that in FIG. 20, there is a specific net between the first three P-channels of the top row 2650, and the same net spans the second, third and fourth N-channel devices. Therefore, the optimal placement for the internal port corresponds to only the port connected to this designated net. Optimal placement of other internal ports among the four columns 2640, 2642, 2644, 2646 will vary based upon other net assignments.

Another cost factor which is to be determined is the placement of an internal port relative to the active device to which it will be connected. It is desired to place an internal port directly adjacent to an active device to which a terminal of the active device will connect. An internal port which does not directly connect to an adjacent active device is less preferred in the cost factor analysis to one that does directly connect to an adjacent active device. A fourth and final cost factor in the placement of internal ports is the consideration of how many ports have been previously placed in a given column. The cost criteria here is to minimize the number of ports associated with a particular column. The theory is to spread the number of internal ports as equally as possible among the various columns. It should be noted in connection with the four recited cost factors that they are not given equal priority.

Returning to FIG. 19, after an assignment of ports to row and coarse column have been made in step 2608, a determination of whether or not to place the internal ports in a staggered mode is made in step 2609. Stagger Mode alternates the assignment of internal ports between alternating rows for successive columns. In order to optimize the number of directions in which a port is accessible by a "place and route" tool, staggering is very advantageous. When in Stagger Mode, "stagger" groups of interacting ports are first identified in step 2610. After a group of interacting ports has been identified, an evaluation in step 2612 is made of the total cost of two or more stagger types for each stagger group and is based on fine columns. The number of fine columns correspond to the number of terminals which an active device has and which can be defined to fall within a modular column in the rows and columns of the active devices.

In the