# Patent

## Title
Adaptive power routing and shield sharing to reduce shield count

## Abstract

Described herein are two techniques referred to as “Adaptive Power Routing” and “Shield Sharing To Reduce Shield Count,” that allow power routing and signal routing to be integrated in a manner that provides more efficient and compact layout of design blocks as compared to traditional techniques. Adaptive power routing refers to completion of power routing to be postponed to the signal routing phase, at which time signal shielding requirements are also used to complete the power routing along with predefined power delivery constraints. Shield sharing optimization refers to the more efficient use of previously routed power lines and to the insertion of a reduced number of additional power lines so as to satisfy both shielding requirements and power supply requirements in a gridless environment. These two techniques allow routing in highly congested regions containing performance-critical and/or noise-sensitive signals to be manufactured using less die area than would be required with traditional routing methodologies and algorithms.

## Background
FIELD
The present U.S. patent application is a continuation of U.S. patent application Ser. No. 09/967,797, filed Sep. 28, 2001 now U.S Pat. No. 6,622,294.
The invention relates to integrated circuit layout. More particularly, the invention relates to area-efficient techniques for placing and routing signal nets and power and ground supply lines in an integrated device layout to control electrical cross-coupling between adjacent signal lines.


BACKGROUND
As processes for manufacturing integrated devices allow minimum line sizes to decrease, the potential for interconnect noise due to switching cross-coupling capacitance increases. This switching cross-coupling capacitance increases the difficulty of converging high performance circuits by widening the transition windows of signals to account for unpredictable transition states of neighboring signals, as well as by causing failures. Convergence refers to conditions under which all timing requirements are met.
In view of this situation, designers often attempt to reduce switching cross-coupling capacitance by shielding sensitive signal nets using power supply (Vcc) or ground (Vss) lines. The set of lines providing any combination of a positive supply voltage, a negative supply voltage and/or ground are referred to herein as “power lines.” Shielding can be accomplished by placing sensitive signal nets adjacent to pre-existing power lines or by adding power lines adjacent to the sensitive signal lines for the purpose of shielding.
With the effects of switching cross-coupling capacitance increasing with each generation of integrated device manufacturing processes, the proportion of signals requiring shielding, and consequently the area used by the shields also increases. Because design blocks layouts are often wire-limited, an increase in the number of power lines required solely for shielding increases the die area required to manufacture the integrated device.
Furthermore, detailed shielding requirements are available only at late stages in the design process, at which time the die area available to lay out each converged design block may already have been allocated. In such a scenario, if the layout of a converged design block cannot be carried out in its planned area, extensive delays can be incurred due to redesign of the surrounding design blocks.
L. He, “Simultaneous Shield Insertion and Net Ordering for Capacitive and Inductive Coupling Minimization,” Proc. ISPD'00 (hereinafter “the He Paper”) discloses a technique for integrated shielding and signal net ordering. However, the He Paper focuses on signal net ordering and shield insertion primarily for inductive noise under a simplistic model and is not well suited to layouts containing may prerouted signal nets and shields, which is common. Furthermore, the He Paper does not address either shield sharing or power grid perturbation.



BRIEF DESCRIPTION OF THE DRAWINGS
The invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings in which like reference numerals refer to similar elements.
FIG. 1 is one embodiment of a flow diagram for power supply and signal net routing.
FIG. 2 illustrates a block diagram of one embodiment of an electronic system.
FIG. 3a illustrates a sample routing of signal nets and power lines using traditional routing methodologies.
FIG. 3b illustrates the routing of the signal nets and of power lines using adaptive power routing and shield sharing to reduce shield count.
FIG. 4 illustrates adaptive power routing in an integrated circuit design block.



DETAILED DESCRIPTION
Techniques for power supply routing in an integrated device such that the power supply lines are used to shield signal lines are described. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the invention. It will be apparent, however, to one skilled in the art that the invention can be practiced without these specific details. In other instances, structures and devices are shown in block diagram form in order to avoid obscuring the invention.
Reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment.
It has been noted by design engineers in the field of integrated circuit (IC) design that process migration often results in an increase in interconnect noise induced due to switching cross-capacitance, which results in increasing difficulty in designing functional circuits. Furthermore, switching cross-capacitance increases the difficulty of converging high performance circuits by widening the transition windows of signals to account for unpredictable transition states of neighboring signals.
In view of these factors, circuit designers attempt to minimize switching cross-capacitance by shielding sensitive signal nets using power supply (Vcc) and ground (Vss) lines (collectively “power lines”). As described herein, by integrating two traditionally disjoint phases of the layout process (viz., power routing and signal routing) in a way that satisfies both shielding and power delivery integrity constrains while using a reduced number of power lines, the disadvantages of traditional technologies can be overcome.
Described herein are two techniques referred to as “Adaptive Power Routing” and “Shield Sharing To Reduce Shield Count,” that allow power routing and signal routing to be integrated in a manner to provide more efficient and compact layout of design blocks as compared to traditional techniques. Adaptive power routing refers to a technique that allows the completion of power routing to be postponed to the signal routing phase, at which time signal shielding requirements are also used to complete the power routing along with predefined power delivery constraints. The phrase “design block” refers to a collection of circuit elements.
Shield sharing to reduce shield count refers to a technique to use previously routed power lines more efficiently and to insert a reduced number of additional power lines so as to satisfy the shielding requirements of delay- and/or noise-sensitive signals. In one embodiment, this can be accomplished efficiently in a gridless routing environment. This technique along with adaptive power routing allows routing in regions containing sensitive signals (e.g., dynamic logic circuits) to be completed using less die area than would be required with traditional routing methodologies and algorithms.
In general, unlike traditional routing methodologies where power routing is completed prior to signal routing, the technique described herein results in a postponement of detailed power routing until later in the layout flow by integrating the detailed power routing adaptively into signal routing as described with respect to FIG. 1, which is a flow diagram of one embodiment of a technique for power supply and signal net routing. If a local region has insufficient shields subsequent to signal routing, additional power lines can be inserted as part of the adaptive power routing in order to maintain power delivery integrity.
Prior to layout, the timing and noise characteristics of the circuit are analyzed to determine wire and device sizes as well as the shielding requirements for signal nets, 100. Signal nets are ordered by the degree of freedom in their placement and by their shielding requirements, 110. In one embodiment, the degree of freedom of a signal net is determined by the number of available tracks within the cumulative span of its driver(s) and by the number of shields required by the signal net.
In one embodiment, the most constrained signal net is routed gridlessly along with any associated shields, 120. Using the ordering described above, each signal net is placed so as to reuse previously routed shields as much as possible. During this process, 125, the ordering of the signal nets is dynamically updated, 110, with the most constrained remaining signal net and shields being routed at each stage, 120. The reordering and placement of signal nets and associated shields, if any, is repeated until all signal nets are routed, 130. At this stage, the polarity of the shields is unassigned.
The polarity of the existing power lines as well as existing and newly inserted shield lines is assigned in a manner to satisfy the power pitch, 140. The power pitch is the maximum allowable distance between adjacent power lines of opposite polarities for a particular manufacturing process. The power pitch is a predetermined value that is known prior to layout of signal nets and power lines. If assigning of polarities to the shield lines does not provide enough power lines to satisfy the power pitch, new power lines are inserted, 150.
In one embodiment, the region as defined by a previous power line and the routing track one power pitch beyond that power line is iteratively searched for shields starting from the far end of the region and moving toward the existing power line. If a shield is found, that shield is treated as part of the power grid and assigned a polarity opposite of the previous power line. Thus, the separation between the existing power line and the new power line is no greater than the power pitch in this case, thus ensuring power delivery integrity. More significantly, no new power line needs to be added in this case in contrast to traditional routing methodologies.
A new power line is explicitly added, 160, only if no shield exists within the power pitch region. Even in this case, the techniques described herein provide more efficient routing completion than traditional techniques by allowing the power lines to be assigned to any unused track over a region of equal width to the power pitch. In contrast, traditional non-adaptive power routing requires that the power line be added to a considerably smaller region. Thus, the number of power lines in the layout is less than a corresponding layout using traditional methodologies, which results in a more compact layout.
The shields that have not had polarities assigned are assigned, 170. In one embodiment, these shields are assigned Vss; however, these shields can also be assigned Vcc.
FIG. 4 illustrates an integrated circuit design block. Integrated design block 400 includes multiple signal nets and their associated shield lines that are not illustrated for reasons of simplicity of description. In one embodiment, after signal nets and associated shield lines are routed, a power grid is extracted from the existing shield lines as much as possible with additional power lines being explicitly added only where necessary to satisfy power delivery requirements.
In one embodiment, extraction of a power grid from shield lines placed in integrated circuit design block 400 starts at boundary 460. Any boundary can be used as a starting point and non-boundary starting points can also be used. A first region is defined with respect to boundary 460. In one embodiment, the first region is one half of a power pitch




  
    (
    
      λ
      2
    
    )
  
  ;




however, the first region can be defined in another manner.

The first region is searched starting at boundary (dashed line) 420 opposite starting boundary 460. The dashed lines of FIG. 4 are for illustration purposes only and are not part of the integrated circuit design block layout. The tracks of the first region are searched for a shield line that is the greatest distance from boundary 460. In the example of FIG. 4, shield line 410 is the shield line within the first region that is the greatest distance from boundary 460. Shield line 410 is used as part of the power grid and assigned a polarity (either Vcc or Vss).
A second region of design block 400 is defined based on shield/power line 410 as the starting boundary. In one embodiment, regions beyond the first region are defined as a power pitch (λ) or the boundary of the design block, whichever is smaller. Thus, the second region is defined by shield/power line 410 and dashed line 440.
The second region is searched from dashed line 440 toward shield/power line 410 to find a shield line that is the greatest distance from shield/power line 410, if any. In the example of FIG. 4, shield line 430 is the shield line in the second region that is the greatest distance from shield/power line 410. Shield line 430 is used as part of the power grid and assigned a polarity opposite of shield/power line 410.
A third region of design block 400 is defined based on shield/power line 430 as the starting boundary. Using a power pitch distance, the third region is defined by shield/power line 430 and dashed line 450. As described above, the third region is searched from dashed line 450 to shield/power line 430 to find a shield line that is the greatest distance from shield/power line 430. In the example of FIG. 4, no shield line exists in the third region. If no usable shield line exists, a power line (not shown in FIG. 4) is explicitly added to design block 400 in a vacant track in the third region that is farthest from shield/power line 430 in order to satisfy power delivery requirements.
In one embodiment, the technique described herein is implemented as sequences of instructions executed by an electronic system. The sequences of instructions can be stored by the electronic device or the instructions can be received by the electronic device (e.g., via a network connection). FIG. 2 is a block diagram of one embodiment of an electronic system. The electronic system illustrated in FIG. 2 is intended to represent a range of electronic systems, for example, computer systems, network access devices, etc. Alternative electronic systems can include more, fewer and/or different components.
Electronic system 200 includes bus 201 or other communication device to communicate information, and processor 202 coupled to bus 201 to process information. While electronic system 200 is illustrated with a single processor, electronic system 200 can include multiple processors and/or co-processors. Electronic system 200 further includes random access memory (RAM) or other dynamic storage device 204 (referred to as memory), coupled to bus 201 to store information and instructions to be executed by processor 202. Memory 204 also can be used to store temporary variables or other intermediate information during execution of instructions by processor 202.
Electronic system 200 also includes read only memory (ROM) and/or other static storage device 206 coupled to bus 201 to store static information and instructions for processor 202. Data storage device 207 is coupled to bus 201 to store information and instructions. Data storage device 207 such as a magnetic disk or optical disc and corresponding drive can be coupled to electronic system 200.
Electronic system 200 can also be coupled via bus 201 to display device 221, such as a cathode ray tube (CRT) or liquid crystal display (LCD), to display information to a computer user. Alphanumeric input device 222, including alphanumeric and other keys, is typically coupled to bus 201 to communicate information and command selections to processor 202. Another type of user input device is cursor control 223, such as a mouse, a trackball, or cursor direction keys to communicate direction information and command selections to processor 202 and to control cursor movement on display 221. Electronic system 200 further includes network interface 230 to provide access to a network, such as a local area network.
Instructions are provided to memory from a storage device, such as magnetic disk, a read-only memory (ROM) integrated circuit, CD-ROM, DVD, via a remote connection (e.g., over a network via network interface 230) that is either wired or wireless providing access to one or more electronically-accessible media, etc. In alternative embodiments, hard-wired circuitry can be used in place of or in combination with software instructions. Thus, execution of sequences of instructions is not limited to any specific combination of hardware circuitry and software instructions.
An electronically-accessible medium includes any mechanism that provides (i.e., stores and/or transmits) content (e.g., computer executable instructions) in a form readable by an electronic device (e.g., a computer, a personal digital assistant, a design blockular telephone). For example, a machine-accessible medium includes read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; electrical, optical, acoustical or other form of propagated signals (e.g., carrier waves, infrared signals, digital signals); etc.
To illustrate the results of signal net routing and power routing using the techniques described herein, FIGS. 3a and 3b illustrate signal net routing and power routing using traditional techniques and using adaptive power routing and shield sharing, respectively. In FIGS. 3a and 3b, the solid lines represent signal nets (labeled Ni), with the numbers in parenthesis indicating the number of shields required by the associated signal nets. In FIG. 3a, the dotted lines represent the power lines, with the heavy dotted lines representing the power tracks assigned during the power routing phase prior to signal routing.
Traditional routing methodologies tend to produce trace assignments similar to FIG. 3a because these methodologies do not order the signal nets according to shielding requirements to reduce the overall number of shields required. Thus, once signal net N1 has been routed, signal net N2 is routed in the next available track along with any required shields.
In contrast, the technique described herein results in a layout like the one in FIG. 3b. Using this methodology, the signal nets to be routed in this region are re-ordered so as to share as many shields as possible (e.g., between signal nets N2 and N4). As a result, additional power lines are often not required (as in the lower portion of FIG. 3b) because power can be adequately delivered through the shields that have been routed during signal net routing.
However, because signal routing and the associated shield placement does not provide adequate power to the top portion of the layout of FIG. 3b, an additional power track as represented by the heavy dotted line in FIG. 3b is assigned to be Vcc or Vss, with polarity assigned as needed, to meet power delivery constraints.
As can be seen from FIGS. 3a and 3b, the layout produced using the adaptive power routing and shield sharing techniques results in a more compact layout than that using traditional techniques. Adaptive power routing and shield sharing thus satisfy signal routing, signal shielding and power delivery constraints in a more efficient manner than traditional techniques.
The signal net and power delivery routing techniques described herein are most effective when used on middle metal layers. The technique is less effective when used on upper metal layers where long range matching of power networks is a stringent requirement. However, in layers where power networks of adjacent design blocks are generally not required to match exactly because of dense connections through the upper layers, the techniques described herein are more effective.
In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes can be made thereto without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.

## Claims

1. A method of laying out signal lines in a design block of an integrated circuit comprising:
routing signal lines, including one or more sensitive signal lines, for a design block of an integrated circuit prior to routing sufficient power lines to satisfy power grid requirements of the design block;
routing a shielding line within the design block based on an associated sensitive signal line selected from the routed signal lines; and
routing additional power lines based on power grid requirements of the design block.

2. The method of claim 1 wherein the routing the shielding lines within the design block comprises placing the shielding lines without an associated polarity.

3. The method of claim 2 further comprising assigning polarity to the shielding lines after the signal lines and the shielding lines have been routed, the polarities being assigned such that the shielding lines and power lines satisfy a predetermined power grid condition.

4. The method of claim 1 wherein routing signal lines including one or more sensitive signal lines for a design block of an integrated circuit comprises dynamic signal line reordering.

5. The method of claim 4 wherein the dynamic signal reordering is based on one or more of: geometric constraints, shielding constraints and previously routed signal and/or power lines.

6. An article comprising a storage medium accessible by an electronic device, the storage medium to store instructions that, when executed by one or more processors, cause the one or more processors to:
route signal lines, including one or more sensitive signal lines, for a design block of an integrated circuit prior to routing sufficient power lines to satisfy power grid requirements of the design block;
route a shielding line within the design block based on an associated sensitive signal line selected from the routed signal lines; and
route additional power lines based on power grid requirements of the design block.

7. The article of claim 6 wherein the routing the shielding lines within the design block comprises placing the shielding lines without an associated polarity.

8. The article of claim 7 further comprising instructions that, when executed by the one or more processors, cause the one or more processors to assign polarity to the shielding lines after the signal lines and the shielding lines have been routed, the polarities being assigned such that the shielding lines and power lines satisfy a predetermined power grid condition.

9. The article of claim 6 wherein routing signal lines including one or more sensitive signal lines for a design block of an integrated circuit comprises dynamic signal line reordering.

10. The article of claim 9 wherein the dynamic signal reordering is based on one or more of: geometric constraints, shielding constraints and previously routed signal and/or power lines.