System and method for transposing wires in a circuit design

[0002] 1. Field of the Invention

[0003] This invention relates to tools for designing digital circuits and analyzing digital circuit designs, and particularly to transposing wires in digital circuit designs.

[0004] 2. Description of the Related Art

[0005] One of the goals in designing synchronous integrated circuits, and particularly very large scale integrated (VLSI) circuits, including application specific integrated circuits (ASICs), general purpose processors, embedded processors, and digital signal processors (DSPs), is high speed operation. To that end, a variety of computer aided design (CAD) tools are used to design, analyze, and simulate integrated circuits. In the process of designing integrated circuits, often referred to as electronic design automation (EDA), a particular integrated circuit (or section thereof) is typically described by a netlist. The netlist is a list of circuit components or cells and interconnections between the circuit components. The various cell input terminals and output terminals through which cells are connected to each other are often referred to as pins or nodes. The speed at which a given circuit can operate depends in large part on the timing of signals arriving at, and being transmitted from various cells in the circuit.

[0006] For example, a bus, i.e., a group of two or more wires (sometimes referred to as nets or bits) that carry closely-associated signals in an electronic design, included in an integrated circuit design can require specific timing characteristics to maintain maximum operating speed for the circuit. If the circuit design depends on well defined relationships among the signals transmitted on the bus lines, anything that affects the signal timing on individual lines of the bus, and/or the relationship among signals on the bus, can affect the overall performance of the circuit. In the case of bus lines, one cause of relative signal timing delays is impedance differences among bus lines. If the impedances of the wires in a bus differ significantly, then signal arrival times, signal edge rates, and clock skew can be very different from one bit line to the next. Apart from the electrical characteristics of the material making up a wire, the impedance of the wire depends on its length, and inductive effects (both self and mutual) associated with the wire. These effects can be particularly significant in buses where the outer wires of the bus present a different impedance than the inner wires of the bus.

[0007] Since EDA routing tools are often used to route clock, signal, data, and power paths between various elements of an integrated circuit, one way to alleviate the impedance mismatch among bus wires is via the design rules used in conjunction with the tools. Examples of such routing tools include FlexRoute by Synopsys, Inc., and Envisia Silicon Ensemble (including the Integrated Circuit (IC) Craftsman package) by Cadence Design Systems, Inc. For example, maximum wire length can be restricted to control the total resistance in a line; wire width and length matching can be used to match pairs; and wire spacing can be adjusted to control capacitance and crosstalk between lines. These techniques often have limited effect on the problem, and can cause the area on the die needed for the integrated circuit to increase.

[0008] Another common solution is to design a unique driver for each wire in the bus. If all of the lines on the bus are not identical in terms of electrical loading, then the driver for each line has to be individually adjusted to match the characteristics of the specific bus line. Of course, having unique drivers for each wire in the bus can significantly complicate the circuit design process. Moreover, there can be circuit area costs and power consumption costs associated with the unique drivers.

[0009] Still another solution is to transpose wires in the bus, thereby giving the wires similar impedances, and obviating the need for individually designed drivers for each of the bus lines. Unfortunately, prior art methods for transposing bus lines have relied on the manual efforts of a circuit designer to select buses from a circuit design, and decide where and how to reroute the bus lines. This process can also be very time consuming, does not guarantee optimal re-routing of bus lines, and thus, may eliminate any benefit gained from not having to design specific drivers for each of the bus lines.

[0010] Accordingly, it is desirable to have integrated circuit design tools and techniques for automatically transposing wires in order to reduce cross coupling and to balance bus loading.

[0011] It has been discovered that an automatic and parameterized computer implemented method for transposing wires in an integrated circuit design can yield bus lines with similar impedances, and therefore similar signal transmission characteristics. Using a specially designed CAD tool, a user can specify a transposing pattern, intervals at which to transpose wires, and a metal layer through which to accomplish the transposing in the integrated circuit. Using a routing database the tool then automatically determines the locations in the design where transposing needs to be performed, re-routes the wires being transposed while optimizing the circuit design space being used, and re-routes (or causes the re-route of) any other wires affected by the transposing process. The result is a new version of the routing database reflecting transposition, but with no change to the circuit's netlist.

[0012] Transposition of bus lines may also be desirable to make lines that switch in similar logic direction run adjacent to each other. This can help reduce the coupling capacitance of the adjacent lines, and results in a lower delay for a signal propagating through a wire.

[0013] Accordingly, one aspect of the present invention provides a computer implemented method of transposing a plurality of wires in a circuit design. A database is provided including a plurality of wire descriptions, each of the plurality of wire descriptions including a path traversed by the wire in the circuit design. A transposing region is defined around portions of a first and a second path corresponding to a first and a second wire description of the plurality of wire descriptions, respectively. The transposing region dividing the first path into a first leading path segment, a first transposing path segment, and a first ending path segment, and the transposing region further dividing the second path into a second leading path segment, a second transposing path segment, and a second ending path segment. The first transposing path segment is replaced with a first new transposing path segment between the first leading path segment and the second ending path segment, thereby modifying the first path for the first wire description. The second transposing path segment is replaced with a second new transposing path segment between the second leading path segment and the first ending path segment, thereby modifying the second path for the second wire description.

[0014] In another aspect of the present invention provides a computer implemented method of transposing a plurality of wires in a circuit design. A database is provided including a plurality of wire descriptions, each of the plurality of wire descriptions including a path traversed by the wire in the circuit design. A wire transposing pattern is received for application to at least a first and a second wire description of the plurality of wire descriptions. A first portion of the first wire description path is replaced with a first new portion, and replacing a second portion of the second wire description path with a second new portion such that the first wire description path and the second wire description path are transposed according to the transposing pattern.

[0015] In another aspect of the invention, an apparatus includes a processor, a memory coupled to the processor, and a circuit design program at least partially storable in the memory, and executable on the processor. The program includes a wire selection routine, a transposing region definition routine, and a replacement routine. The wire selection routine selects a plurality of wire descriptions from a database, each of the plurality of wire descriptions including a path traversed by the wire in a circuit design. The transposing region definition routine defines a transposing region around portions of a first and a second path corresponding to a first and a second wire description of the plurality of wire descriptions, respectively. The transposing region divides the first path into a first leading path segment, a first transposing path segment, and a first ending path segment, and the transposing region further divides the second path into a second leading path segment, a second transposing path segment, and a second ending path segment. The replacement routine replaces the first transposing path segment with a first new transposing path segment between the first leading path segment and the second ending path segment, thereby modifying the first path for the first wire description.

[0016] The present invention may be better understood, and its numerous objects, features, and advantages made apparent to those skilled in the art by referencing the accompanying drawings.

[0017] FIG. 1 is a block diagram of a computer system for implementing the tools and techniques of the present invention.

[0018] FIGS. 2A-2E illustrate several steps in transposing wires for a two-wire bus.

[0019] FIGS. 3A-3B illustrate two metal layers used to transpose wires for a four-wire bus.

[0020] FIGS. 4A-4C illustrate examples of different wire transposing patterns.

[0021] FIG. 5 is a flow chart illustrating an integrated circuit wire transposing procedure.

[0022] In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be obvious, however, to one having ordinary skill in the art that the present invention may be practiced without these specific details. In other instances, well-known circuits, structures and techniques have not been shown in detail in order not to unnecessarily obscure the present invention.

[0023] Because of the complexity of designing integrated circuits, many of the design steps are performed on a computer system. FIG. 1 illustrates a block diagram of a computer system 100 for implementing the design tools discussed below. Computer system 100 includes a processor 110 and a memory 120 coupled together by communications bus 105. Processor 110 can be a single processor or a number of individual processors working together. Memory 120 is typically random access memory (RAM), or some other dynamic storage device, and is capable of storing instructions to be executed by the processor, e.g., wire transposing software 130, and information used by the instructions, such as routing database 140. Memory 120 is also used for storing temporary variables or other intermediate information during the execution of instructions by the processor 110.

[0024] Wire transposing software 130 is one example of a software design tool, and in the present example, it is illustrative of a wire transposing method implemented in software. Those having ordinary skill in the art will ready recognize that the techniques and methods discussed below can be implemented in software using a variety of computer languages, including, for example, traditional computer languages such as assembly language, Pascal, and C; object oriented languages such as C++ and Java; and scripting languages such as Perl. Routing database 140 is one example of information that can be used by software such as wire transposing software 130 as part of the integrated circuit design process. Additionally, software 130 can be provided to the computer system via a variety of computer readable media including electronic media (e.g., flash memory), magnetic storage media (e.g., hard disk 158, a floppy disk, etc.), optical storage media (e.g., CD-ROM 160), and communications media conveying signals encoding the instructions (e.g., via a network coupled to network interface 154).

[0025] Computer system 100 also includes devices such as keyboard 150, mouse 152, network interface 154, graphics & display 156, hard disk 158, and CD-ROM 160, all of which are coupled to processor 110 by communications bus 107. It will be apparent to those having ordinary skill in the art that computer system 100 can also include numerous elements not shown in the figure, such as additional storage devices, communications devices, input devices, and output devices, as illustrated by the ellipsis shown.

[0026] Timing database 140 includes information produced by a router tool based on a netlist of the circuit design provided to the tool. Routers (such as the aforementioned FlexRoute and IC Craftsman) generally fall into one of two classes: channel-based and area-based. Channel-based routing assumes that all cells (devices) are arranged neatly into rows, with reserved tracks for interconnects. The placement of the rows is relative because the track width is adjusted by the tool to ensure 100% routing completion. The main disadvantages to channel-based routers are that they result in unpredictable die size, force iteration with floorplanning and impose restrictions on cell design. Area-based routing assumes that cell placement is fixed, and it does its best to complete the route within a known area and die size. Area-based routers enjoy the advantages of predictable die size without floorplan iteration and greater flexibility in cell design. The traditional disadvantages with area-based routers are that they do not guarantee 100% route completion and may not make best use of available silicon area.

[0027] Additionally, routing algorithms generally fall into two categories: gridded or gridless. Gridded routers divide the routing area in a uniform grid for every metal layer. This is equal to width plus spacing for that metal layer. Gridded routers require that all the wires on any metal layer use one grid or a whole integer multiple of the grid for routing any wire. This approach may waste die space, for example with a wire that only needs 1.2 times the grid. The main advantage of gridded routers is that they can handle very large designs. One disadvantage is that they cannot efficiently handle variable width and spacing. With the advent of 0.25 micron and below technologies, variable width and spacing is required for long wires to satisfy noise, delay, crosstalk or signal integrity issues. A gridless router is a shape-based or object-based router that views pins, wires and blockages as objects and routes around them instead of using a routing grid. The advantage of a gridless router is that it gives the user complete control over wire width and spacing. It can address signal integrity and crosstalk issues by using wide spacing for wires and can also address delay and electromigration issues by increasing wire width without any area penalty. Gridless routers can also handle blocks with different pin pitches thereby making it easier to route blocks with different physical characteristics (such as intellectual property blocks) in a given design. The main disadvantage of a gridless router is that it can only handle a limited number of objects or shapes. Therefore, gridless routers are mainly used for top level routing or interblock routing where the number of nets is limited to 10,000 to 25,000. They are generally not used for inside-the-block or standard cell routing because of capacity limitations.

[0028] Whatever the type of routing tools used, the end product is a routing database that describes the geometry of the wires between circuit elements, including the paths that the wires take within and between metal layers of the integrated circuit's interconnect scheme.

[0029] FIGS. 2A-2E illustrate the effects of employing an automated wire transposing procedure on a two-wire bus. Note that a two-wire bus is shown for simplicity, and that the transposing procedure described can be implemented with any size bus or collection of wires.

[0030] In FIG. 2A, two wires 210 in first metal layer 200 form the bus lines. Each of the wires 210 has an associated track 220 for design purposes, thereby defining the space needed surrounding the wire to satisfy the circuit's design rules. As illustrated, each track 220 has a track width 225 defined by the design rules for the circuit. Another design rule is implemented through the wire separation or pitch 215. As is well known to those having ordinary skill in the art, the various design parameters 215, 225, and others not illustrated, are specified by circuit designers, and affect the routing of wires in the circuit design.

[0031] The size of transposing region 230 is defined based on the number of lines to be transposed, the design rules being implemented, and the metal layers in which the transposing is to occur. For example, transposing the two wires will require a transposing segment from one wire to be routed through a second metal layer, while a transposing segment for the other wire will remain in first metal layer 200. Thus, transposing region 230 should be at least as wide as track 220 for first metal layer 200 (and at least as wide a second metal layer track for second metal layer 250). In practice, transposing region 230 is wider to ensure that no design rules are violated. Thus, the width of a transposing region can generally be represented as:

[0032] b/2+d,

[0033] where b is number of bus lines in the bus, and d is some multiple of track width required to satisfy design rules. Typically, d is either one (as illustrated in FIG. 2A) or two track widths.

[0034] FIG. 2B illustrates the portions of wires 210 removed in first metal layer 200 in preparation for inserting a transposing segment. Note that in practice, no real segment is removed from the wires, but instead appropriate changes are made to the wire descriptions corresponding to wires 210 in routing database 140, and the nature of those changes depends upon the format of the database. In FIG. 2C, first metal layer to second metal layer vias 235 are inserted, as is a transposing segment 240. As previously noted, only half (in this case one wire) of the bus wires are transposed in first metal layer 200. Vias 235 provide interconnect paths to second metal layer 250, which is the metal layer that contains transposing segment 255 as illustrated in FIG. 2D. FIG. 2E illustrates the two metal layers superimposed upon each other.

[0035] FIGS. 3A-3B illustrate two metal layers 300 and 350 that accomplish transposing of the wires in a four-bit bus. Vias 335 are inserted to accommodate transposing segments 355 through metal layer 350, while transposing segments 340 are placed in metal layer 300. The examples of FIGS. 2A-2E and 3A-3B illustrate a typical transposing pattern where outer bus lines are moved inward, and vice versa. This of course is only one of the many transposing patterns that can be used, and that will be well known to those having ordinary skill in the art. FIGS. 4A-4C illustrate examples of three other transposing patterns: nearest-neighbor, next-in-line, and next-nearest-neighbor, respectively.

[0036] FIG. 5 is a flow chart illustrating an integrated circuit wire transposing procedure utilizing information from routing database 140. As indicated by wire transposing software 130, some or all of the procedure illustrated in FIG. 5 is usually performed by software.

[0037] The procedure begins at 500 where wires to be transposed are selected. This can be accomplished in a number of ways. For example, if routing database 140 labels all of the wires belonging to a particular bus with some designation unique to that bus, a user could simply request that that bus be transposed. Alternately, a user could request that all busses in database 140 be transposed, or the user could specifically select individual wires to undergo the transposing procedure. The manner in which wires and/or buses are selected can be parameter files used by the tool, parameters entered via a command line, a graphical user interface, or any other suitable means. Moreover, wire and/or bus selection need not be performed by a user, but can be based on software intelligence. For example, the tool can select buses to be transposed based on the results of the analysis of the parasitic effects occurring in the circuit.

[0038] In 510, one or more transposing patterns are selected. Different transposing patterns can be selected for different busses, and indeed several different transposing patterns can be used on the same bus. Typically, wire transposing will occur at a specified interval across the length of a bus, and so that interval is also specified. In general, transposing on a particular bus will occur an even number of times, so as to render the inputs and output the same. However, this need not be the case if a facility is included for revising the netlist associated with circuit elements receiving the bus lines. Other parameters, such as the metal layer through which some of the transposing segments are routed are also selected in 510. Although it is preferred that only one additional metal layer be used for transposing (i.e., the metal layer in which the original bus lines are routed, and one additional layer for transposing half of the lines), multiple metal layers can be used.

[0039] The size of the transposing region is determined in 520. As noted above, with regard to transposing region 230, the size of the transposing region can depend on the number of wires being transposed, the pattern, design rules for the circuit, and the metal layers used. For example, if a transposing pattern is selected where the transposed lines are not neighbors, a larger transposing region may be needed to accomplish transposing within the confines of the design rules. In 530 wire descriptions are modified according to the transposing pattern. The portions of the wire paths that are modified are generally limited to those portions or segments of the paths that fall within the transposing region.

[0040] In 540, whether the transposing requires rerouting of other wires is determined. For example, those transposing segments that are placed in a metal layer different from that which contains the original bus may interfere with existing wires. The portions of the wires that are displaced, e.g., portions that are removed based on the size of the transposing region must be accounted for. If re-routing is needed, wire re-routing is performed in 550 by a routing tool. This can be accomplished by designating the transposing region “off-limits” and requiring the router to re-route affected wires. Alternatively, the re-routing can be postponed for a subsequent re-routing iteration for all wire that must be re-routed. If no re-routing is needed, the procedure proceeds to 560. If additional transposing is to be performed, then operation returns to 520. For example, if a user specified that transposing occur at 500 μm intervals on a bus that is approximately 2000 μm long, then the process must be repeated. When there is no longer a need to transpose wires in the selected group of wires and or bus, the procedure ends. Of course, this procedure could be repeated numerous times for a given circuit design depending on the need to transpose different busses or wire groups.

[0041] The description of the invention set forth herein is illustrative and is not intended to limit the scope of the invention as set forth in the following claims. Variations and modifications of the embodiments disclosed herein may be made based on the description set forth herein, without departing from the scope and spirit of the invention as set forth in the following claims.