Hierarchical parasitic capacitance extraction for ultra large scale integrated circuits

[0002] 1. Field of the Invention

[0003] The invention relates to methods for modeling electric effects of interconnect parasitics in integrated circuits.

[0004] 2. Background Art

[0005] The design of an integrated circuit occurs in several stages. As illustrated in FIG. 1, the design of the integrated circuit starts with drafting a specification of the intended functions of the integrated circuit (shown at 2). A logic design is then produced and optimized based on the functions described in the specification (shown at 4). For ultra large scale integration (ULSI), i.e., an integrated circuit consisting of millions of transistors, the logic design is described in many levels of abstraction to ensure an orderly and structured design process. Typically, the logic design is expressed as a set of interconnected blocks in a hierarchical structure, each block in the design hierarchy representing pieces of hardware ranging from simple logic gates to complete systems, e.g., microprocessors. A floor plan of the integrated circuit is created from the logic design (shown 6). The floor plan is transferred to a layout design system for placement and routing (shown at 8). “Placement” is the process by which logic elements in the logic design are realized in the circuit elements of a physical implementation, and “routing” is the process by which metal interconnections are created between the circuit elements. After placement and routing, estimates of the parasitic impedances of the metal interconnections are made (“extracted”) to form an interconnect delay model (shown at 10). The signal path delays are then calculated using the interconnect delay model, and detailed timing analysis is performed to verify that the delay characteristics of the circuit satisfy specified design criteria (shown at 12). The design process is completed (shown at 14) if the delay characteristics of the circuit satisfy specified design criteria. If the delay characteristics of the circuit do not satisfy specified design criteria, the logic design is refined and the circuit is retested until the delay characteristics of the circuit satisfy the specified design criteria.

[0006] In deep submicron process technologies (0.35 μm and below), interconnect delays dominate system performance. Therefore, accurate modeling of the parasitic effects, e.g., parasitic capacitances, associated with the interconnects is very important. The most accurate algorithm for extracting capacitance involves solving Laplace's equation with boundary conditions numerically. See, for example, E. Dengi and R. Rohrer, “Boundary Element Method Macromodels for 2-D Hierarchical Capacitance Extraction,” Proc. of the 35^thDAC, pp. 218-333, June 1998, W. Shi et al., “A Fast Hierarchical Algorithm for 3-D Capacitance Extraction,” Proc. of the 35^thDAC, pp. 212-217, June 1998. This approach is, however, very slow and therefore not appropriate for computing the overall capacitance matrix of ULSI layout. Full-chip interconnect models are usually obtained using a layout parameter extraction tool which employs three-dimensional field solutions to create analytical model or lookup table models. These models in conjunction with layout pattern recognition algorithms are applied during run time to determine capacitance values. To ensure the quality of subsequent timing and signal integrity analyses, the extracted parasitic values have to be verified against some known “golden data” which are either results of three-dimensional field solutions or measured parasitic values. See, for example, P. Franzon et al., “Parasitic Extraction Accuracy; How much is enough?” Proc. of the 36^thDAC, pp. 429, June 1999. Once an extraction tool is validated, a flat, post-layout extraction is expected to produce reasonably accurate interconnect models.

[0007] Interconnect parasitics are not intentionally designed into a chip but rather are consequences of the layout and are usually degrading to the circuit performance. Thus modeling interconnect parasitics early in the design process, i.e., prior to completion of the physical design, is crucial to capturing major timing and noise problems. Initially, values of interconnect parasitics are computed based on a set of wire load models and Manhattan distances of the nets. Later in the design process, most blocks on the chip have either a partial layout view or an abstract view describing areas to be occupied by a certain level of metal. To achieve timing closure, a realistic estimation of the total capacitance for the nets must be determined. The total net capacitance is given by the following expression: $\begin{array}{cc}{C}_T=C_G+\sum _i{M}^i{C}_C^i& \left(1\right)\end{array}$

[0008] where Mⁱare Miller scaling factors, usually ranging from 0 to 2, C_Gis the capacitance to static nets (ground), and C_cⁱare capacitances to switching nets (signal). In order to compute C_T, it is necessary to distinguish between switching nets and static nets. Unfortunately, the switching information of every net is not known prior to completion of the physical design. Without switching information, performance analysis (timing, noise, etc.) has to be done under “worst case” assumptions. However, in hierarchical extraction, most extraction tools consider all unspecified nets static by default. As a result, the worst case conditions may not necessarily be captured, leading to significant errors in analysis results.

[0009] In one aspect, the invention relates to a method for extracting parasitic capacitance from an integrated circuit layout which comprises decomposing nets in the integrated circuit layout into conductive segments along two mutually perpendicular directions. The method further includes summing capacitances between the conductive segments in a selected net and the remaining conductive segments in the integrated circuit layout that are aligned with the conductive segments in the selected net and multiplying the sum by a scaling factor to obtain a first capacitance value. The method further includes summing capacitances between the conductive segments in the selected net and the remaining conductive segments in the integrated circuit layout that are transverse, to the conductive segments in the selected net to obtain a second capacitance value. The method further includes summing the first capacitance value and second capacitance value to obtain a total capacitance value for the selected net.

[0010] In another aspect, the invention relates to a method for extracting parasitic capacitance from an integrated circuit layout which comprises decomposing nets in the integrated circuit layout into conductive segments along two mutually perpendicular directions. The method further includes summing capacitances between the conductive segments in a selected net and the remaining conductive segments in the integrated circuit layout that are aligned with the conductive segments in the selected net and multiplying the sum by a first scaling factor to obtain a first capacitance value. The method further includes summing capacitances between the conductive segments in the selected net and the remaining conductive segments in the integrated circuit layout that are transverse to the conductive segments in the selected net and multiplying the sum by a second scaling factor to obtain a second capacitance value. The method further includes summing the first capacitance value and second capacitance value to obtain a total capacitance value for the selected net.

[0011] Other aspects and advantages of the invention will be apparent from the description which follows and the appended claims.

[0012] FIG. 1 is a flowchart illustrating a process for designing an integrated circuit.

[0013] FIG. 2 shows a block diagram of an extraction tool.

[0014] FIG. 3 schematically depicts a hierarchical design of an integrated circuit.

[0015] FIG. 4 shows the nets in FIG. 3 divided into conductive segments.

[0016] Various embodiments of the invention will now be described with reference to the accompanying figures. FIG. 2 shows an extraction tool 22 which comprises a geometry processing tool 24. Typically, the geometry processing tool is a computer-aided design (CAD) engine which receives a geometric file and produces certain parameters based on the information contained in the geometric file. In the invention, the geometry processing tool 24 receives an integrated circuit layout 26 as input. Typically, the layout 26 is in a standard industry format, e.g., GDSII or LEF/DEF. The geometry processing tool 24 analyzes the nets in the layout 26 and generates parameters based on specific regions of the layout 26. Examples of geometry processing tools suitable for use in the invention can be found in Fire & Ice QX extraction tool from Simplex Solutions, Inc., and Star-RC extraction tool from Avant! Corporation. The extraction tool 22 further includes a capacitance solver 28 which extracts capacitances from the layout 26 using the parameters generated by the geometry processing tool 24 and technology data 27. The capacitance solver 28 may be implemented as a set of instructions which are executable by a processor (not shown). The capacitances extracted by the capacitance solver 28 are used in building an interconnect delay model 30 of the circuit.

[0017] FIG. 3 schematically depicts a hierarchical design of an integrated circuit 32 that may be processed by the extraction tool 22 shown in FIG. 2. It should be noted that the design shown in FIG. 3 is very simple and is intended for illustrative purposes only. The integrated circuit design 32 includes nets A-H, each located on different levels of the design hierarchy. There are three levels in this example, including levels 0, 1, and 2, where level 0 is the top level and level 2 is the bottom level. In reality, there will be many more levels. Nets A, C, F, and G are located at level 0, nets D and H are located at level 1, and nets B and E are located at level 2. The nets A-H are represented by conductor polygons. The conductor polygons can be further decomposed into conductive segments, each conductive segment oriented along one of two mutually perpendicular directions, e.g., the x or y direction. As shown in FIG. 4, net A includes conductive segments A_N⁰and A_N−1⁰, where the subscripts N and N-1 represent the conductive layers of the segments and the superscript 0 represents the level number of the conductive segments in the design hierarchy. Similarly, net B includes conductive segment B_N−1², net C includes conductive segment C_N−1⁰, net D includes conductive segment D_N−2¹, net E includes conductive segment E_N², net F includes conductive segment F_N⁰, net G includes conductive segment G_N−1⁰, and net H includes conductive segment H_N−1¹. In the design hierarchy, conductive segments F_N⁰, E_N², G_N−1⁰, and H_N−1¹interact with conductive segment A_N⁰, and conductive segments B_N−1², C_N−1⁰, and D_N−2¹interact with conductive segment A_N−1⁰.

[0018] The capacitance solver 28 (shown in FIG. 2) uses a hierarchical parasitic capacitance extraction method to extract capacitances from an integrated circuit layout. The hierarchical parasitic capacitance extraction method of the invention will be described first for an arbitrary net N and then applied to a specific net in the integrated circuit design 32 (shown in FIGS. 3 and 4). Suppose that an arbitrary net N can be divided into n conductive segments, each of the n wire segments lying along either one of two mutually perpendicular directions. The total capacitance of the net N is equal to the sum of the conductive segment capacitances, C_Tⁿ, $\begin{array}{cc}\begin{array}{c}{C}_T^n=\sum _j{C}_G^j\underset{i}{+\sum }{M}^i{C}_C^i\\ =\sum _{\mathrm{jS}}{C}_G^{\mathrm{jS}}+\sum _{\mathrm{jL}}{C}_G^{\mathrm{jL}}+\sum _{\mathrm{iS}}{M}^{\mathrm{iS}}{C}_C^{\mathrm{iS}}+\sum _{\mathrm{iL}}{M}^{\mathrm{iL}}{C}_C^{\mathrm{iL}}\end{array}& \left(2\right)\end{array}$

[0019] where Mⁱ, M^iS, and M^iLare Miller scaling factors, C_G^jSand C_C^iSare capacitances to static nets and switching nets, respectively, in the same hierarchical level as wire segment n, and C_G^jLand C_C^jLare capacitances to static and switching nets, respectively, at other hierarchical levels. While it is straightforward to extract C_G^jSand C_C^iSextracting C_G^iLand C_C^iLmay be challenging because switching characteristics of every net at hierarchical levels other than the hierarchical level of net N are often unknown prior to completion of the physical design. Not being able to separate C_G^jLfrom C_C^jL, i.e., not being able to distinguish between static and switching nets at other hierarchical levels, introduces significant uncertainty in the extracted net capacitance values.

[0020] Returning to equation (2), if a global Miller scaling factor M is applied to all the capacitances to switching nets (also known as coupling capacitances), C_c, equation (2) can be expanded into $\begin{array}{cc}{C}_T^n=\sum _{\mathrm{jSP}}{C}_G^{\mathrm{jSP}}+\sum _{\mathrm{jST}}{C}_G^{\mathrm{jST}}+\sum _{\mathrm{jLP}}{C}_G^{\mathrm{jLP}}+\sum _{\mathrm{jLT}}{C}_G^{\mathrm{jLT}}+M\left(\sum _{\mathrm{iSP}}{C}_C^{\mathrm{iSP}}+\sum _{\mathrm{iST}}{C}_C^{\mathrm{iST}}+\sum _{\mathrm{iLP}}{C}_C^{\mathrm{iLP}}+\sum _{\mathrm{iLT}}{C}_C^{\mathrm{iLT}}\right)& \left(3\right)\end{array}$

[0021] where C_G^jSPand C_C^iSPare capacitances between the conductive segment n and static and switching conductor polygons, respectively, parallel to and on the same hierarchical level as the conductive segment n, C_G^jLPand C_C^iLPare capacitances between the conductive segment n and static and switching conductor polygons, respectively, parallel to and on a different hierarchical level than the conductive segment n, C_G^jSTand C_C^iSTare capacitances between the conductive segment n and static and switching conductor polygons, respectively, transverse to and on the same hierarchical level as the conductive segment n, C_G^jLTand C_C^iLTare capacitances between the conductive segment n and static and switching conductor polygons, respectively, transverse to and on a different hierarchical level than the conductive segment n. If switching characteristics of every net are not known, by default most traditional extraction tools assume that all unspecified nets are static. The estimated total capacitance value based on this assumption is therefore $\begin{array}{cc}{\tilde{C}}_T^n=\sum _{\mathrm{jSP}}{C}_G^{\mathrm{jSP}}+\sum _{\mathrm{jST}}{C}_G^{\mathrm{jST}}+\sum _{\mathrm{jLP}}{C}_G^{\mathrm{iLP}}+\sum _{\mathrm{jLT}}{C}_G^{\mathrm{iLT}}+M\sum _{\mathrm{iSP}}{C}_C^{\mathrm{jSP}}+M\sum _{\mathrm{iST}}{C}_C^{\mathrm{jST}}+\sum _{\mathrm{iLP}}{C}_C^{\mathrm{iLP}}+\sum _{\mathrm{iLT}}{C}_C^{\mathrm{iLT}}& \left(4\right)\end{array}$

[0022] It is straightforward to prove that {tilde over (C)}_Tⁿ−C_Tⁿ≦0 for setup time analysis (M≈2), and {tilde over (C)}_Tⁿ−C_Tⁿ≧0 for hold time analysis (M≈0). In either case, capacitance values extracted based on equation (4) generally leads to optimistic timing results.

[0023] In the invention, a more reliable prediction of capacitance values is achieved by taking advantage of the fact that lateral coupling capacitance is the dominant factor in deep submicron circuits. Thus, if all conductor polygons that are parallel to conductive segment n are treated as switching and all conductor polygons that are transverse to conductive segment n are considered static, the segment capacitance value is $\begin{array}{cc}{\hat{C}}_T^n=\underset{\mathrm{jSP}}{M\sum }{C}_G^{\mathrm{jSP}}+\sum _{\mathrm{jST}}{C}_G^{\mathrm{jST}}+M\sum _{\mathrm{jLP}}{C}_G^{\mathrm{iLP}}+\sum _{\mathrm{jLT}}{C}_G^{\mathrm{iLT}}+M\sum _{\mathrm{iSP}}{C}_C^{\mathrm{jSP}}+\sum _{\mathrm{iST}}{C}_C^{\mathrm{jST}}+M\sum _{\mathrm{iLP}}{C}_C^{\mathrm{iLP}}+\sum _{\mathrm{iLT}}{C}_C^{\mathrm{iLT}}& \left(5\right)\end{array}$

[0024] where C_G^jSPand C_C^iSPare capacitances between the conductive segment n and conductor polygons parallel to and on the same hierarchical level as the conductive segment n, C_G^jLPand C_C^iLPare capacitances between the conductive segment n and conductor polygons parallel to and on a different hierarchical level than the conductive segment n, C_G^jSTand C_C^iSTare capacitances between the conductive segment n and conductor polygons transverse to and on the same hierarchical level as the conductive segment n, and C_G^jLTand C_C^iLTare capacitances between the conductive segment n and conductor polygons transverse to and on a different hierarchical level than the conductive segment n.

[0025] It should be noted that equation (5) does not depend on switching information to compute capacitance value, only information about the orientation of the conductor polygons with respect to the conductive segment n is needed. For nets in densely routed areas, the most significant portion of the net capacitance can be attributed to lateral coupling capacitances. In this case equation (5) yields conservative estimation of parasitic capacitances for timing analysis, i.e., Ĉ_Tⁿ−C_Tⁿ≧0 for setup time analysis (M≈2) and Ĉ_Tⁿ−C_Tⁿ≦0 for hold time analysis (M≈0). Because the routing direction on each conductive layer is predetermined, the approach above can be implemented by dynamically applying the Miller scaling factor M to the capacitance models according to the routing directions involved.

[0026] Equation (5) assumes that switching of the transverse nets is not strongly correlated. In other words, equation (5) essentially assumes that all the transverse conductor polygons above and below net N form pseudo-static reference grids. This yields capacitance values with a reasonable guard band but are not overly pessimistic. If the switching of the transverse nets is strongly correlated, then equation (5) can be modified as $\begin{array}{cc}{\hat{C}}_T^n=\underset{\mathrm{jSP}}{M\sum }{C}_G^{\mathrm{jSP}}+M\sum _{\mathrm{jST}}{C}_G^{\mathrm{jST}}+M\sum _{\mathrm{jLP}}{C}_G^{\mathrm{iLP}}+\underset{\mathrm{jLT}}{M\sum }{C}_G^{\mathrm{iLT}}+M\sum _{\mathrm{iSP}}{C}_C^{\mathrm{jSP}}+\underset{\mathrm{iST}}{M\sum }{C}_C^{\mathrm{jST}}+M\sum _{\mathrm{iLP}}{C}_C^{\mathrm{iLP}}+M\sum _{\mathrm{iLT}}{C}_C^{\mathrm{iLT}}& \left(6\right)\end{array}$

[0027] to provide a conservative capacitance estimation.

[0028] The following illustrates how the principles of the invention are applied to the net A in the integrated circuit design 32 shown in FIGS. 3 and 4. As shown in FIG. 4, net A has a wire segment A_N⁰along the y direction and a wire segment A_N−1⁰along the x direction. Table 1 shows a summary of the other nets in the design hierarchy of FIG. 3 and their relationship to net A.

[0029] Assume for illustration purposes that the conductor polygons C_N−1⁰and D_N−2¹are static, then the capacitance elements for net A are as shown in Table 2 below.

[0030] It should be noted that capacitances between transverse polygons that are on different metal layers are not included in Table 2.

[0031] Returning to FIG. 4, some of the conductor polygons B_N−1², C_N−1⁰, D_N−2¹, E_N², F_N⁰, G_N−1⁰, and H_N−1¹are too far from the conductive segments A_N⁰and A_N−1⁰to contribute significantly to the overall capacitance value of net A. For example, the capacitance between A_N⁰and D_N−2¹i.e., C(A_N⁰,D_N−2¹), can be approximated to zero because the horizontal distance between A_N⁰and D_N−2¹exceeds a selected threshold distance. In addition, A_N⁰and D_N−2¹, are on different metal layers. Similarly, the capacitances C(A_N−1⁰,G_N−1¹) and C(A_N−1⁰,H_N−1¹) can be approximated to zero because G_N−1⁰and H_N−1¹, respectively, are far from the wire segment A_N−1⁰. In general, a threshold distance is selected which will be used to determine when two nets are far apart enough that the capacitance between them can be approximated to zero. Table 3 shows the capacitance elements for net A if C(A_N⁰,D_N−2¹), C(A_N−1⁰,G_N−1⁰), and C(A_N−1⁰,H_N−1¹), are approximated to zero.

[0032] Using equation (3) and the capacitance elements in Table 3, the correct total capacitance value for net A is: $\begin{array}{cc}{C}_A=C\left(A_{N-1}^0,C_{N-1}^0\right)+C\left(A_{N-1}^0,D_{N-2}^1\right)+M\times C\left(A_N^0,F_N^0\right)+M\times C\left(A_N^0,G_{N-1}^0\right)+M\times \left[C\left(A_{N-1}^0,B_{N-1}^2\right)+C\left(A_N^0,E_N^2\right)\right]+M\times C\left(A_N^0,H_{N-1}^1\right)& \left(7\right)\end{array}$

[0033] Using traditional methods, i.e., equation (4), the estimated total capacitance value is: $\begin{array}{cc}{\tilde{C}}_A=C\left(A_{N-1}^0,C_{N-1}^0\right)+C\left(A_{N-1}^0,D_{N-2}^1\right)+M\times C\left(A_N^0,F_N^0\right)+M\times C\left(A_N^0,G_{N-1}^0\right)+C\left(A_{N-1}^0,B_{N-1}^2\right)+C\left(A_N^0,E_N^2\right)+M\times C\left(A_N^0,H_{N-1}^1\right)& \left(8\right)\end{array}$

[0034] The difference between the estimated capacitance using equation (4) and the correct total capacitance using equation (2) is then $\begin{array}{cc}{\tilde{C}}_A-C_A=\left(1-M\right)\times C\left(A_{N-1}^0,B_{N-1}^2\right)+C\left(A_N^0,E_N^2\right)+\left(1-M\right)\times C\left(A_N^0,H_{N-1}^1\right)& \left(9\right)\end{array}$

[0035] where M typically ranges from 0 to 2. For M greater than 1, the first and third terms in equation (9) are negative. If the sum of the absolute values of the first and third terms is equal to or greater than the second term, then {tilde over (C)}_A−C_A≦0. However, for conservative estimation of parasitic capacitances, it is desirable that {tilde over (C)}_A−C_A≧0 for M approximately equal to 2. For M less than 1, {tilde over (C)}_A−C_A≧0. However, for conservative estimation of parasitic capacitances, it is desirable that {tilde over (C)}_A−C_A≦0 for M approximately equal to 0. Thus as previously noted, the estimated value using the traditional approach in equation (4) is usually too optimistic.

[0036] A more conservative estimate of parasitic capacitances can be obtained using equation (5) or (6) of the present invention. Using equation (5), the overall capacitance for net A is $\begin{array}{cc}{\hat{C}}_A=M\times C\left(A_{N-1}^0,C_{N-1}^0\right)+C\left(A_{N-1}^0,D_{N-2}^1\right)+M\times C\left(A_N^0,F_N^0\right)+C\left(A_N^0,G_{N-1}^0\right)+M\times \left[C\left(A_{N-1}^0,B_{N-1}^2\right)+C\left(A_N^0,E_N^2\right)\right]+C\left(A_N^0,H_{N-1}^1\right)& \left(10\right)\end{array}$

[0037] The difference between the estimated capacitance using equation (5) and the correct total capacitance using equation (2) is then $\begin{array}{cc}{\hat{C}}_A-C_A=\left(M-1\right)\times C\left(A_{N-1}^0,C_{N-1}^0\right)+\left(1-M\right)\times C\left(A_N^0,G_{n-1}^0\right)+\left(1-M\right)\times C\left(A_N^0,H_{N-1}^1\right)& \left(11\right)\end{array}$

[0038] When M is approximately 0, the second and third terms are positive and the first term is negative. If the absolute value of the first term is greater than the sum of the second and third terms, then Ĉ_A−C_A≦0. When M is approximately 2, the first term is positive and the second and third terms are negative. If the first term is greater than the sum of the absolute values of the second and third terms, then Ĉ_A−C_A≧0. In deep submicron design, equation (11) is most/likely to be on the conservative side because lateral coupling capacitance is dominant, i.e., C(A_N−1⁰,C_N−1⁰)>>C(A_N⁰, G_N−1⁰) and C(A_N−1⁰,C_N−1⁰) >>C(A_N⁰, H_N−1¹).

[0039] In operation, and with reference to FIG. 2, the geometry processing tool 24 receives the integrated circuit layout 26 and analyzes the nets in the layout 26. For each net of interest N in the integrated circuit layout 26, the geometry processing tool 24 identifies the nets within a predetermined distance of the net of interest N. The geometry processing tool 24 further identifies the conductor polygons that are parallel or perpendicular to the conductive segments of the net of interest N. The information about these conductor polygons are then transferred to the capacitance solver 28. The capacitance solver 28 extracts the capacitance for the net of interest N using equation (5) or equation (6) and the orientation of the conductor polygons, as demonstrated for the net A above. The capacitances between the conductive segments of the net of interest N and the conduction polygons are obtained from the technology data 27. The capacitance extraction process can be repeated for all the nets in the integrated circuit layout to generate a capacitance matrix for the integrated circuit.

[0040] The hierarchical parasitic capacitance extraction method of the invention is advantageous because it reduces the gap between the parasitic values estimated based on a partial layout of an integrated circuit and the results of post-layout extraction. As previously mentioned, for integrated circuits with multimillion transistors, timing analysis has to be performed continually through the design cycle to ensure that the circuit that is being constructed meets specified design criteria. To perform the timing analysis, it is necessary to determine the total capacitance of all the nets in the integrated circuit layout. To compute the correct total capacitance of all the nets, one needs to be able to distinguish between switching nets and static nets. However, until the physical design of the integrated circuit is completed, the switching information of every net in the integrated circuit is not known. Advantageously, the parasitic extraction methodology of the present invention is based on routing directions instead of the incomplete switching information. Thus, realistic parasitic capacitance estimates can be obtained at any stage of the design process. At later stages of the design process, more layout information is available, allowing the interconnect model to be refined. The advantage of the present invention over the traditional extraction method becomes more evident as wire width and space shrink.

[0041] While the invention has been described with respect to a limited number of embodiments, those skilled in the art, having benefit of this disclosure, will appreciate that other embodiments can be devised which do not depart from the scope of the invention as disclosed herein. Accordingly, the scope of the invention should be limited only by the attached claims.