Method of automated repair of crosstalk violations and timing violations in an integrated circuit design

[0001] 1. Field of the Invention

[0002] The present invention relates generally to the design of integrated circuits. More specifically, but without limitation thereto, the present invention relates to methods of avoiding crosstalk during placement and routing of an integrated circuit design.

[0003] 2. Description of the Prior Art

[0004] With the dramatic increase in very large scale integrated circuit (VLSI) chip gate counts and circuit density, circuit noise resulting from crosstalk interference is becoming increasingly significant. Noise analysis is an important step in the design flow of integrated circuits, because crosstalk interference may result in false switching and failure of the design to meet performance specifications. Computer software tools have been developed for analyzing crosstalk noise, however, these tools may not be suitable for a variety of applications. Such tools generally require preparation of several special input files that require other software tools, which increases the turnaround time (TAT). The accuracy of the noise calculations is also limited by the accuracy of the software tools used to prepare the special input files.

[0005] In one embodiment of the present invention, a method includes steps of:

• • [0006] (a) receiving as input an integrated circuit design;
  • [0007] (b) performing an initial cell placement and global routing from the integrated circuit design;
  • [0008] (c) identifying nets having crosstalk violations according to a first set of rules from the initial cell placement and global routing;
  • [0009] (d) performing a detailed routing that includes providing crosstalk protection for the nets identified in step (c);
  • [0010] (e) identifying nets having crosstalk violations according to a second set of rules from the detailed routing; and
  • [0011] (f) performing an additional detailed routing that includes providing crosstalk protection for the nets identified in step (e).

[0012] In another aspect of the present invention, a computer program product for automatically repairing crosstalk violations in an integrated circuit design includes a medium for embodying a computer program for input to a computer and a computer program embodied in the medium for causing the computer to perform steps of:

• • [0013] (a) receiving as input an integrated circuit design;
  • [0014] (b) performing an initial cell placement and global routing from the integrated circuit design;
  • [0015] (c) identifying nets having crosstalk violations according to a first set of rules from the initial cell placement and global routing;
  • [0016] (d) performing a detailed routing that includes providing crosstalk protection for the nets identified in step (c);
  • [0017] (e) identifying nets having crosstalk violations according to a second set of rules from the detailed routing; and
  • [0018] (f) performing an additional detailed routing that includes providing crosstalk protection for the nets identified in step (e).

[0025] One of the most significant factors that may affect signal or clock arrival time, or propagation delay, in a selected signal net or clock tree net of an integrated circuit design is the crosstalk noise generated from signals carried in wires adjacent to the selected net, or victim net. The crosstalk noise may inject an incremental crosstalk delay (positive or negative) in the victim net. In previous design flows, the net implementation is designed and a crosstalk analysis is performed afterward to determine whether the crosstalk results in any timing violations in the net. If timing violations are found, the net design is modified, and another crosstalk analysis is performed. This cycle is iterated until all timing violations are removed, which may be an extremely time-consuming process.

[0026] Crosstalk noise is generally capacitively coupled between traces in an integrated circuit and is most significant when the sources of the crosstalk, commonly referred to as aggressor nets, or “aggressors”, have a fast switching waveform. The switching waveforms of one or more aggressor nets are coupled by parasitic coupling capacitances to a net that is commonly referred to as a victim net or “victim”. Crosstalk noise may cause a change in propagation delay in the victim net and consequent failure of the integrated circuit design to meet timing specifications. For example, depending on the waveform of the signal in the aggressor nets, the crosstalk noise may inject a positive or negative delay in the victim net.

[0027] Previous methods for avoiding crosstalk in integrated circuit designs may report nets that have a net length greater than the critical length of the driver cells during placement. However, these methods may not make corrections during placement to avoid crosstalk due to critical net length. A path is timing critical to the setup time requirement if the propagation delay of the path is more than an empirical threshold, typically about 90 percent, of the clock period. A path is usually timing critical to setup time if the path includes a large number of cells, typically 40 to 70, and if the average wire length between cells is more than a small value, for example, 200 microns. A path may also be timing critical to setup time if the path includes an average number of cells, typically 25 to 30, and if the average wire length between cells is more than a large value, for example, 500 microns. A path is timing critical to hold time if the propagation delay of the path is less than an empirical threshold, typically about 10 percent, of the clock period. A path is usually timing critical to hold time if the path includes a small number of cells, typically 0 to 5, and the average wire length between cells is less than a small value, for example, 200 microns.

[0028] A timing critical net is a net that belongs to a timing critical path. All other nets are timing non-critical nets. Timing critical nets may result in severe crosstalk delays. Also, delay estimates for timing critical nets that are based on coupling capacitance multipliers may be extremely inaccurate, if the nets have lengths that are much greater than the critical length.

[0029] Previous methods for avoiding crosstalk include reporting noise violations and timing violations after cell placement and detailed routing, however, these methods generally require that the noise and timing violations be corrected manually. As a consequence of these corrections, net drivers may be downsized, and net lengths may be increased by design engineers during manual engineering change orders (ECO), resulting in crosstalk noise problems that may not be reported. Another disadvantage of previous methods for closing timing in an integrated circuit design is that manually correcting crosstalk noise problems is a time consuming and error prone process.

[0030] The present invention overcomes the disadvantages of the previous methods described above by providing a method of closing timing that ensures that all timing and noise violations are reported and automatically corrected.

[0031] In one embodiment of the present invention, a method includes steps of:

• • [0032] (a) receiving as input an integrated circuit design;
  • [0033] (b) performing an initial cell placement and global routing from the integrated circuit design;
  • [0034] (c) identifying nets having crosstalk violations according to a first set of rules from the initial cell placement and global routing;
  • [0035] (d) performing a detailed routing that includes providing crosstalk protection for the nets identified in step (c);
  • [0036] (e) identifying nets having crosstalk violations according to a second set of rules from the detailed routing; and
  • [0037] (f) performing an additional detailed routing that includes providing crosstalk protection for the nets identified in step (e).

[0038] FIG. 1 illustrates a flow chart 100 of a method of automatically repairing crosstalk violations in an integrated circuit design according to an embodiment of the present invention.

[0039] Step 102 is the entry point of the flow chart 100.

[0040] In step 104, an integrated circuit design is received as input, for example, from a netlist according to well known techniques.

[0041] In step 106, an initial cell placement and global routing of the integrated circuit design are performed according to well known techniques.

[0042] In step 108, nets having crosstalk violations according to a first set of rules are identified from the initial cell placement and global routing of the integrated circuit design before performing detailed routing.

[0043] The first set of rules for identifying nets having crosstalk violations uses information about the integrated circuit design that is available from the initial cell placement and global routing. An exemplary first set of rules is described as follows. Nets that are at risk for crosstalk violations are assigned to two categories: time critical and time non-critical.

[0044] Time critical nets with length ratio violation are nets having a ratio of net length to critical net length that is greater than a selected critical length ratio. The selected critical length ratio may be determined by experiment and is preferably given a conservative value to avoid a high level of crosstalk interference, for example 2.5. The selected critical length ratio may be stored in a technology library and updated as necessary to increase or decrease the amount of crosstalk protection.

[0045] Time non-critical nets with length ratio violation are nets having a ratio of net length to critical net length that is greater than a selected non-critical length ratio. The selected non-critical length ratio may be determined by experiment and is preferably given a conservative value to avoid a high level of crosstalk interference, for example 3.0. The selected non-critical length ratio may be stored in a technology library and updated as necessary to increase or decrease the amount of crosstalk protection.

[0046] Time critical nets with length ratio violation have a higher sensitivity to crosstalk interference than time non-critical nets with length ratio violation, therefore time critical nets with length ratio violation are preferably given a higher priority for crosstalk protection. A first list is created of the net names of the time critical nets with length ratio violation in the first category, for example, in a computer readable file format. A second list is likewise created of the net names of the time non-critical nets with length ratio violation in the second category. If the initial cell placement and routing includes some crosstalk avoidance provision, then the two lists should have few entries.

[0047] In step 110, nets that have timing violations, that is, nets that belong to paths having negative timing slack, are identified according to well known techniques, for example, by performing a circuit analysis using a circuit simulation program at gate level.

[0048] In step 112, a detailed routing is performed that includes special rule routing of the nets identified in step 110. The special rule routing for nets having timing violations includes, for example, additional spacing and/or shielding as for nets having crosstalk violations, and also increasing trace width to reduce wire resistance and the corresponding net delay.

[0049] In step 114, a detailed routing is performed that includes special routing of the nets identified as having crosstalk violations in step 108. In contrast to the initial global routing, which may include some provisions for crosstalk avoidance, the special routing actually corrects crosstalk violations identified in step 108. The detailed routing includes providing crosstalk protection such as additional spacing or other suitable crosstalk protection for all of the nets identified in step 108. Providing crosstalk protection for nets identified as having crosstalk violations during detailed routing advantageously reduces the number of nets that may still be at risk for crosstalk violations after detailed routing and is an important feature of the method of the present invention.

[0050] In step 116, nets having crosstalk violations are identified according to a second set of rules. An exemplary second set of rules for identifying nets having crosstalk violations is described as follows. Nets that are at risk for crosstalk violations are assigned to four additional categories: noise critical nets having noise violations, noise non-critical nets having noise violations, time critical nets with multiple factor violations, and time non-critical nets with multiple factor violations.

[0051] A noise critical net is identified as having a noise violation if the ratio of noise glitch peak magnitude to supply voltage exceeds a selected critical noise glitch peak magnitude ratio, for example, 48 percent. Noise critical nets are nets that drive inputs to flip-flops or latches, for example.

[0052] Nets that are not noise critical nets are noise non-critical nets. A noise non-critical net is identified as having a noise violation if the ratio of noise glitch peak magnitude to supply voltage exceeds a selected non-critical noise glitch peak magnitude ratio, for example, 52 percent.

[0053] Time critical nets with multiple factor violations are time critical nets that exceed multiple net rules, for example, nets that have a ratio of net length to critical length that exceeds a selected critical length ratio and a ratio of coupling capacitance to total net capacitance that exceeds a selected critical coupling capacitance ratio and a ratio of glitch peak magnitude to supply voltage that exceeds a selected glitch peak magnitude ratio.

[0054] Time non-critical nets with multiple factor violations are time non-critical nets that have a ratio of net length to critical length that exceeds the non-critical length ratio, a ratio of coupling capacitance to total net capacitance that exceeds a selected non-critical coupling capacitance ratio, and a ratio of glitch peak magnitude to supply voltage that exceeds a selected glitch peak magnitude ratio. A glitch is a noise spike that is induced in a victim net by an aggressor net. The glitch peak magnitude is usually available after detailed routing, however, if the glitch peak magnitude is not available, then the ratio of glitch peak magnitude to supply voltage may be approximated, for example, by the formula:
M≈(S_max+Sa−S)/(2*S_max)  (1)
where S is the net driver strength for the victim net, Sa is the average aggressor net driver strength, and S_max is the maximum driver strength among all cells in the cell library for the desired technology.

[0055] A list of net names is created for each category of nets that are identified as noise critical nets having noise violations, noise non-critical nets having noise violations, time critical nets with multiple factor violations, and time non-critical nets with multiple factor violations, for example, in a computer readable file format.

[0056] In step 118, manual changes to the cell placement and routing may be requested by the circuit designer. If manual changes to the cell placement and routing are requested, then engineering change orders (ECO) are implemented in the layout. The manual changes may introduce additional timing violations that have to be corrected.

[0057] In step 120, if any nets were identified in step 116, then the next step continues from step 118. Otherwise, the next step continues from step 120.

[0058] In step 122, an additional detailed routing is performed that provides crosstalk protection such as additional spacing or other suitable crosstalk protection for the nets identified in step 116. The next step continues from step 116 to ensure that no nets remain having crosstalk violations.

[0059] Step 124 is the exit point of the flow chart 100.

[0060] FIG. 2 illustrates a flow chart 200 of a method of identifying nets that having crosstalk violations according to a first set of rules in FIG. 1.

[0061] Step 202 is the entry point of the flow chart 200.

[0062] In step 204, an analysis is performed according to well known techniques, for example, using a circuit simulation program at gate level, to calculate net and path delays to identify nets in the integrated circuit design that are time critical.

[0063] In step 206, a net in the integrated circuit design is selected.

[0064] In step 208, if the selected net is time critical, then the next step continues from step 210. Otherwise, the next step continues from step 214.

[0065] In step 210, the ratio of net length to critical length of the selected net is compared to a selected time critical length ratio, for example, 2.5. If the net length ratio exceeds the time critical length ratio, then the next step continues from step 212; otherwise the next step continues from step 218.

[0066] In step 212, the name of the selected net is included in a list of time critical nets having a length ratio violation, and the next step continues from step 216. The list may be implemented, for example, as a computer file.

[0067] In step 214, the ratio of net length to critical length of the selected net is compared to a selected time non-critical length ratio, for example, 3.0. If the net length ratio exceeds the time non-critical length ratio, then the next step continues from step 216; otherwise the next step continues from step 218.

[0068] In step 216, the name of the selected net is included in a list of time non-critical nets having a length ratio violation. The list may be implemented, for example, as a computer file.

[0069] In step 218, if all nets in the integrated circuit design have been selected, then the next step continues from step 220. Otherwise, the next step continues from step 206.

[0070] Step 220 is the exit point of the flow chart 200.

[0071] An example of a second set of rules that may be used to identify nets having crosstalk violations without calculating incremental crosstalk delays is described as follows.

[0072] FIGS. 3A, 3B, and 3C illustrate a flow chart 300 of a method of identifying nets having crosstalk violations according to a second set of rules in FIG. 1 without using incremental crosstalk delay information.

[0073] Step 302 is the entry point of the flow chart 300.

[0074] In step 304, an analysis is performed according to well known techniques, for example, using a circuit simulation program at gate level, to calculate net and path delays and incremental crosstalk delays to identify time critical nets in the integrated circuit design.

[0075] In step 306, noise glitch peak magnitudes are calculated according to well known techniques from the circuit analysis to identify nets having noise violations.

[0076] In step 308, a net in the integrated circuit design is selected.

[0077] In step 310, if the selected net has a noise violation, then the next step continues from step 312. Otherwise, the next step continues from step 318.

[0078] In step 312, if the selected net is noise critical, for example, if the selected net precedes a flip-flop, latch, or memory, then the next step continues from step 314. Otherwise, the next step continues from step 316.

[0079] In step 314, the name of the selected net is included in a list of noise critical nets having a noise violation, and the next step continues from step 318. The list may be implemented, for example, as a computer file as described above for the lists of net names for nets having crosstalk violations.

[0080] In step 316, the name of the selected net is included in a list of noise non-critical nets having a noise violations.

[0081] In step 318, if all nets have been selected, then the next step continues from step 338. Otherwise, the next step continues from step 306.

[0082] In step 320, if the selected net is time critical, then the next step continues from step 322. Otherwise, the next step continues from step 330.

[0083] In step 322, the ratio of net length to critical length of the selected net is compared to a selected time critical length ratio, for example, 2.5. If the net length ratio exceeds the timing critical length ratio, then the next step continues from step 324; otherwise the next step continues from step 318.

[0084] In step 324, the ratio of coupling capacitance to total net capacitance of the selected net is compared to a selected critical coupling capacitance ratio, for example, 0.3. If the ratio of coupling capacitance to total net capacitance of the selected net exceeds the critical coupling capacitance ratio, then the next step continues from step 326. Otherwise, the next step continues from step 318.

[0085] In step 326, the ratio of noise glitch peak magnitude to supply voltage of the selected net is compared to a selected critical noise glitch peak magnitude ratio, for example, 0.3. If the ratio of glitch peak magnitude to supply voltage of the selected net exceeds the critical glitch peak magnitude ratio, then the next step continues from step 328. Otherwise, the next step continues from step 336.

[0086] In step 328, the name of the selected net is included in a list of time critical nets with multiple factor violations, and the next step continues from step 318.

[0087] In step 330, the ratio of net length to critical length of the selected net is compared to a selected time non-critical length ratio, for example, 3.0. If the net length ratio exceeds the timing non-critical length ratio, then the next step continues from step 332; otherwise the next step continues from step 318.

[0088] In step 332, the ratio of coupling capacitance to total net capacitance of the selected net is compared to a selected non-critical coupling capacitance ratio, for example, 0.35. If the ratio of coupling capacitance to total net capacitance of the selected net exceeds the critical coupling capacitance ratio, then the next step continues from step 334. Otherwise, the next step continues from step 318.

[0089] In step 334, the ratio of noise glitch peak magnitude to supply voltage of the selected net is compared to a selected non-critical noise glitch peak magnitude ratio, for example, 0.35. If the ratio of glitch peak magnitude to supply voltage of the selected net exceeds the selected non-critical noise glitch peak magnitude ratio, then the next step continues from step 336. Otherwise, the next step continues from step 318.

[0090] In step 336, the name of the selected net is included in a list of time non-critical nets with multiple factor violations, and the next step continues from step 318.

[0091] Step 338 is the exit point of the flow chart 300.

[0092] An example of a second set of rules that may be used to identify nets having crosstalk violations that uses incremental crosstalk delay information is described as follows.

[0093] FIGS. 4A and 4B illustrate a flow chart 400 of a method of identifying nets having crosstalk violations according to a second set of rules in FIG. 1 using incremental crosstalk delay information.

[0094] Step 402 is the entry point of the flow chart 300.

[0095] In step 404, an analysis is performed according to well known techniques, for example, using a circuit simulation program at gate level, to calculate net and path delays and incremental crosstalk delays to identify time critical nets in the integrated circuit design.

[0096] In step 406, noise glitch peak magnitudes are calculated according to well known techniques from the circuit analysis to identify nets having noise violations.

[0097] In step 408, a net in the integrated circuit design is selected.

[0098] In step 410, if the selected net has a noise violation, then the next step continues from step 412. Otherwise, the next step continues from step 420.

[0099] In step 412, if the selected net is noise critical, for example, if the selected net precedes a flip-flop, latch, or memory, then the next step continues from step 414. Otherwise, the next step continues from step 416.

[0100] In step 414, the name of the selected net is included in a list of noise critical nets having a noise violation, and the next step continues from step 418. The list may be implemented, for example, as a computer file having the same format as described above for the lists of net names for nets having crosstalk violations.

[0101] In step 416, the name of the selected net is included in a list of noise non-critical nets having a noise violation.

[0102] In step 418, if all nets in the integrated circuit design have been selected, then the next step continues from step 430. Otherwise, the next step continues from step 408.

[0103] In step 420, if the selected net is time critical, then the next step continues from step 422. Otherwise, the next step continues from step 426.

[0104] In step 422, if the crosstalk delay of the selected net exceeds a selected critical crosstalk delay, for example, 30 picoseconds, then the next step continues from step 424; otherwise the next step continues from step 418.

[0105] In step 424, the name of the selected net is included in a list of noise critical and time critical nets with timing violations, and the next step continues from step 418.

[0106] In step 426, if the crosstalk delay of the selected net exceeds a selected non-critical crosstalk delay, for example, 200 picoseconds, then the next step continues from step 428; otherwise the next step continues from step 418.

[0107] In step 428, the name of the selected net is included in a list of noise non-critical and time non-critical nets with timing violations, and the next step continues from step 418.

[0108] Step 430 is the exit point of the flow chart 400.

[0109] The methods illustrated in the flowchart descriptions above may be embodied in a computer program product and implemented by a computer according to well known programming techniques.

[0110] In another aspect of the present invention, a computer program product for automatically repairing crosstalk violations in an integrated circuit design includes a medium for embodying a computer program for input to a computer and a computer program embodied in the medium for causing the computer to perform steps of:

• • [0111] (a) receiving as input an integrated circuit design;
  • [0112] (b) performing an initial cell placement and global routing from the integrated circuit design;
  • [0113] (c) identifying nets having crosstalk violations according to a first set of rules from the initial cell placement and global routing;
  • [0114] (d) performing a detailed routing that includes providing crosstalk protection for the nets identified in step (c);
  • [0115] (e) identifying nets having crosstalk violations according to a second set of rules from the detailed routing; and
  • [0116] (f) performing an additional detailed routing that includes providing crosstalk protection for the nets identified in step (e).

[0117] FIGS. 5A and 5B illustrate a flow chart 500 of a method and computer program for automatically repairing crosstalk violations in an integrated circuit design according to an embodiment of the present invention.

[0118] Step 502 is the entry point of the flow chart 500.

[0119] In step 504, an integrated circuit design is received as input;

• • [0120] In step 506, an initial cell placement and global routing is performed from the integrated circuit design according to well-known techniques.

[0121] In step 508, nets in the integrated circuit design that have crosstalk violations are identified according to a first set of rules as described above.

[0122] In step 510, a list of the nets that have crosstalk violations according to the first set of rules is generated as output.

[0123] In step 512, nets in the integrated circuit design that have timing violations, that is negative slack, are identified as described above.

[0124] In step 514, an additional list of the nets in the integrated circuit design that have timing violations is generated as output.

[0125] In step 516, a special rule routing of the integrated circuit design is performed to correct the timing violations identified in step 512.

[0126] In step 518, a detailed routing of the integrated circuit design is performed that provides additional crosstalk protection to the nets listed in step 510. The additional crosstalk protection may include, for example, spacing the nets named in the list further apart from aggressor nets.

[0127] In step 520, nets that have crosstalk violations are identified according to a second set of rules as described above.

[0128] In step 522, an additional list of the nets in the integrated circuit design that have crosstalk violations according to the second set of rules is generated as output.

[0129] In step 524, engineering change orders (ECOs) may be implemented as requested by the circuit designer, including manual changes entered by the circuit designer.

[0130] In step 526, if the additional list of nets identified in step 522 is empty, then the next step continues from step 530. Otherwise, the next step continues from step 528.

[0131] In step 528, an additional detailed routing is performed for the integrated circuit design that provides additional crosstalk protection for the nets listed in step 522. The next step continues from step 520 until all crosstalk violations have been corrected.

[0132] Step 528 is the exit point of the flow chart 500.

[0133] Although the method of the present invention illustrated by the flowchart descriptions above are described and shown with reference to specific steps performed in a specific order, these steps may be combined, sub-divided, or reordered without departing from the scope of the claims. Unless specifically indicated herein, the order and grouping of steps is not a limitation of the present invention.

[0134] While the invention herein disclosed has been described by means of specific embodiments and applications thereof, numerous modifications and variations could be made thereto by those skilled in the art without departing from the scope of the invention set forth in the following claims.