(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2004/0098674 A1
`Vuong et al.
`(43) Pub. Date:
`May 20, 2004
`
`US 20040098674A1
`
`(54) PLACE AND ROUTE TOOL THAT
`INCORPORATES A METAL-FILL
`MECHANISM
`
`(75) Inventors: Thanh Vuong, Milpitas, CA (US);
`William H. Kao, Fremont, CA (US);
`David C. Noice, Palo Alto, CA (US)
`Correspondence Address:
`BINGHAM, MCCUTCHEN LLP
`THREE EMBARCADERO, SUITE 1800
`SAN FRANCISCO, CA 94111-4067 (US)
`(73) Assignee: Cadence Design Systems, Inc.
`(21) Appl. No.:
`10/300,715
`(22) Filed:
`Nov. 19, 2002
`
`Publication Classification
`
`(51) Int. Cl." .......................... G06F 15/76; G06F 15/00;
`G06F 17/50
`(52) U.S. Cl. .................................................................. 716/1
`(57)
`ABSTRACT
`Disclosed is a method, System, and article of manufacture
`for a one-pass approach for implementing metal-fill for an
`integrated circuit. Also disclosed is a method, System, and
`article of manufacture for implementing metal-fill that is
`coupled to a tie-off connection. An approach that is disclosed
`comprises a method, System, and article of manufacture for
`implementing metal-fill having an elongated Shape that
`corresponds to the length of whitespace. Also disclosed is
`the aspect of implementing metal-fill that matches the rout
`ing direction. Yet another disclosure is an implementation of
`a place & route tool incorporating an integrated metal-fill
`mechanism.
`
`Partition Design into Windows
`
`Custer Windows into Windows
`
`ldentify Blockages
`
`Sort Blockages
`
`Compute pre-fill density
`
`For Each Layer:
`Fence Blockages
`
`ite spaces
`Locate Wh
`
`Separate joint white spaces
`
`Split whit
`e Spaces
`
`Compute po
`st-fill density
`
`Remove metal-fill if appropriate
`
`of metal-fills
`Maintain list
`
`
`
`
`
`
`
`
`
`End each layer
`
`Process for tie-off nets
`
`Write list of metal fills
`
`End each region
`
`
`
`2O6
`
`
`
`21
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`232
`
`234
`
`236
`
`Intel Exhibit 1106
`
`

`

`Patent Application Publication May 20, 2004 Sheet 1 of 16
`
`US 2004/0098674 A1
`
`
`
`
`
`3
`
`O
`O
`v
`
`3
`
`S
`
`

`

`Patent Application Publication May 20, 2004 Sheet 2 of 16
`
`US 2004/0098674 A1
`
`Fig. 2
`
`
`
`2O2
`
`Partition Design into Windows
`
`Cluster WindoWS into Windows
`
`For Each
`Region:
`
`ldentify Blockages
`
`Sort Blockages
`
`Compute pre-fill density
`
`
`
`208
`
`210
`
`212
`
`
`
`
`
`21
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`232
`
`234
`
`
`
`236
`
`For Each Layer:
`Fence Blockages
`
`
`
`216
`
`
`
`for
`218 e
`split white spaces
`H.222
`Ecs,
`
`226
`
`228
`
`230
`
`Maintain list of metal-fills
`
`End each layer
`
`
`
`
`
`
`
`Process for tie-off nets
`
`Write list of metal fills
`
`End each region
`
`

`

`Patent Application Publication May 20, 2004 Sheet 3 of 16
`
`US 2004/0098674 A1
`
`Windows and Regions partitioning
`
`step
`size
`
`WindoW
`Size
`
`Wa, Wb, Wo: window that overlaps 3,5 and 8 other windows respectively
`
`Region 1
`
`": Region 3
`
`:...........
`
`Region 2
`
`
`
`Region 4
`
`

`

`Patent Application Publication May 20, 2004 Sheet 4 of 16
`
`US 2004/0098674 A1
`
`
`
`Fig. 4
`
`
`
`
`
`402
`
`40
`
`
`
`Build Kod-tree
`
`Sort Edges
`
`Create Lookup Strips
`
`408
`
`For Each Lookup Strip:
`Find Rectangle
`intersecting strip
`
`For each found rectangle 414
`
`Form New Rectangle
`
`Update bottom edge to top
`edge of rectangle
`
`420
`
`Vertical/Horizontal Merging
`
`

`

`Patent Application Publication May 20, 2004 Sheet 5 of 16
`
`US 2004/0098674 A1
`
`Merging and Extracting
`Overlapping Rectangles
`
`
`
`505f
`
`504
`
`Overlapping
`rectangles
`
`: g : : :
`
`Lookup
`Strips
`
`Rectangles
`formed
`
`Fig. 5a
`
`

`

`Patent Application Publication May 20, 2004 Sheet 6 of 16
`
`US 2004/0098674 A1
`
`
`
`532
`
`After vertical merge
`from fig 2C
`
`After horizontal
`merge
`
`Fig. 5b
`
`

`

`Patent Application Publication May 20, 2004 Sheet 7 of 16
`
`US 2004/0098674 A1
`
`540
`
`
`
`542
`
`,
`
`After horizontal
`merge
`
`After Vertical
`merge
`
`Fig. 5c
`
`

`

`Patent Application Publication May 20, 2004 Sheet 8 of 16
`
`US 2004/0098674 A1
`
`
`
`

`

`Patent Application Publication May 20, 2004 Sheet 9 of 16
`
`US 2004/0098674 A1
`
`
`
`CN
`N
`
`O
`N
`O
`N
`
`O
`N
`
`CD d
`
`--
`
`E
`o 5
`u
`s 3: .
`is a 3 E
`
`c
`
`C
`c
`
`CD
`to
`its
`on 9 U)
`is
`& 25
`S.
`5 .
`.
`if
`E 9
`5
`X
`2 5 2 as
`is 9 E
`
`N.
`O)
`-
`
`o 8
`&
`3 S.
`R 9
`S
`S. e
`
`

`

`Patent Application Publication May 20, 2004 Sheet 10 of 16
`
`US 2004/0098674 A1
`
`802
`
`804
`
`806
`
`
`
`Whitespace
`before split
`
`first vertical
`split
`
`Fig. 8
`
`then horizontal
`split
`
`

`

`Patent Application Publication May 20, 2004 Sheet 11 of 16
`
`US 2004/0098674 A1
`
`
`
`Whitespace
`before split
`
`first vertical
`split
`
`Fig. 9
`
`then horizontal
`split
`
`

`

`Patent Application Publication May 20, 2004 Sheet 12 of 16
`
`US 2004/0098674 A1
`
`
`
`Whitespace
`before split
`
`first vertical
`split
`
`Fig. 10
`
`then horizontal
`split
`
`

`

`Patent Application Publication May 20, 2004 Sheet 13 of 16
`
`US 2004/0098674 A1
`
`
`
`

`

`Patent Application Publication May 20, 2004 Sheet 14 of 16
`
`US 2004/0098674 A1
`
`
`
`1212
`
`1214
`
`1206
`
`1204
`
`Whitespace
`
`1210
`
`Fig. 12
`
`

`

`Patent Application Publication May 20, 2004 Sheet 15 of 16
`
`US 2004/0098674 A1
`
`
`
`cN r to do o ch
`O C C C v- w -
`cd c
`i?
`of c) or
`w-
`v
`v- w
`x-
`
`O O N
`N
`O o was v
`co
`c
`Y
`c.
`w
`w
`v
`v.
`
`

`

`Patent Application Publication May 20, 2004 Sheet 16 of 16
`
`US 2004/0098674 A1
`
`

`

`US 2004/0098674 A1
`
`May 20, 2004
`
`PLACE AND ROUTE TOOL THAT
`INCORPORATES A METAL-FILL MECHANISM
`
`COPYRIGHT NOTICE
`0001. A portion of the disclosure of this patent document
`contains material which is Subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent document or the patent
`disclosure, as it appears in the Patent and Trademark Office
`patent files and records, but otherwise reserves all other
`copyright rights.
`BACKGROUND AND SUMMARY
`0002 The invention relates to the design and manufac
`ture of integrated circuits, and more particularly, to tech
`niques, Systems, and methods for implementing metal-fill
`patterns on an integrated circuit.
`0003. In recent years, in IC manufacturing, chemical
`mechanical polishing (CMP) has emerged as an important
`technique for planarizing dielectrics because of its effec
`tiveness in reducing local Step height and achieving a
`measure of global planarization not normally possible with
`spin-on and resist etch back techniques. However, CMP
`processes have been hampered by layout pattern dependent
`variation in the inter-level dielectric (ILD) thickness which
`can reduce yield and impact circuit performance. A common
`approach for reducing layout pattern dependent dielectric
`thickness variation is to change the layout pattern itself via
`the use of metal-fill patterning.
`0004 Metal-fill patterning is the process of filling large
`open areas on each metal layer with a metal pattern to
`compensate for pattern-driven variations. The manufacturer
`of the chip normally Specifies a minimum and maximum
`range of metal that should be present at each portion of the
`die. If there is an insufficient amount of metal at a particular
`portion or “window' on the chip, then metal-fill is required
`to increase the proportion of metal in that portion or window.
`Otherwise, an insufficient amount of metal may cause bumps
`to exist in the finished chip. However, too much metal may
`cause dishing to occur. Therefore, the metal-fill proceSS
`should not cause the die to exceed any Specified maximum
`range of metal for the chip.
`0005 FIG. 1 shows a “fixed template” approach for
`performing metal-fill patterning, in which a template pattern
`is overlaid with the chip design, the results are tested with
`a separate analysis Step, and then new fixed shapes are added
`or the starting point (offset) of the fixed shapes is shifted
`until the minimum density is met in every area.
`0006 To explain further, in this approach, a chip layout
`is divided into a set of delineated portions or windows. For
`each window, the metal features or “blockages' 103 are
`identified, as shown in window 102. If the proportion of
`metal in that window is below a specified minimum per
`centage, then metal-fill patterning is performed to increase
`the amount of metal. In many cases, the designer or manu
`facturer will Specify a minimum distance around each block
`age that should not contain the additional metal-fill. AS
`shown in window 104, a fence 105 is established around
`each blockage 103 in the window to maintain this minimum
`distance around each blockage.
`0007 A fill template is selected to provide the metal-fill
`pattern. The fill template is a fixed pattern of uniform metal
`
`shapes, e.g., an array of 2 umx2 um shapes Spaced apart by
`2 um, as shown in the example fill template of window 106.
`Once a fill template has been Selected, the fenced blockage
`window 104 is overlaid upon the fill template, resulting in
`the new chip layout as shown in window 108.
`0008. At this point, a determination is made whether the
`layout meets minimum and maximum metal requirements.
`In Some cases, the Selected metal-fill pattern may contain too
`much metal, causing the new layout to exceed maximum
`metal percentages as Specified by the manufacturer. In other
`cases, the metal-fill pattern may contain too little metal,
`causing the new layout to fall beneath Specified minimum
`metal percentages. In either case, a new metal-fill pattern
`must be Selected and the Overlaying process repeated.
`0009. In certain instances, the metal-fill pattern may be
`sufficient, but must be “shifted” to properly fit against the
`fenced blockage window. For example, it can be seen in
`portion 110 of window 108 that because of the uneven
`distances between blockages, the metal-fill pattern does not
`exactly fit within the Spaces between the blockages. Thus,
`the fixed, regular pattern of the metal in the metal-fill causes
`portions 112 and 114 of the new layout in window 108 to
`contain leSS metal than other portions. This can be corrected
`by shifting the metal-fill pattern 106 against the fenced
`blockage window 104 until a more optimal metal percentage
`is achieved.
`0010. The process of re-selecting a new metal-fill pattern
`or shifting the metal-fill pattern and then re-performing the
`overlaying is iteratively repeated until the final layout Sat
`isfies the minimum and maximum metal percentage require
`ments for the chip. In effect, this fixed template approach
`may be seen as a trial and error approach in which multiple
`passes through the metal-fill Selection/overlaying process is
`needed to achieve an acceptable metal percentage. This trial
`and error approach can be costly and inefficient, particularly
`if the iterative Steps of the process must be manually
`performed. Moreover, as new chip designs become Smaller,
`the required metal percentage requirements become even
`Stricter, which may require even more passes through this
`process to achieve an acceptable metal percentage.
`0011 To overcome the disadvantages of these and other
`approaches, the present invention provides an improved
`method, System, and article of manufacture for implement
`ing metal-fill for an integrated circuit. A disclosed embodi
`ment calculates the best offset in each area to be filled and
`dynamically adjust shape widths and different shape lengths
`that best fill that area, in which only a single pass is needed
`to appropriately determine the metal-fill pattern. An embodi
`ment also simultaneously optimizes acroSS multiple metal
`fill windows such that that the process will not add shapes
`in a window that would exceed the maximum density, while
`attempting to make all windows match the preferred density,
`and meeting the minimum density.
`0012. Also disclosed is a method, system, and article of
`manufacture for implementing metal-fill that is coupled to a
`tie-off connection. An embodiment that is disclosed com
`prises a method, System, and article of manufacture for
`implementing metal-fill having an elongated Shape that
`corresponds to the length of whitespace. Also disclosed is
`the aspect of implementing metal-fill that matches the rout
`ing direction. Yet another disclosure is an implementation of
`a-place & route tool incorporating an integrated metal-fill
`
`

`

`US 2004/0098674 A1
`
`May 20, 2004
`
`mechanism. Other and additional objects, features, and
`advantages of the invention are described in the detailed
`description, figures, and claims.,
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`0013 FIG. 1 shows a fixed template approach for imple
`menting metal-fill.
`0.014
`FIG. 2 shows a flowchart of a process for imple
`menting metal-fill according to an embodiment of the inven
`tion.
`FIG. 3 illustrates partitioning a design into win
`0.015
`dows and regions according to an embodiment of the
`invention.
`0016 FIG. 4 shows a process for performing merge/sort
`of blockages according to an embodiment of the invention.
`0017 FIGS.5a, 5b, and 5c illustrate the process of FIG.
`4.
`FIG. 6 illustrates a process for identifying
`0.018
`whitespace according to an embodiment of the invention.
`0019 FIG. 7 illustrates a process for converting
`whitespace into metal-fill according to an embodiment of the
`invention.
`0020 FIG. 8 illustrates a process for splitting whitespace
`into metal-fill according to an embodiment of the invention.
`0021 FIGS. 9 and 10 show alternate metal-fill patterns
`according to an embodiment of the invention.
`0022 FIG. 11 illustrates a process for removing metal
`fill according to an embodiment of the invention.
`0023 FIG. 12 illustrates connection of metal-fill to
`ground and power.
`0024 FIG. 13 illustrates a process for removing selected
`metal-fill elements when Some elements are connected to
`power or ground.
`0.025
`FIG. 14 shows architecture for implementing a
`metal-fill mechanism according to an embodiment of the
`invention.
`
`DETAILED DESCRIPTION
`0026. The present invention is directed to an improved
`method, System, and article of manufacture for implement
`ing metal-fill for an integrated circuit. A disclosed embodi
`ment calculates the best offset in each local area to be filled
`(e.g. minimum spacing from the existing metal), and
`dynamically adjust shape widths and different shape lengths
`that best fill that area. A metal-fill window will be processed
`in one pass, with possibly different sizes or shapes of
`metal-fill in the windows. An embodiment also simulta
`neously optimizes acroSS multiple metal-fill windowS Such
`that that the process will not add shapes in a window that
`would exceed the maximum density, while attempting to
`make all windows match the preferred density, and meeting
`the minimum density.
`0027 FIG. 2 shows a flowchart of a metal-fill procedure
`according to an embodiment of the invention. Some
`example inputs to this procedure are: (a) the minimum and
`maximum fill width and length; (b) minimum, maximum
`and preferred density; (c) design rule spacing, window size
`
`and Step size; and (d) optional list of tie-off nets to connect
`to. In many cases, input parameters (a), (b), and (c) are
`Specified by the chip manufacturer. AS described in more
`detail below, the list of tie-off nets for (d) can be provided
`to connect the metal-fill to ground or power nets. The output
`of the procedure is a list of metal-fills inserted in the design.
`0028. At 202, the design is partitioned into a collection of
`windows. The required/desired window Size can be specified
`by, for example, the chip manufacturer. In this proceSS
`action, the design is divided into windows of the desired
`size, e.g., 100x100 microns or 50x50 microns.
`0029 FIG. 3 shows an example of a design that has been
`partitioned into a number of windows. Each window may
`overlap a number of other windows depending on the
`window Step size. For instance, a window Step size can be
`chosen to be one half the window Sizes. In Such case, a
`window may overlap 3, 5 or 8 other windows. In FIG. 3,
`window We overlaps eight other windows (including win
`dow Wa), window Wb overlaps five other windows, and
`window Wa overlaps three other windows.
`0030. In one embodiment, the first window starts at the
`lower left of the design. An area look-up data Structure can
`be built to Support area Searching during the metal-fill
`process. In one embodiment, a “kd-tree” (WindowTree)
`Structure is built to Support area Searching. AS known to
`those of skill in the art, a kd-tree refers to a well-known data
`Structure that Supports efficient geometric data retrieval. For
`purposes of illustration only, and not by way of limitation,
`the present embodiment of the invention is described using
`the kd-tree Structure.
`0031. After the design has been partitioned into windows,
`the windows can be clustered into defined regions (204 from
`FIG. 2). This action is optionally performed to optimize
`computing efficiency, particularly if the proceSS is con
`Strained by limitations with respect to System memory. The
`Size of each region is approximately N routing grids (or
`windows) in width and height. Each region consists of one
`or more windows to be filled. Region size is chosen to
`achieve runtime and memory consumption in linear propor
`tion to the design size. FIG. 3 illustrates a collection of
`windows that have been clustered into four regions (regions
`1, 2, 3, and 4). In this illustrated example, window Wa is in
`region 1, window Wb is in region 2, and window We is in
`region 3.
`0032 Referring back to the flowchart of FIG. 2, for each
`region (if the windows are clustered into regions), the
`present procedure performs the actions identified in box 206.
`At 208, blockages are identified in the design. These block
`ages include, for example, wires, cells, pins, and obstruc
`tions inside a cell as well as wires, pins, and obstructions in
`the design. At 210, the blockages are Sorted according to
`their respective layers in the design.
`0033. At 212, the procedure computes the pre-filled den
`sity per window per layer. Computing the density values can
`be rendered more efficient by using an abstract of Standard
`cells in the design. The abstract provides an estimated/
`composite density value that can be used for all associated
`Standard cells, instead of performing costly calculation
`activities to determine the exact density contributed by each
`portion of a Standard cell. Depending upon the Specific
`Standard cell, this approach may result in Some amount of
`
`

`

`US 2004/0098674 A1
`
`May 20, 2004
`
`inaccuracy in the final density calculations (e.g., if the cell
`Straddles two windows), which may be generally acceptable.
`0034 Blockages (rectangles) are merged and extracted to
`ensure that overlapping blockages are counted only once.
`This avoids over-calculating the density for a particular
`window. FIG. 4 depicts a flowchart of a process for merg
`ing/extracting the blockages according to one embodiment
`of the invention, which is illustrated using FIGS. 5a, 5b, and
`5c. For purposes of explanation, this Section of the detailed
`description will jump between the flowchart of FIG. 4 and
`the illustrative example of FIGS. 5a-c. At 402, the process
`builds an area look-up data Structure, e.g., a kd-tree of
`rectangles. The edges of rectangles are Sorted from left to
`right (404). At 406, the process creates lookup strips using
`the sorted edges. The example of FIG. 5a shows a set of
`three overlapping rectangles 502, 504, and 506, having
`edges 505a, 505b, 505c, 505d, 505e, and 505f. Action 406
`is illustrated in FIG. 5a with edges 505a, 505b, 505c, 505d,
`505e, and 505f being used to create lookup strips 506a,
`506b, 506c, 506d, and 506e.
`0035. For each lookup strip, the process performs the
`actions shown in box 408. At 410, the process finds rect
`angles interSecting the lookup Strip from the kd-tree Struc
`ture. The edges of the found rectangles are Sorted, e.g., from
`bottom to top (412).
`0.036
`For each found rectangle, the process performs the
`action shown in box 414. The new rectangle is formed using
`sides from the lookup Strip and the found rectangle (416).
`The bottom edge of the lookup Strip to top edge of rectangle
`is updated (418). FIG. 5a shows the found rectangles 508
`based upon the lookup strips 506a, 506b, 506c, 506d, and
`506e.
`0037 Horizontal and/or vertical merging are next per
`formed (420). FIG. 5b illustratively shows the found rect
`angles first undergoing vertical merge (530) and then hori
`Zontal merge (532). Based on the preferred routing layer,
`one can perform the merging and extracting on reversed
`direction. For example, FIG. 5c illustratively shows the
`found rectangle first undergoing horizontal merge (540) and
`then vertical merge (542).
`0038) Referring back to FIG. 2, for each layer, the
`process performs the actions shown in box 214. At 216, a
`fence is formed around each identified blockage. The correct
`design rule spacing for the fence is specified, for example,
`by the designer or manufacturer to avoid detrimentally
`impacting the functionality of the blockage Structure.
`0039) “Whitespaces” are located and identified around
`the fenced blockages. Whitespaces are open areas where
`metal-fills can be inserted without causing DRC (design rule
`checking) violations. Each whitespace is bordered by the
`edges of fenced blockages and region boundary. The pro
`cedure to find whitespaces is similar to the merge/extract
`procedure explained with reference to FIG. 4, but the
`rectangle extraction is reversed.
`0040 FIG. 6 illustrates this process of identifying
`whitespaces. Window 602a shows blockages 604, 606, and
`608. Window 602b shows a fence formed around each
`blockage. Thus, fence 610 is formed around blockage 604,
`fence 612 around blockage 606, and fence 614 around
`blockage 608. The combined geometric dimensions of each
`blockage plus it associated fence is shown in window 602c.
`
`In particular, fenced blockage structures 616, 618, and 619
`are shown. The whitespace 620 comprises the open area
`within window 602c that is not inhabited by fenced blockage
`structures 616, 618, and 619.
`0041 After whitespaces are formed, a whitespace is
`likely bordered by other whitespaces. If this occurs, the
`boundary of the whitespace is shrunk by the required
`spacing. Therefore, the joint whitespaces are separated at
`Step 220. The procedure to check if a whitespace touches
`other whitespaces is described below:
`
`Sort whitespaces from largest to smallest.
`Build kd-tree with one single largest whitespace.
`For each current remaining whitespace do
`Find whitespaces in kd-tree.
`If found whitespaces
`Adjust current whitespace boundary.
`End If
`Insert current whitespace in kd-tree
`End For
`
`0.042 Windows 702a and 702b in FIG. 7 illustrate this
`process of Separating and forming whitespaces. AS shown in
`window 702a, the edge of each fenced blockage is used to
`define the boundary of a potential whitespace portions for
`the joint whitespaces. In Some cases, multiple whitespace
`portions can be combined together to form a larger, rectan
`gular whitespace portion. For example, whiteSpace portions
`704 and 706 in window 702a are combined together to form
`the combined whitespace portion 708 in window 702b.
`0043. Once the whitespaces have been defined, each
`whitespace is split into Smaller metal-fills at Step 222 to form
`a metal-fill pattern in the whitespaces (window 702c of FIG.
`7). In one approach, each whitespace is split first in the
`direction of the preferred routing layer, then in another
`direction (e.g., a perpendicular direction) if no tie-off net is
`Selected or if the metal length is longer than the maximum
`length specified. This process creates the initial metal-fill
`shapes for the whitespace.
`0044 FIG. 8 illustrates this procedure. Shown in FIG. 8
`is a whitespace portion 802. Initially, the whitespace is split
`in the vertical direction to form a series of long wires 804 as
`a vertical metal-fill pattern. The length of the fill lines
`correspond to the length of the whitespace. Since the
`whitespace is being Split according to the existing dimen
`Sions of the individual whitespace, this inherently prevents
`the offset problem seen with the fixed template approach of
`FIG. 1 (e.g., as shown in the unbalanced metal-fill of portion
`110 in FIG.1). In one embodiment, the wire direction for the
`metal-fill matches the routing direction for the layer at
`interest. Thus, if the routing direction for the layer is
`horizontal, the initial wire-fill pattern would be a set of
`horizontal wires.
`0045. If desired, the long wires of the metal-fill pattern
`can be split again in another direction to form Smaller
`metal-fill pattern elements, as shown by elements 806 in
`FIG.8. One reason for performing this additional split is to
`provide a Smaller granularity of metal-fill elements, which
`allows greater control over the exact amount and Selection of
`metal-fill to put into (or remove) from a particular window.
`AS described in more detail below, the metal-fill elements
`
`

`

`US 2004/0098674 A1
`
`May 20, 2004
`
`can be removed to configure the window to meet minimum,
`maximum, or even preferred density values.
`0046) The exact metal-fill pattern used in a particular
`whitespace can be adjusted to change the amount of metal
`fill in each whitespace or window. If a particular window has
`a low density value, then the metal-fill pattern can be
`Selected to deposit a greater amount of metal. If a window
`already has a high density value, then the Shape, Spacing, or
`dimensions of the metal-fill pattern can be adjusted to reduce
`the amount of metal deposited in the whiteSpace for that
`window. For example, the Spacing between the metal-fill
`elements can be adjusted. FIG. 9 illustrates a metal-fill
`pattern which has a wider spacing between metal-fill ele
`ments than the metal-fill pattern of FIG. 8. In addition, the
`dimensions of the metal-fill elements themselves can be
`adjusted. FIG. 10 illustrates a metal-fill pattern in which the
`wires have a greater width than the wires of the metal-fill
`pattern of FIG. 8. It is noted that these variations in
`metal-fill (e.g., shape, width, length, offset, etc.) may occur
`acroSS multiple overlapping windows.
`0047. In addition to the minimum and maximum density
`parameters, a manufacturer often has a preferred or desired
`density for the metal-fill percentage of a given window. The
`present approach allows one to not only meet the minimum
`and maximum density requirements, but to tailor the exact
`amount of metal that is deposited to match the preferred
`density. To accomplish this, the post-fill density of the
`window is determined (224). If the metal-fill percentage of
`the window exceeds the preferred density, then the metal-fill
`pattern for that window is modified to attempt to match the
`preferred percentage. In one approach, this is accomplished
`by removing metal-fill from the window (226).
`0.048. The density values of neighboring, overlapping
`windows can be considered when determining how to adjust
`the metal-fill in a particular window. This is illustrated by the
`metal-fill procedure shown in FIG. 11. In this figure, the
`whitespace 1101 in window 1102a has been split both
`Vertically and horizontally to form a repeating pattern of
`whitespace elements in window 1102b.
`0049. After calculating the density in window 1102b,
`assume that it has been determined that Some metal-fill
`elements should be removed to meet the preferred density
`value in this window 1102c. Here, the window 1102 over
`laps with neighboring windows 1110 and 1112. In this
`example, further assume that window 1110 has a relatively
`low density value while window 1112 has a relatively higher
`density value. As a result, the metal-fill elements removed
`from the overlapping portions of window 1102c should be
`Selected to ensure that it both benefits and does not harm the
`ability of the neighboring windows to achieve the desired
`density. Here, Since neighboring window 1112 already has a
`relatively high density, excess metal-fill from window 1102c
`can be removed from the portion of this window that
`overlaps window 112 to help ensure that window 112 does
`not exceed the maximum density, and preferably meets the
`desired density. Since neighboring window 1110 has a
`relatively low density, no or little metal-fill is removed from
`the overlapping portion between window 1110 and window
`11102C.
`0050. The following describes an embodiment of an
`approach for removing metal-fill if there are windows that
`exceed preferred density after computing post-filled density
`for all windows:
`
`Build kd-tree from all metal-fills created.
`Sort windows with largest density first.
`For each window do
`If window density less than preferred then
`exit window loop.
`Find metal-fills in window from kd-tree.
`For each found metal-fill do
`Evaluate impact of density on neighboring windows.
`Assign a score to each metal-fill.
`End For
`Remove metal-fills with best scores. This minimizes impact on
`neighboring windows while attempting to achieve preferred
`density.
`End For
`
`0051. The list of metal-fills is maintained to track the
`changes to the design (228).
`0052 At 232, the metal-fill wires are processed with
`respect to tie-off nets (if they exist). In conventional Systems,
`metal-fill is left floating on the chip. In the present invention,
`the metal-fill can be designed to tie-off at either power or
`ground. This aspect of the invention is illustrated in FIG. 12.
`Once again, the process begins with an identified whitespace
`1202 that is split into a set of wires 1204 to form the
`metal-fill. Here, a first wire 1206 has been connected to Vcc,
`while wires 1208 and 1210 have been connected to ground.
`In one embodiment, a Search can be made to determine if
`there are available power and/or ground connections that can
`be made, either on the Same layer or on another layer. If the
`available connection is on another layer, then a via is
`dropped to the appropriate layer to make the connection. If
`the available connection is on the same layer, then the wire
`in the metal-fill can be routed to that connection on the same
`layer. In fact, one wire can be routed to another wire in the
`metal-fill to make the power or ground connection, as shown
`by route 1212 between wires 1210 and 1214 in FIG. 12.
`0053. The following describes an embodiment of a pro
`ceSS for implementing the metal-fill wires to connect to
`tie-off nets:
`
`If tie-off net exists
`Create ConnectTree using wires of tie-off nets
`While ConnectTree exists do
`For each floating fill in list do
`Find tie-off target in ConnectTree
`If target found
`Drop via to make connection
`Mark this fill as connected fill
`End If
`End For
`Delete ConnectTree
`Create new ConnectTree using connected fills
`End While
`End If tie-off net
`
`In this process, a ConnectTree refers to a tree of
`0054.
`existing wires that connect to power and ground. Wire
`Segments of tie-off nets are placed in tree (kd-tree) to
`facilitate area lookup. This tree is constantly growing, Since
`any wire in the metal-fill that connects to power and ground
`provides yet another connection for power or ground that is
`
`

`

`US 2004/0098674 A1
`
`May 20, 2004
`
`accessible by other wires in the metal-fill. This process
`keeps track of these connections as a tree Structure. AS is
`evident, any later connections can be tied to any point in the
`tree of connections. Any wire type, shape or width can be
`filtered and excluded as potential target if desired.
`0.055
`For the act of finding a tie-off target in Connect
`Tree, a bounding box of each floating fill can be used to
`search in ConnectTree (kd-tree) for potential tie-off net
`targets for a connection. A potential target is then checked to
`ensure a via can be inserted without causing DRC violation.
`If Stack via is not allowed, in one embodiment, a potential
`target must be within one layer (above or below) from the
`floating fill layer. The size of the via can be selected based
`on the via rule generation definition. The metal and cut
`spacing are taken into account to ensure no DRC violations
`occur as the via is inserted.
`0056. In the step of creating a new ConnectTree using
`connected fills, the old ConnectTree is no longer needed and
`hence can be removed. The new ConnectTree is created
`using only connected fills of the last pass. The loop iterates
`until there are no more connected fill from the last pass (i.e.,
`ConnectTree is nil).
`0057 When removing metal-fill to achieve a preferred
`density, one factor that can be taken into account is whether
`a particular wire-fill element is tied to power or ground. To
`illus