Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-06-01
2003-04-01
Niebling, John F. (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06543043
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The field of the present invention relates to electronic design automation and, more particularly, to methods and systems for routing wires in circuit designs created through an electronic design automation procedure.
2. Background
Chip designers often use electronic design automation (EDA) software tools to assist in the design process, and to allow simulation of a chip design prior to prototyping or production. Chip design using EDA software tools generally involves an iterative process whereby the chip design is gradually perfected. Typically, the chip designer builds up a circuit by inputting information at a computer workstation generally having high quality graphics capability so as to display portions of the circuit design as needed. A top-down design methodology is commonly employed using hardware description languages (HDLs), such as Verilog® or VHDL, for example, by which the designer creates an integrated circuit by hierarchically defining functional components of the circuit, and then decomposing each component into smaller and smaller components.
The various components of an integrated circuit are initially defined by their functional operations and relevant inputs and outputs. From the HDL or other high level description, the actual logic cell implementation is typically determined by logic synthesis, which converts the functional description of the circuit into a specific circuit implementation. The logic cells are then “placed” (i.e., given specific coordinate locations in the circuit layout) and “routed” (i.e., wired or connected together according to the designer's circuit definitions). The placement and routing software routines generally accept as their input a flattened netlist that has been generated by the logic synthesis process. This flattened netlist identifies the specific logic cell instances from a target standard cell library, and describes the specific cell-to-cell connectivity.
Presently, there are two common types of low-level routing tools, also known as detail routers. The first type, known as “channel routers,” divide a chip design into channels and place junction pins (i.e., channel wire exits) between the channels. A disadvantage of channel routers is the requirement in advance of good channel ordering—i.e., a defined order of processing channels such that the final physical layout does not contain an over-abundance of cross-overs or too many unnecessarily lengthy wires. Another disadvantage of channel routers is that mis-matches of junction wire ordering often occur, leading to twisted wires and wasted space. These disadvantages can lead to a larger chip size than might otherwise be required.
The second type of detail router are known as “maze routers.” Maze routers tend to route wires individually, with only an initial ordering of all wires, and thus ordering the junction wires arbitrarily. Hence, they suffer from the same problem of mis-matching of junction wire ordering, and can also lead to an unnecessarily large chip size.
To address the problems associated with channel ordering in conventional detail routers, some methods have been developed which use a rough one-pass ordering to arrive at an initial channel ordering. Examples of these methods are described in, for example, D. F. Wong and M. Guruswamy, “Channel Ordering for VLSI Layout with Rectilinear Modules,”
IEEE Transaction of Computer-Aided Design,
Vol. 10, No. 11 (Nov. 1991), pp. 1425-1431, and W. M. Dai et al, “Routing Region Definition and Ordering Scheme for Building-Block Layout,”
IEEE Trans. Computer-Aided Design,
Vol. CAD-4 (July 1985), pp. 189-197. According to these techniques, based on the resulting channel order from the rough one-pass ordering, the channels routed first decide the junction wire orders/positions for channels routed later, in essentially a unidirectional manner. However, since these unidirectional methods do not consider the effects of later channels on the previous channels, the resulting channel ordering can often be poor at the junctions. Furthermore, most attention by designers and researchers has focused primarily on optimizing the metrics internal to the channels, but have failed to sufficiently address inter-region constraints on channel ordering.
A subsidiary problem during the routing process is known as the track ordering problem, which involves associating wires in the same channel with specific tracks in the channel. The simplest approach arbitrarily assigns wires to tracks within a single channel. However, such as arbitrary assignment will generally fail to arrive at an optimal physical layout, and may, for example, lead to numerous wire crossovers. Another approach is to address track ordering through the defined channel ordering; that is, to assign tracks based upon the optimal wire layout from channel to channel following the same order as the channel layout. This approach also will generally fail to arrive at an optimal physical layout, because the amount of information that is utilized in ordering the tracks is generally limited due to the dependence of the technique on the sequence of channels handled in channel ordering.
One approach to the track ordering problem involves topological (i.e., planar) ordering, and is generally. described in P. Groeneveld, “Wire Ordering for Detailed Routing,”
IEEE Design
&
Test of Computers
(1989), pp. 6-17. Topological ordering techniques generally attempt to minimize the crossings between nets and to maintain as much planarity as possible at each junction based on the topology derived from the placement graph. It can be successfully applied to remove wire twisting at junctions. However, topological ordering techniques typically do not address the sequence of junctions to be operated on, nor the potential interaction between junctions and channels.
A potential problem in all circuit design layouts is crosstalk, which, from a general standpoint, is signal interference that can occur between adjacent or closely spaced wires. Crosstalk can lead to increased noise in signals carried across the affected wires, which in turn can lead to deteriorated noise margins and, possibly, to errors in signal propagation. A variety of techniques have been developed to estimate and/or reduce the potential for crosstalk in electrical circuits. For example, certain crosstalk techniques are described in T. Xue, et al., “Post Global Routing Crosstalk Risk Estimation and Reduction,” DAC Proceedings (1996), pp. 302-309. However, the ability of such conventional techniques to reduce crosstalk is limited because conventional global routers are typically unable to provide the type of detailed track location information needed to calculate the exact noise levels.
There is a need for a technique for automated circuit design tools which permit more efficient routing of wires and, particularly, for reducing twisted wires and minimizing wire lengths. There is further a need for an automated design tool useful for routing wires and also useful for reducing the potential for crosstalk between near or adjacent wires.
SUMMARY OF THE INVENTION
The invention provides in one aspect systems and methods for routing wires using an automated circuit design tool.
In one embodiment as disclosed herein, order negotiation is used to adjust the ordering of wires back and forth between conduits (i.e., routing regions, as further explained herein) by considering both inter-region and intra-region constraints on the layout of the wires. In a preferred embodiment, order negotiation is carried out by looking both forward and backward during the processing of channels, and switching back and forth between conduits in adjusting the wire orders for each net. The order negotiation process may flexibly account for intra-region, crosstalk, and grouping constraints, as well as conduit exit constraints. Further, the order negotiation process may be capable of working with loosely defined conduits and imperfect conduit ordering, and does not necessarily require well-defined channels and channe
Chyan David
Wang Xiao-Dong
Bingham & McCutchen LLP
Cadence Design Systems Inc.
Whitmore Stacy
LandOfFree
Inter-region constraint-based router for use in electronic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Inter-region constraint-based router for use in electronic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inter-region constraint-based router for use in electronic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3010237