1. Field of the Invention
The present invention concerns wire routing to control skew, and particularly relates to wire routing during integrated circuit (IC) design.
2. Description of the Related Art
xe2x80x9cRoutingxe2x80x9d in semiconductor fabrication involves determining wiring paths between elements on the surface of an integrated circuit. As is described more fully below, certain signals, such as clock signals, require special attention during the routing process. In particular, it is desirable to have a clock signal reach all the functional elements to which the clock signal is routed at the same time. This generally allows a higher clock frequency, which in turn generally increases the performance of the integrated circuit. As is described more fully herein, the present invention relates to signal routing, particularly clock signal routing during integrated circuit design.
Integrated Circuit Basics
An integrated circuit chip (or die) includes electronic components formed on a surface of a semiconductor substrate and also includes connections between those components.
A cell is a group of one or more circuit elements such as transistors, capacitors, and other basic circuit elements grouped to perform a function. Each of the cells of an IC may have one or more pins, each of which, in turn, may be connected to one or more other pins of the IC by electrically conductive traces (or wires). The wires connecting the pins of the IC typically are formed on the metal layers of the chip, which in turn are formed on top of the chip""s semiconductor substrate.
A net is a set of two or more pins which must be connected, thus connecting the logic circuits having the pins. Because a typical chip has thousands, tens of thousands, or hundreds of thousands of pins that must be connected in various combinations, the chip generally also includes definitions of thousands, tens of thousands, or hundreds of thousands of nets, or sets of pins. The number of the nets for a chip is typically on the same order as the order of the number of cells on the chip. Commonly, a majority of the nets include only two pins to be connected; however, many nets include three or more pins. Some nets may include hundreds, thousands or tens of thousands of pins to be connected. A netlist is a list of nets including names of connected pins or a list of cells including names of nets that connect to pins of cells. Clock nets typically have around 100,000 pins.
Microelectronic integrated circuits consist of a large number of electronic components that are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in several layers.
The layout is then checked to ensure that it meets all of the design requirements. The result is a set of design files in a particular unambiguous representation known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator.
During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design.
Currently, the minimum geometric feature size of a component is on the order of 0.2 microns. However, it is expected that the feature size can be reduced to 0.1 micron within the next few years. This small feature size allows fabrication of as many as 4.5 million transistors or 1 million gates of logic on a 25 millimeter by 25 millimeter chip. This trend is expected to continue, with even smaller feature geometries and more circuit elements on an integrated circuit, and of course, larger die (or chip) sizes will allow far greater numbers of circuit elements.
Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use Computer Aided Design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time, and enhanced chip performance.
The objective of physical design is to determine an optimal arrangement of devices in a plane or in a three dimensional space, and an efficient interconnection or routing scheme between the devices to obtain the desired functionality.
The input to the physical design problem is a circuit diagram, and the output is the layout of the circuit. This is accomplished in several stages including partitioning, floor planning, placement, routing and compaction.
As noted above, a chip may contain several million transistors. Layout of the entire circuit cannot be handled due to the limitation of memory space as well as the computation power available. Therefore the circuit is normally partitioned by grouping components into blocks, such as subcircuits and modules. The actual partitioning process considers many factors such as the size of the blocks, number of blocks and number of interconnections between the blocks.
The output of partitioning is a set of blocks, along with the interconnections required between blocks. As noted above, the set of required interconnections is the netlist. In large circuits, the partitioning process is often hierarchical, although non-hierarchical (e.g. flat) processes can be used, and at the topmost level a circuit can have between 5 and 25 blocks. However, greater numbers of blocks are possible and contemplated. Each block is then partitioned recursively into smaller blocks.
Floor planning and placement are concerned with selecting good layout alternatives for each block of the entire chip, as well as between blocks and to the edges. Floor planning is a critical step as it sets up the ground work for a good layout. During placement, the blocks are exactly positioned on the chip. The goal of placement is to find a minimum area arrangement for the blocks that allows completion of interconnections between the blocks. Placement is typically done in two phases. In the first phase, an initial placement is created. In the second phase, the initial placement is evaluated and iterative improvements are made until the layout has minimum area and conforms to design specifications.
The objective of the routing phase is to complete the interconnections between blocks according to the specified netlist. First, the space not occupied by blocks, which is called the routing space, is partitioned into rectangular regions called channels and switch boxes. The goal of a router is to complete all circuit connections using the shortest possible wire length and using only the channel and switch boxes.
Routing is usually done in two phases referred to as the global routing and detailed routing phases. In global routing, connections are completed between the proper blocks of the circuit disregarding the exact geometric details of each wire and terminal. For each wire, a global router finds a list of channels that are to be used as a passageway for that wire. In other words, global routing specifies the loose route of a wire through different regions of the routing space.
Global routing is followed by detailed routing which completes point-to-point connections between terminals on the blocks. Loose routing is converted into exact routing by specifying the geometric information such as width of wires and also specifying, for example, a particular grid on which to route each wire. Detailed routing includes channel routing and switch box routing.
Compaction is the task of compressing the layout in all directions such that the total area is reduced. By making the chips smaller, wire lengths are reduced, which in turn reduces the signal delay between components of the circuit. At the same time, a smaller area enables more chips to be produced on a wafer, which in turn reduces the cost of manufacturing. Compaction must ensure that no rules regarding the design and fabrication process are violated.
Upon completion of physical design, the IC chip is fabricated using the information generated during physical design. Photolithography is a common technique employed in the manufacture of semiconductor devices. Typically, a semiconductor wafer is coated with a layer (film) of light-sensitive material, such as photoresist. Using a patterned mask or reticle, the wafer is exposed to projected light, typically actinic light, which manifests a photochemical effect on the photoresist, which is subsequently chemically etched, leaving a pattern of photoresist xe2x80x9clinesxe2x80x9d on the wafer corresponding to the pattern on the mask.
A xe2x80x9cwaferxe2x80x9d is a thin piece of semiconductor material from which semiconductor chips are made. The four basic operations utilized to fabricate wafers include (1) layering, (2) patterning, (3) doping and (4) heat treatments.
The layering operation adds thin layers of material, including insulators, semiconductors, and conductors, to a wafer surface. During the layering operation, layers are either grown or deposited. Oxidation involves growing a silicon dioxide (an insulator) layer on a silicon wafer. Deposition techniques include, for example, chemical vapor deposition, evaporation, and sputtering. Semiconductors are generally deposited by chemical vapor deposition, while conductors are generally deposited with evaporation or sputtering.
Patterning involves the removal of selected portions of surface layers. After material is removed, the wafer surface has a pattern. The material removed may form a hole or an island. The process of patterning is also known to those skilled in the relevant art as microlithography, photolithography, photomasking and masking. The patterning operation serves to create parts of the semiconductor device on the wafer surface in the dimensions required by the circuit design and to locate the parts in their proper location on the wafer surface.
Doping involves implanting dopants in the surface of the wafer through openings in the layers to create the n-type and p-type pockets needed to form the N-P junctions for operation of discrete elements such as transistors and diodes. Doping is generally achieved with thermal diffusion (wafer is heated and exposed to the desired dopant) and ion implantation (dopant atoms are ionized, accelerated to high velocities and implanted into the wafer surface).
Zero-Skew Routing of Clock Nets
The performance of an IC generally is proportional to clock frequency. Maximum clock frequency, in turn, typically is limited by the maximum variation in clock delay to the different functional units implemented on the chip. Accordingly, it is preferable that the clock signal arrive at all functional units at as close to the same time as possible. In order to attain this goal, clock nets in very large scale integration systems generally require special attention with respect to routing.
The maximum difference in the arrival time of a signal at any two different components is called xe2x80x9cskew.xe2x80x9d Thus, the goal in routing clock nets is to achieve as close to xe2x80x9czero skewxe2x80x9d as is possible.
Accordingly, the chip designer is faced with the following problem: Given a clock signal input terminal and a number of clock pins (usually attached to flip-flops) distributed arbitrarily on a chip, find a route from the clock signal input terminal to each of the clock pins such that the delay to each of the clock pins (due mainly to the parasitic capacitances of the wires) is within some pre-defined range, or alternatively, skew (which is defined to be the difference between the largest delay and the smallest delay) is limited to a pre-defined amount.
The classical zero-skew routing of Tsay builds a zero-skew bottom-up tree, by choosing two pins under which the skew is zero, merging them by routing, and then finding a balance point (which will be the new tapping point) from which delays to all the bottom level flip-flops below this balance point are the same. Tsay""s technique is described in his article xe2x80x9cExact Zero Skewxe2x80x9d, IEEE, pp. 336-339, 1991. However, in many cases, Tsay""s balance point does not exist because the delay below one of the pins to be merged is much larger than that of the other. Therefore, enough wire is added in the route so that the delays are equal if the tapping point is placed at the pin with the larger delay to all its bottom level pins. It is noted that Tsay uses the Elmore delay model, which is described in Elmore""s article xe2x80x9cThe Transient Response of Damped Linear Networks with Particular Regard to Wideband Amplifiersxe2x80x9d, Journal of Applied Physics, Volume 19, pp. 55-63, January 1948.
Although Tsay""s approach theoretically can be carried out all the way up to the clock signal input terminal, certain practical considerations obviate its implementation. Electrical considerations imply that the clock signal input terminal will be inputting a relatively large amount of current, and hence the wire coming out of the input terminal needs to be very thick to handle such heavy currents. Therefore, trying to do Tsay""s zero skew route all the way to the top often fails due to lack of routing resources. In particular, routing very thick wires at the top level becomes problematic due to interference with wires already routed.
For this reason, some space (a pre-route) is normally reserved which is used for routing at the top level to the signal input terminal. For symmetry, this pre-route is generally an H-trunk, whose middle wire and legs are much thicker than the wires that are used for lower level zero-skew routing, and the clock signal input terminal then connects to the center of the middle wire.
This is shown in FIG. 1. Referring to FIG. 1, H-trunk 100 includes a top segment 105, a middle segment 103 and a bottom segment 104. The input terminal 101 connects to the center 102 of the middle segment 103. Due to the symmetry of the H-trunk 100, the signal delay to points 107, 108, 109 and 110 is theoretically identical (zero skew). An H-trunk therefore can effectively generate 4 symmetrically arranged zero-skew points (such as points 107 to 110) from a single zero skew point (such as point 101 or 102). Accordingly, utilizing the H-trunk depicted in FIG. 1, Tsay""s algorithm can be applied to each quadrant of the chip surface, with the highest level connection in each quadrant being made to the appropriate one of points 107 to 110.
However, conventional clock signal routing techniques such as Tsay""s have certain disadvantages. First, constructing a zero-skew tree in this manner can require a significant amount of processing time. Moreover, because Tsay""s tree is constructed from the bottom up, subsequent movement of clock pins may require extensive changes to the tree structure, further complicating the design process. Finally, techniques such as Tsay""s often require adding large amounts of wire in order to ensure that balance points can be obtained at each level.
Other conventional approaches also have been proposed. In one such technique, a region is identified where delay falls within certain predetermined limits, and then pin placement is constrained to fall within that region. Such a technique is described in Ogawa, et al. xe2x80x9cEfficient Placement Algorithms Optimizing Delay For High-Speed ECL Masterslice LSI""sxe2x80x9d, Proceeding of the 23rd Design Automation Conference, pp. 404-410, 1986. Techniques such as Ogawa""s also have disadvantages. For instance, in order to use such techniques, the number of locations where pins may be placed is limited. However, in most conventional IC design, placement precedes routing. Thus, to the extent that the placement required by Ogawa""s routing technique is not satisfied, placement improvement must be performed. This can have the effect of further complicating the IC design process.
The present invention addresses the foregoing problems by identifying and routing to a number of connection points using a pattern of diamond-shaped rings.
Thus, according to one aspect, the invention is directed to laying out connection points and routing a signal from an input terminal to the connection points, for use in signal distribution to control skew. A pattern of diamond-shaped rings is constructed, each of the diamond-shaped rings including an inner diamond, an outer diamond and all space between the inner diamond and the outer diamond, where the diamond-shaped rings are arranged such that each point within a specified area is included within at least one diamond-shaped ring. A center point is identified for each of the diamond-shaped rings and each center point is designated as a connection point. A connection is then routed between the input terminal and each of plural of the connection points.
By identifying and routing connections to a number of connection points in the foregoing manner, the present invention frequently can facilitate controlled skew routing to arbitrarily arranged pins. Moreover, connections to such connection points often can be pre-routed, thereby further facilitating a particular routing design.
The present invention also addresses the problems described above by associating a diamond-shaped ring with each of several connection points and routing a connection between a pin and the connection point associated with one of the diamond-shaped rings that include the pin.
Thus, according to a further aspect, the invention is directed to routing a signal from one of plural connection points to a pin so as to control skew. A diamond-shaped ring is associated with each connection point, the diamond-shaped ring including an inner diamond, an outer diamond and all space between the inner diamond and the outer diamond, where the inner diamond and the outer diamond have a common center which is the connection point associated with the diamond-shaped ring. It is then determined which of the diamond-shaped rings include the pin. Finally, a connection is routed between the pin and the connection point associated with one of the diamond-shaped rings that includes the pin.
Routing a signal between such a connection point and a pin in the foregoing manner often can be accomplished in a relatively simple manner, while at the same time controlling skew.
According to a still further aspect, the invention is directed to routing a signal from an input terminal to a pin so as to control skew. A pattern of diamond-shaped rings is constructed, each of the diamond-shaped rings including an inner diamond, an outer diamond and all space between the inner diamond and the outer diamond, where the diamond-shaped rings are arranged such that each point within a specified area is included within at least one diamond-shaped ring. A center point is then identified for each of the diamond-shaped rings and each center point is designated as a connection point. A nearly zero-skew connection is routed between the input terminal and each of plural of the connection points, and it is determined which of the diamond-shaped rings include the pin. A connection is routed between the pin and the connection point associated with one of the diamond-shaped rings that includes the pin. It is a feature of this aspect of the invention that the pattern includes an arrangement of diamond-shaped rings such that the center points for the diamond-shaped rings are equally spaced in the horizontal direction and are equally spaced in the vertical direction.
The foregoing arrangement frequently can provide routing from an input terminal to a pin which both is relatively easy to implement and can be used to control skew. Such a routing technique is particularly applicable to clock signal routing on an integrated circuit chip.
The foregoing summary is intended merely to provide a brief description of the general nature of the invention. A more complete understanding of the invention can be obtained by referring to the claims and the following detailed description of the preferred embodiments in connection with the accompanying figures.