Iterative, noise-sensitive method of routing semiconductor nets using a delay noise threshold

[0002] The invention relates generally to the field of semiconductor design. and more specifically to a method and apparatus for routing semiconductor nets that considers functional and delay noise during the routing process.

[0003] As semiconductors operate at increasingly low cycle times and geometries become increasingly. small, functional and delay noise become more of a problem. Conventionally, noise or cross talk problems in the microprocessor design process are addressed by a cross talk analysis performed after a global or detailed routing of the nets in the chip. Following detailed routing, however, the chip layout is much less flexible. Consequently, it becomes very difficult to correct functional and delay noise problems identified after detailed routing. In turn, this may result in a longer time-to-market for the product.

[0004] It has therefore become desirable to develop a new method and system for routing nets which is noise-sensitive at earlier stages of the design process, as accomplished by the present invention.

[0005] The present invention is illustrated by way of example and not limitation in the accompanying figures, in which like references indicate similar elements, and in which:

[0006] FIG. 1 is a flowchart showing a preferred embodiment of the methodology of routing semiconductor nets of the present invention;

[0007] FIG. 2 is a flowchart showing in greater detail the process for classifying victim nets and safe nets, shown as step 115 in FIG. 1;

[0008] FIG. 3 is an exemplary diagram showing a potential victim net and neighboring aggressor nets;

[0009] FIG. 4 is a flowchart showing in greater detail the process for identifying least noise-aggressive neighboring nets for routing in tracks adjacent to the victim net;

[0010] FIG. 5 is an exemplary diagram showing a victim net and neighboring aggressor nets; and

[0011] FIG. 6 is an exemplary diagram showing routing constraints for least noise-aggressive neighboring nets relative to a victim net.

[0012] The following discussion is intended to provide a detailed description of at least one embodiment of the invention and should not be taken to be limiting of the invention itself. Rather, any number of variations may fall within the scope of the invention which is properly defined in the claims following this description.

[0013] The present invention relates to a novel method for routing semiconductor nets wherein functional noise and delay noise problems are addressed at earlier stages in the design process. All nets in the chip are Steiner routed, capacitance is extracted, and a static timing analysis performed. A list of noise related victim nets is generated which represents potentially problematic nets. The victim nets are detail routed, as are the least noise aggressive neighboring nets, which are selected so as to interact with the victim net in a manner which complies with pre-established noise thresholds. The process is then repeated until there are no new victim nets detected, at which point the remaining nets are detail routed.

[0014] Referring now to FIG. 1, initially all nets are “approximate routed.” Approximate routing shall be understood as a process whereby all nets are not detail-routed, but are assigned approximate routes which may not be unique. Approximate routing is much faster than detail routing and retains additional flexibility to the final design. One type of approximate routing is known in the art as “Steiner routing,” which shall be discussed in an exemplary fashion as the method of approximate routing herein.

[0015] As shown in FIG. 1, all nets are Steiner routed in step 105. As a result of Steiner routing, the nets are assigned approximate tracks which may overlap at various segments. After all nets are Steiner routed, grounded and coupling capacitances are extracted, and timing and noise analyses are performed in step 110. The static timing analysis performed in step 110 typically provides information as to the minimum cycle time for the chip, and generates a worse paths-based slack report.

[0016] In step 115, a list of victim nets most prone to functional and/or delay noise is generated. As described in more detail below in connection with FIG. 2, this list of victim nets may be generated through integer linear programming heuristics, or by other means known to those skilled in the art. As shown in step 120, if the set of victim nets is empty, then the remaining nets are detail routed in step 160, and the final timing and noise analysis is performed in step 170. If, however the set of victim sets is not empty, then each of the victim nets identified in step 115 is detailed routed in step 125.

[0017] The detailed routing of the victim nets acts as a blockage with respect to the Steiner routes of other non-victim nets. In other words, once detail-routed, the path of the net will not be used in future iterations of the Steiner routing. In this way, the chip is incrementally detail routed, which promotes routing convergence. In step 130, the remaining nets are Steiner routed with the nets which were detail routed in step 125 acting as blockages. In step 135, the chip is again subjected to capacitance extraction, timing analysis and noise analysis.

[0018] Still referring to FIG. 1, for each net detail routed in step 125, least noise aggressive of neighboring nets are selected in such a way as to maximize the amount of net segment coverage of tracks adjacent to the victim net in step 140. “Least” noise. aggressive neighboring nets may be those optimal for a set of conditions present in each embodiment, and not optimal in the absolute sense. Step 140 is discussed in greater detail in connection with FIG. 4, below. The purpose of selecting least noise aggressive neighboring nets (or those with noise below predetermined thresholds) is to identify those neighboring nets which may be placed adjacent to the victim net in such as way as to reduce functional and delay noise below specified thresholds. Constraints are generated for the detailed router, which results in routing the segments of the less aggressive neighboring nets are placed adjacent to the victim net in such a way as to fall within the aforementioned functional and delay noise thresholds.

[0019] Utilizing the constraints generated in connection with step 140, the selected neighboring aggressor nets are detail routed in step 145. These net segments then become fixed for purposes of the iterative process, and also act as blockages for later Steiner routing. All remaining nets are Steiner routed in step 150, and the process returns to step 110 to be repeated until a “yes” response is obtained in response to decision branch 120.

[0020] Step 115 is discussed in more detail in connection with FIG. 2. FIG. 2 shows the way in which victim nets that are safe nets may be identified. For each net being Steiner routed, a set of neighbor nets is selected in step 210. For purposes of ease of discussion, the set of neighbor nets in the following examples is assumed to be those nets with segments adjacent to segments of the potential- victim net under evaluation. The neighbor nets may include, however, nets which are not immediately adjacent to the net under evaluation, as shown in FIG. 3. While such nets will generally have a lesser effect on functional and delay noise on the potential victim net, they may also be considered for purposes of determining whether the net is a victim net, and may also be used as least-noise aggressive neighbor nets as discussed below. Once the'set of neighbor nets has been identified in step 210, a set of worse potential aggressor nets are identified in step 220. In step 230, the maximum total functional and delay noise from the worse aggressor nets is evaluated. If either the functional noise or delay noise is beyond predetermined thresholds, the net is classified as a victim net in response to decision branch 240. If both functional and delay noise are below the predetermined thresholds, then the net is classified as a safe net.

[0021] As a person skilled in the art would appreciate, the noise thresholds may be specific, user-specified values for functional and delay noise. Alternatively, a predetermined number or percentage of nets which exhibit the highest maximum functional noise or delay noise may be classified as victim nets. In another embodiment, the noise thresholds may be automatically generated by software.

[0022] In a preferred embodiment of step 220, an integer linear programming formulation is utilized wherein constraints and objective functions are generated. Overlap constraints are formulated to ensure that two aggressor nets cannot share the same track segment. For two aggressor nets i and j, which could potentially overlap if routed on the same track segment, X_i+X_j=1, where X_i=1 if net i is routed next to a potential victim net, and X_i=0 if net i is not routed next to a potential victim net. To determine the total functional and delay noise from the worse aggressor nets in step 230, an objective function is formulated as follows:

[0023] Let FN_ibe the functional noise component when net i is routed next to the potential victim net, and let DN_ibe the delay noise component when net i is routed next to the potential victim net. To maximize functional noise, the sum of FN_i*X_ifor all i's which are members of the group of aggressor nets is calculated. To maximize delay noise, the sum of DN_i*X_iis calculated for all i's in the group of neighboring aggressor net segments.

[0024] FIG. 3 shows a simplified diagram of potential victim net 310 with neighboring aggressor net segment A (320), aggressor net segment B (350), aggressor net segment C (340). and aggressor net segment D (330). Net segments A (320), B (350), and C (340) are all disposed within track K+1 (370), which is adjacent to track K (360), containing potential victim net 310. Net segment D (330) is located track K+2(380), which is located adjacent to track K+1(370) but not immediately adjacent to track K (360). A similar Set of net segments can be routed on the other side of the victim net on tracks K−1, K−2, . . . .

[0025] In reference to FIG. 3, let:

[0026] X_A=1 when net A is chosen to be placed in a track adjacent to the victim net

[0027] X_A=0 when net A is not chosen to be placed a track adjacent to the victim net

[0028] FN_A=Functional noise induced on victim net by net A when net segment A is routed next to victim net

[0029] DN_A=Delay noise induced on victim net by net A when net segment A is routed next to victim net

[0030] The following overlap constraints may be imposed:

[0031] X_D+X_B≦1

[0032] X_C+X_B≦1

[0033] X_A+X_D≦1

[0034] X_D+X_C≦1

[0035] By referring to FIG. 3, it is seen that X_D+X_B≦1 so long as both X_Dand X_Bare not simultaneously chosen to be placed in the track segment adjacent to the potential victim net segment. These constraints ensure that multiple net segments are not assigned the same segment of the potential victim net for determining the maximum delay and functional noise of the potential victim net.

[0036] To determine which nets are to be classified as victim nets, the objective is to determine the maximum noise to which the potential victim net may be subjected. In a preferred embodiment, total functional noise is equivalent to the sum of the noise induced by various neighbor net segments:

[0037] ΣFN_i·X_i,

[0038] i.e., maximum total functional noise=FN_A*X_A+FN_B*X_B*+FN_C* X_C+FN_D*X_D.

[0039] Similarly, total delay noise is determined by summing the total delay noised induced by all neighbor net segments:

[0040] ΣDN_i·X_i

[0041] i.e., maximum total delay noise=DN_A*X_A+DN_B*Y_B+DN_C*Y_C+DN_D*Y_D

[0042] For all potential victim nets for which either the maximum total functional noise or the maximum total delay noise exceed a predetermined threshold, such nets are classified as victim nets and detail routed in accordance with the methodology shown in FIG. 1.

[0043] In addition to those potential victim nets classified as victim nets in accordance with the integer linear programming formulation described above, certain nets which are known to be likely problem nets may also be classified as victim nets. For example, nets which comprise long buses are commonly subject to noise problems. A long bus net is one net of a set of long nets that are routed in parallel and connect different parts of a chip. In addition, nets driving latches, registers, other storage elements and dynamic logic, and other high-noise components are also subject to noise problems, and may also be classified as victim nets.

[0044] The flow chart in FIG. 4 shows in greater detail a preferred embodiment of selecting the least noise aggressive neighboring nets and generating constraints per detailed router for each detailed routed net, as shown in step 140 of FIG. 1. It should be understood that while step 140 refers to the “least” noise aggressive neighboring nets, in one embodiment it is not the least noise aggressive neighboring nets but those which have a noise below a predetermined threshold for functional noise and delay noise which are chosen. In other words, it may not be the least noise aggressive neighboring nets which are selected, but instead those which are below specified noise thresholds.

[0045] As shown in FIG. 4, for each detailed routed victim net identified in the current iteration. a set of least aggressive neighboring or close proximity net segments which maximally cover the detailed routing victim net while hearing the specified noise thresholds is selected in step 410. Nets are considered to be in close proximity where such nets are adjacent to, or within a few tracks of, the victim net.

[0046] One methodology for selecting this set is to use an integer linear programming formulation wherein it is ensured that two aggressor nets cannot share the same track such that the induced noise is less than the functional and delay noise threshold. and to maximize utilization of the neighboring track of the victim net. Routing constraints of the detailed router are generated for the selected aggressive neighboring net segments in step 420. The constraints are fed to the detailed router so that each such selected neighboring net segment is routed.

[0047] As stated above, the least noise aggressive neighboring nets may also be identified through integer linear programming methods. It should be understood that the neighboring tracks selected for routing may be those with noise below a specified threshold, and not truly the “least” noise aggressive neighboring nets, depending on the methodology selected for identifying such nets. To ensure that two neighboring nets are not assigned the same track, an overlap constraint may be imposed as follows:

[0048] X_i+X_j≦1, where i and j are two neighboring net segments

[0049] To ensure that induced functional noise is below a predetermined threshold, neighboring net segments in which the functional noise induced therein is below a predetermined threshold are selected as follows:

[0050] ΣFN_i·X_i≦a predetermined noise threshold (noise margin)

[0051] A similar calculation is performed with respect to delay noise:

[0052] ΣDN_i·X_i≦a predetermined noise threshold (noise margin)

[0053] An objective of this methodology is to maximize the utilization of the tracks adjacent to the victim net, so as to maximally exploit the available routing space on the semiconductor.

[0054] An example of the integer linear programming formulation is shown below in connection with FIG. 5. Victim net 550 has aggressive neighboring segments A, B, C, D, E, F and G; 530, 540, 520, 510, 560, 570 and 580, respectively. Adopting the methodology discussed above, least noise aggressive neighboring net segments are selected for tracks adjacent to victim net 550.

[0055] Applying integer linear programming, the following overlap constraints may be generated:

[0056] X_D+X_B≦1

[0057] X_C+X_B≦1

[0058] X_A+X_D≦1

[0059] X_D+X_C≦1

[0060] X_E+X_G≦1

[0061] X_F+X_G≦1

[0062] ΣFN_i·X_i<a predetermined functional noise threshold (noise margin), such that:

[0063] FN_A*X_A+FN_B*X_B*+FN_C*X_C+FN_D*X_D+FN_E*X_E+FN_F*X_F+FN_G*X_G≦a predetermined functional noise threshold

[0064] Similarly, total delay noise is summed and compared to a predetermined delay noise threshold:

[0065] ΣDN_i·X_i≦a predetermined delay noise threshold (slack), such that:

[0066] DN_A*X_A+DN_B*X_B*+DN_C*X_C+DN_D*X_D+DN_E*X_E+DN_F*X_F+DN_G*X_G≦a predetermined delay noise threshold

[0067] By way of example, constraints for the detailed router may be generated in accordance with FIG. 6. As shown in FIG. 6 victim net n1 (660) is routed on track K (610). Constraints for nets N2, N3 and N4 are generated as follows:

[0068] Net n2 (630) is routed on track K+1 (620) from coordinate x1 to x2;

[0069] Net n3 (640) is routed on track K+1 (620) from coordinate x3 to x4; and

[0070] Net n4 (650) is routed on track K+1 (620) from coordinate x5 to x6.

[0071] Upon generation, the constraints are provided to the detailed router, and the nets are detail routed. The method then returns to the Steiner routing phase until all victim nets have been detail-routed.

[0072] Skilled artisans would appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help improve the understanding of the embodiments of the present invention.

[0073] In the foregoing specification, the invention has been described with reference to specific embodiments. However, one of ordinary skill in the art appreciates that various modifications and changes can be made without departing from the scope of the present invention as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of present invention.

[0074] Benefits, other advantages, and solutions to problems have been described above with regard to specific embodiments. However, the benefits, advantages, solutions to problems, and any element(s) that may cause any benefit, advantage, or solution to occur or become more pronounced are not to be construed as a critical, required or essential feature or element of any or all the claims. As used herein, the terms “comprises,” “comprising,” or any other variation thereof, are intended to cover a non-exclusive inclusion. such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus.