A typical computer system includes at least a microprocessor and some form of memory. The microprocessor has, among other components, arithmetic, logic, and control circuitry that interpret and execute instructions necessary for the operation and use of the computer system. FIG. 1 shows a typical computer system (10) having a microprocessor (12), memory (14), integrated circuits (IC) (16) that have various functionalities, and communication paths (18, 20), i.e., buses and wires, that are necessary for the transfer of data among the aforementioned components of the computer system (10).
Microprocessors are often fabricated on an integrated circuit (IC). Because signal wires within an IC are often in close proximity to each other, the signal wires have a propensity to affect the behavior of each other. This occurs due to intrinsic capacitances (also referred to and known as xe2x80x9ccross-coupling capacitancexe2x80x9d) that are formed between signal wires operating at different voltage levels.
FIG. 2 shows a typical routing of signal wires. The routing of signal wires includes signal wires (22, 24, 26, 28). Signal wires (22, 24) are located in a first routing layer and signal wires (26, 28) are located in a second routing layer. Some amount of cross-coupling capacitance is likely to be formed between signal wire (22) and signal wire (24) because they are located relatively close to one another in the first routing layer. Similarly, in the second routing layer, the signal wire (26) and the signal wire (28) develop some amount of cross coupling capacitance. If a voltage on the signal wire (22) changes, the cross-coupling capacitance will have a tendency to affect the signal on the signal wire (24). For example, when the voltage is raised on the signal wire (22), i.e., transitions to a xe2x80x9clogic high,xe2x80x9d the cross coupling capacitance tends to raise the voltage on the signal wire (24). When the voltage is reduced on the signal wire (22), i.e., transition to a xe2x80x9clogic low,xe2x80x9d the cross coupling capacitance tends to reduce the voltage on the signal wire (24). In other words, when the signal wire (22) switches state, noise may be injected on the signal wire (24) that causes the signal on signal wire (24) to glitch, i.e., an electrical spike occurs. Signal wire (24) may also adversely affect the signal on signal wire (22). Further, cross-coupling capacitance may affect signal wires (26, 28) in the second routing layer in a similar manner.
Noise affects may be increased through other factors. For example, referring to FIG. 2, the thickness t (32) of the signal wire (22) is greater than the width w (34) of the signal wire (22), and the distance, d1 (36), is often smaller than the distance between adjacent layers, d2 (38). The dimensions of the wires and the amount of overlap of the wires between routing layers also increases the cross coupling capacitance because cross-coupling capacitance between adjacent wires, e.g., signal wire (22) and signal wire (24), is larger than the cross-coupling capacitance between wires in different routing layers, e.g., signal wire (22) and signal wire (26).
Noise is also produced due to increased processing speeds. As the rise times (or equally, fall times) of signals decrease, the rapid change in voltage differences increase the amount of noise. The noise injected on a non-switching signal can propagate to other parts of the processor. Such undesired behavior on any signal may lead to performance degradation causing timing failures and/or circuit malfunction.
There are several approaches that designers have used to combat noise caused by cross-coupling capacitance. For example, designers have increased the wiring spacing and added shield wires between signal wires. When adding shield wires, the shield wires are typically at a constant voltage. To this end, FIG. 3 shows a typical routing of shield wires for the routing of signal wires shown in FIG. 2. In FIG. 3, a shield wire (40) at logic low is placed between signal wire (22) and signal wire (24). A shield wire (42) at logic high is placed adjacent to the signal wire (24). Further, a shield wire (44) at logic low is placed in between signal wire (26) and signal wire (28). Because of the routing of shield wires as shown in FIG. 3, other signals in close proximity to the signal wire (24) are not affected significantly by the switching behavior of the signal wire (24) due to the fact that the signal wire (24) is shielded by shield wires (40, 42) that have constant values. Alternatively, the routing of shield wires (40, 42) lessens the effects of the switching behavior of other signals, e.g., signals on signal wires (22, 26, 28) that are in close proximity to the signal wire (24).
Shield wires are typically implemented such that a shield wire at logic high and a shield wire at logic low shield the signal wire. Shield wires implemented in this manner are termed xe2x80x9calternating shield wires.xe2x80x9d In FIG. 3, assigning shield wires (40, 42, 44) to alternating voltage potentials is a relatively simple task because there are only a few signal wires and the routing of the signal wires is not complex. However, when there is a large number of signal wires and there is sophisticated and complex routing, a greater number of shield wires is required, which in turn makes the process of assigning shield wires in a routing layer more complex.
In general, one aspect of the invention involves a method for facilitating the assignment of alternating voltage potentials to a set of shield wires in a routing layer of an integrated circuit. The method comprises generating vertices representing the set of shield wires: dependent on the routing layer, generating edges between the vertices, the edges representing adjacency of the set of shield wires; determining whether any assignment of voltage potentials to the vertices results in an arrangement in which at least one of the edges is positioned between vertices of the same voltage potential; dependent on the determining, selectively minimizing the edges to obtain a minimized arrangement of edges and vertices; and assigning a first indicator to at least one vertex in the minimized arrangement.
In general, in one aspect the invention involves a computer system to transform a behavioral specification. The computer system comprises a computer-readable medium having recorded thereon instructions by a processor to perform an assignment of alternating voltage potentials to a set of shield wires in a routing layer to of an integrated circuit. The instructions are for: generating vertices representing the set of shield wires; dependent on the routing layer, generating edges between the vertices, the edges representing adjacency of the set of shield wires; determining whether any assignment of voltage potentials to the vertices results in an arrangement in which at least one of the edges is positioned between vertices of the same voltage potential: dependent on the determining, selectively minimizing the edges to obtain a minimized arrangement of edges and vertices; and assigning a first indicator to at least one vertex in the minimized arrangement.
In general, in one aspect the invention involves a computer system that determines alternating voltage potentials to a set of shield wires in a routing layer of an integrated circuit. The computer system comprises a processors a memory, a display device, and software instructions stored in the memory for enabling the computer system under control of the processor, to perform: generating vertices representing the set of shield wires; dependent on the routing layer, generating edges between the vertices, the edges representing adjacency of the set of shield wires; determining whether any assignment of voltage potentials to the vertices results in an arrangement in which at least one of the edges is positioned between vertices of the same voltage potential; dependent on the determining, selectively minimizing the edges to obtain a minimized arrangement of edges and vertices; and assigning a first indicator to at least one vertex in the minimized arrangement.
In general, one aspect of the invention involves a method for assigning alternating voltage potentials to a set of shield wires in a routing layer of an integrated circuit. The method comprises: a step for generating vertices representing the set of shield wires; dependent on the routing layer, a step for generating edges between the vertices, the edges representing adjacency of the set of shield wires; a step for determining whether any assignment of voltage potentials to the vertices results in an arrangement in which at least one of the edges is positioned between vertices of the same voltage potential; dependent on the determining, a step for selectively minimizing the edges to obtain a minimized arrangement of edges and vertices; and a step for assigning a first indicator to at least one vertex in the minimized arrangement.
In general, one aspect of the invention involves a an apparatus for assigning alternating voltage potentials to a set of shield wires in a routing layer of an integrated circuit. The apparatus comprises: means for generating vertices representing the set of shield wires; dependent on the routing layer, means for generating edges between the vertices, the edges representing adjacency of the set of shield wires; means for determining whether any assignment of voltage potentials to the vertices results in an arrangement in which at least one of the edges is positioned between vertices of the same voltage potential; dependent on the determining, means for selectively minimizing the edges to obtain a minimized arrangement of edges and vertices; and means for assigning a first indicator to at least one vertex in the minimized arrangement.
Other aspects and advantages of the invention will be apparent from the following description and the appended claims.