CN100405379C - A Fast Method for Routability Analysis of Integrated Circuits - Google Patents

Abstract

The present invention belongs to the field of IC CAD, and is characterized in that it comprises the following steps at one time: computer initialization, and establishment of GRG diagram, reading in wiring resources and circuit netlist; splitting multi-terminal net by Prim algorithm, and obtaining the minimum spanning tree under Manhattan distance ; Pre-estimate the routing probability of each side: if the pins of the two pin segments are at the opposite corners of the bounding box, use the grid model; if they are in the same row or column, use the extended bounding box to estimate the model; quickly Routing: The routing path is selected by means of inverse ratio of routing probability combined with random selection. The invention enables the distributability analysis to serve incremental layout or guide routing by quickly completing congestion estimation.

Description

A Fast Method for Routability Analysis of Integrated Circuits

technical field

In the field of integrated circuit computer aided design (IC CAD), especially in the field of standard cell (SC) overall layout.

Background technique

In the process of traditional computer-aided IC design, after the layout and wiring are completed, the wiring density information is fed back to the layout/router, and the wiring congestion problem can be solved to a certain extent by unwiring and rerouting. However, if the rewiring process still cannot solve the congestion, the designer has to modify the existing layout. The problem with the above-mentioned traditional design process is that the final congestion information is obtained after routing, and the routing process is close to the end of the design, and it is a very time-consuming process. Therefore, if the existing layout is modified, it means that most of the The design process needs to be redone.

It is not difficult to imagine that quickly obtaining accurate congestion information earlier in the design process can help guide the placement/routing process, so that congestion problems can be foreseen in advance and effective measures can be taken to deal with it before it actually occurs. Therefore, if the traditional process is modified, fast and effective functional modules are added to the layout process, and effective congestion evaluation is performed on the layout results to serve as layout feedback information and guide subsequent wiring work. This avoids going back to the previous layout stage for re-improvement when the subsequent routing cannot be completed in the end, so that the entire design can be completed in a reasonable time and reduce unnecessary iterations in the entire physical design. Like this, it can quickly and effectively evaluate the layout results, feed back to the layout and guide the subsequent routing work, we call it the distributability analysis, and the functional module that completes the distributability analysis is called the distributability analyzer.

Among the related domestic and foreign researches that have been reported and can be consulted, the research situation on "methods for congestion estimation after layout" can be listed, analyzed and summarized as follows:

Before introducing the method of congestion estimation, first introduce the meaning of congestion estimation.

Literature [P.N.Parakh, R.B.Brown and K.A.Sakallah, "Congestion Driven Quadratic Placement", Design Automation Conference, pages 275-278, 1998.] [M.Wang, X.Yang, K.Egoru and M.Sarrafzadeh, "Multi-center congestion estimation and minimization during placement", International Symposium on Physical Design, pages 147-152, 2000.] Using congestion information to improve layout quality, [Olivier Coudert, Jason Cong, Sharad Malik, Majid Sarrafzadeh, "INCREMENTAL CAD," ICCAD 2000, pp.236-243] Use congestion information as feedback for incremental layout, literature [R.T.Hadsell and P.H.Madden, "Improved Global Routing through Congestion Estimation", Design Automation Conference, pages 28-31, 2003.] [J.Cong and P.H.Madden, "Performance Driven Multi-Layer General Area Routing for PCB/MCM Designs", Design Automation Conference, pages 356-361, 1998.] [Jinjun Xiong, Lei He, "Probabilistic Congestion Model Considering Shielding for Crosstalk Reduction , "ASP-DAC 2005 pp.739-742.] [T.Jing, X.L.Hong, H.Y.Bao, et al, "SSTT: Efficient Local Search for GSI Global Routing", J.Comput.Sci. & Technol.2003, 18 (5): pp.632-639.] Using information from congestion estimation to improve routing. And [H-M.Chen et al. "Integrated Floorplanning and InterconnectPlannig", International Conference on Computer Aided Design, pages 354-357, 1999.] [Y.Ma et al, "Dynamic global buffer planning optimization based on detail block locating ana and conges ", Design Automation Conference, pages 806-811, 2003.] Crowd-driven optimization in floorplanning.

Based on the relevant domestic and foreign researches that have been reported and can be consulted, the methods of post-layout congestion estimation can be roughly divided into three categories:

●Experimental estimation model

●Router Estimation Model

●Probability estimation model

Experimental Estimation Model

The literature [C.-L.E.Cheng, "RISA: Accurate and efficient placement routability modeling," in Proc.Int.Conf.Computer-Aided Design, June 1994, pp.690-695.] utilizes a large number of experimentally derived routing Distribution map (WDM: wire distribution map) for congestion estimation; [M.Wang and M.Sarrafzadeh, "On the behavior of congestion minimization during placement," in Proc.Int.Symp.Physical Design, Apr.1999, pp.145 -150.] also utilizes an experimentally derived crowding estimation model.

Although such models can quickly estimate the degree of congestion, because they are experimental models, they rely too much on the characteristics of examples, and to some extent, may lose the objectivity of congestion estimation.

Router Estimation Model

Literature [S.Mayrhofer and U.Lauther, "Congestion-driven placement using a new multipartitioning heuristic," in Proc.Int.Conf.Computer-Aided Design, Nov.1990, pp.332-335.] [P.N.Parakh, R.B.Brown , and K.A. Sakallah, "Congestion driven quadratic placement," in Proc.35th Design Automation Conf. June 1998, pp.275-278.] [R.S.Tsay, S.C.Chang, and J. Thorvaldson, "Early wireability checking and 2-D congestion-driven circuit placement,” in Proc.5th Annu.IEEE Int.ASIC Conf.and Exhibit, Sept.1992, pp.50-53.] uses a simplified overall router to estimate congestion.

Although this model uses a simplified overall wiring model, it often faces a trade-off between accuracy and efficiency. On the other hand, due to the different routing strategies and routing capabilities of different simplified overall routers, different simplified overall routers may produce different results for the estimation of congestion. Moreover, the simplified congestion-estimated router may not agree with the subsequent results of the true router.

Probability Estimation Model

Literature [J.Lou, S.Krishnamoorthy and H.S.Sheng, "Estimating Routing Congestion using Probabilistic Analysis", International Symposium on Physical Design, pages 112-117, 2001.] [H-M.Chen et al. "Integrated Floorplanning and Interconnect Plannig" International Conference on Computer Aided Design, pages 354-357, 1999.] In order to better meet the requirements of objectivity and consistency, the method of probability estimation is proposed. In the former, a classic combination model (grid model) is used to solve the distribution of wire mesh routing (different from the experimental estimation model). The latter is to estimate the probability of the routing distribution of the line net under the premise of only considering the simple L-shaped and Z-shaped line nets (combined with some empirical estimates).

This model can quickly analyze the congestion of the results after layout, the estimated value of congestion is in good agreement with the actual situation after wiring, and can maintain good objectivity and consistency.

However, the limitation of [J.Lou] probability estimation model is that the combined probability model is used to evenly distribute the routing on all possible paths in the bounding box, resulting in a fractional solution, so it is impossible to obtain the precise routing of the wire network. At the same time, for the case where two pins are on the same row or column, the pure combination model limits the space for them to choose other possible routes. To address the above limitations, we propose a new estimation algorithm based on a probability model. First, use the bounding box to estimate the degree of congestion. For the distribution of the line network with two points collinear, the extended bounding box (extended bounding box) allows a certain degree of reasonable routing, so that it can bypass the nearby overcrowded area. . Finally the actual fast routing is guided by probabilities without using any iterations and optimizations (avoiding inconsistency and objectivity of congestion estimation). Under the guidance of the estimated congestion degree, we use the inverse ratio of the congestion degree as the selection probability of random routing for actual routing. In this way, the number of traces passing through the paths in each optional range can be made uniform in probability, so that in a small local area, it can avoid the unreasonable situation that one part is highly crowded, while the other adjacent part is relatively loose. Estimated congestion situation.

The "novelty search" has been carried out, and the search report is shown in Appendix 2.

Contents of the invention

The purpose of the present invention is to propose a fast integrated circuit distributability analysis method. The general idea of the present invention is: by quickly completing the estimated congestion, the distributability analysis method can serve incremental layout or guide wiring, thereby shortening the cycle of the entire physical design. The present invention is the distributability analysis method. Firstly, we expand the existing technology of a probability estimation model to pre-estimate the crowding of the problem model. Among them, the method of estimating two pins in the same row or column is mainly improved by using the technology of extended bounding box proposed by the present invention. Then, using the estimated congestion information and guided by probability, the fast routing proposed by the present invention is performed for all nets. To guarantee the objectivity and consistency of the distributability analysis method, this routing is constrained in a bounding box and without any iteration and crowding optimization. The purpose of this step is to make the distributability analysis method get more accurate and practical congestion estimation.

The overall flow chart of the present invention is shown in Fig. 1 .

The present invention is characterized in that it comprises the following steps successively:

Step 1 Initialize and build the general wiring diagram

Step 1.1 The computer reads in the number of rows N _row and the number of columns N _col necessary for dividing the overall wiring unit GRC grid on a multilayer wiring chip;

Step 1.2 Find the dual graph of GRC:

Take the center of each grid in GRC as a new vertex, and reconnect the center points of each adjacent grid to form a new edge, so as to obtain the general wiring graph GRG;

Step 1.3 On the multilayer wiring chip described in step 1.1, establish a Cartesian plane Cartesian coordinate system with the center of the chip as the origin, and project each wiring layer onto the coordinate plane;

Step 1.4 Mark the coordinates of each new vertex described in step 1.2 as v _{row, col} (x, y), and record the set of these new vertices as V, where row and col respectively represent the row and column of the GRG where the new vertex is located , x, y are the coordinates of the coordinate plane built in step 1.3;

Step 1.5 numbers the GRG vertex v _{row, col} and the GRG edge e _k connecting every two adjacent vertices respectively, and the vertices are numbered by the formula (row-1)×N _col +col-1, and the edge e _k is first press Rows are numbered from bottom to top and left to right, and then columns are numbered from left to right and bottom to top;

Step 1.6 The computer reads in the capacity c _k of each GRG edge e _k , and assigns an initial value of 0 to the channel usage λ _k of the edge e _k ;

Step 2 The computer reads in the netlist that characterizes the detailed connections of the circuit

Step 2.1 reads in the total number Mnet of the line net in the circuit;

Step 2.2 The computer executes for each wire net:

Step 2.2.1 read in the source point s and drain point set T of the line network;

Step 2.2.2 Map the source point s of the line network and all points in the leak point set T to each vertex of the GRG, and mark the point with the vertex number;

Step 2.2.3 Number each net according to the reading order;

Step 3 splitting the multi-terminal nets in the nets, but keeping the nets at both ends as they are;

For each multi-terminal net, perform the following operations:

Use the Prim algorithm to obtain the minimum spanning tree under the Manhattan distance to divide the two-pin end, forming a two-pin segment sequence composed of the two-pin segment division order, thereby dividing a multi-terminal line network into a two-pin segment sequence , the two-pin segment refers to a point pair set composed of two points close to each other in the vertex set of the multi-terminal line network, and there is no other point of the vertex set on the path formed by the point pair;

Step 4 pre-estimates the routing probability of each side of the GRG;

Step 4.1 Set the initial value of the routing probability value p _k corresponding to each edge e _k of the GRG to 0;

Step 4.2 Do the following operations for each two-pin segment of each two-terminal net or multi-terminal net:

Step 4.2.1 If the two pins u and v are in the lower left corner and upper right corner of the GRG diagram respectively, u is the lower left corner pin, and v is the upper right corner pin;

As shown in Figure 3, use u as the origin to establish a Cartesian plane Cartesian coordinate system for reference. The horizontal axis is in columns, and the horizontal left is the positive direction. If you pass through m horizontal grids, the vertical axis is in row units. , taking the vertical upward as the positive direction, if passing through n segments of vertical grids, the point v(m, n) is in the Ith quadrant, the origin is u(0, 0), and u(0, 0), v(m, n ) is called a bounding box u-v to form a rectangular frame for the vertices, and the length of any possible path from point u to point v is equal to the half perimeter of the bounding box u-v;

Thus, the probability of routing through a set horizontal edge AB (point B is on the right of point A) or vertical edge AC (point C is above point A) in the bounding box u-v is obtained by the following formula:

The probability of routing through the horizontal edge AB is:

p _k1 = H(x, y)/T(m, n) 0≤x≤m-1, 0≤y≤n,

Among them, T(m, n) represents the number of paths that may exist between starting from u(0,0) and point v(m, n), and the expression is:

$T(m,\mathrm{no})=\frac{(m+\mathrm{no})!}{m!\mathrm{no}!},$ m > 0, n >0;

H(x, y) represents the number of paths starting from the origin u(0, 0) to the point A(x, y) and passing through a certain horizontal edge AB with the point A(x, y) as the left end point. The following formula represents:

H(x,y)=T(x,y)T(m-x-1,n-y), 0≤x≤m-1, 0≤y≤n

T(x, y) represents the number of possible paths from the origin u(0, 0) to the point A(x, y), which can be obtained by the following formula:

$T(x,\mathrm{the\; y})=\frac{(x+\mathrm{the\; y})!}{x!\mathrm{the\; y}!},$ x > 0, y > 0,

T(m-x-1, n-y) represents the number of paths that may exist between point B(x+1, y) and point v(m, n), expressed by the following formula:

$T(m-x-1,\mathrm{no}-\mathrm{the\; y})=\frac{[(m-x-1)+(\mathrm{no}-\mathrm{the\; y})]!}{(m-x-1)!(\mathrm{no}-\mathrm{the\; y})!},$ m>x+1, n>y;

The probability of routing through the vertical edge AC is:

p _k2 = V(x, y)/T(m, n), 0≤x≤m, 0≤y≤n-1,

Among them, V(x, y) represents the number of paths starting from the origin u(0, 0) to point A(x, y) and passing through a certain vertical side AC with point A(x, y) as the lower end point, Expressed in the following formula:

V(x,y)=T(x,y)T(m-x,n-y-1), 0≤x≤m, 0≤y≤n-1,

Among them, T(m-x, n-y-1) represents the number of paths that may exist between starting from point C(x, y+1) and arriving at point v(m, n), expressed by the following formula:

$T(m-x,\mathrm{no}-\mathrm{the\; y}-1)=\frac{[(m-x)+(\mathrm{no}-\mathrm{the\; y}-1)]!}{(m-x)!(\mathrm{no}-\mathrm{the\; y}-1)!},$ m>x, n>y+1,

Then add the obtained p _k1 and p _k2 to the routing probabilities on sides AB and AC respectively, k ₁ and k ₂ are the numbers of sides AB and AC respectively;

Step 4.2.2 If the two pins u and v are located in the lower right corner and upper left corner of the GRG diagram respectively, u is the lower right corner pin, and v is the upper right corner pin;

Then use the pin u in the lower right corner as the origin to establish a Cartesian plane rectangular coordinate system for reference. The horizontal axis is in columns, and the ^horizontal left is the positive direction. In units of rows, with vertical upward as the positive direction, if passing through n ^* vertical grids, point v (m ^* , n ^* ) is in the Ith quadrant, the origin is u (0, 0), and u (0, 0) , v(m ^* , n ^* ) is called a bounding box uv for forming a rectangular frame for vertices, and the length of any possible path from point u to point v is equal to the half perimeter of the bounding box uv;

Therefore, calculate the probability of passing through a set horizontal edge AB (point B is on the left of point A) or vertical edge AC (point C is above point A) in the bounding box uv according to the method in step 4.2.1, where , just replace m and n in the formula in step 4.2.1 with m ^* and n ^* respectively;

Finally, add the obtained p _k1 and p _k2 to the routing probabilities on sides AB and AC respectively, k ₁ and k ₂ are the numbers of sides AB and AC respectively;

Step 4.2.3 If the two pins u and v are respectively in the same row or column of the GRG diagram, the points of the two pins are called a flat point pair, and a reference Cartesian plane Cartesian coordinate system is established with one pin as the origin, And make another pin fall on the positive semi-axis of the horizontal axis or the vertical axis. When in the same row, another pin falls on the positive semi-axis of the horizontal axis. When in the same column, the other pin falls on the positive semi-axis of the vertical axis. Positive semi-axis, then, using the extended bounding box estimation method, calculate the corresponding routing probability on the edge e _k as follows:

Step 4.2.3.1 Establish the extended bounding box according to the following method:

Make the bounding boxes of the flat point pairs in the same row (column) extend to the vertical (horizontal) direction by one row (column);

Step 4.2.3.2 In the bounding box, in the bounding box expansion direction, under the condition that the two pins u and v are allowed to deviate from the same row or column at most once, calculate the passed point (x, y ) is the routing probability p _k1 of a certain horizontal edge at the left end point and the routing probability p _k2 of the vertical edge going up or down through the point (x, 0):

When u and v are in the same row, as shown in Figure 4,

p _k1 = H ^* (x, y)/F(m'), 0≤x≤m'-1, -1≤y≤1,

Among them, m' is the number of columns between points u and v,

F(m') represents the number of possible paths from u to v in the extended bounding box u-v, calculated according to the following formula:

F(m')=m' ² +m'+1, m' is the number of columns between u and v,

H ^* (x, 0) represents the number of possible paths from the point u(0, 0) to the point (x, 0) passing through the horizontal edge with the point (x, 0) as the left end point, calculated by the following formula:

H ^* (x,0)=F(x)+F(m'-x-1)-1, 0≤x≤m'-1,

H ^* (x, ±1) represents the number of possible paths from point u(0, 0) to point (x, ±1) passing through the horizontal edge with the point (x, ±1) as the left end point, using the following formula calculate:

H ^* (x, ±1) = (x+1)(m'-x), 0≤x≤m'-1,

Among them, F(x) represents the number of possible paths from u to (x, 0) in the extended bounding box uv, the expression is: F(x)= ^x2 +x+1,

F(m'-x-1) represents the number of possible paths from (x+1, 0) to v(m', 0) in the extended bounding box uv, the expression is: F(m'-x-1) =(m'-x-1) ² +(m'-x-1)+1;

p _k2 = V ^* (x, y)/F(m'), 0≤x≤m'-1, -1≤y≤1,

Among them, m' is the number of columns between points u and v,

V ^* (x, 0) represents the number of paths from u(0, 0) to the point (x, 0) and passing through the vertical edge connected upwards (or downwards) with the point (x, 0), expressed as follows formula calculation:

V ^* (x,0)=m', 0≤x≤m',

When u, v are in the same column,

Let the number of rows between u and v be m", and substitute the value of m' in the above expression with m" to calculate the corresponding p _k1 , p _k2 ,

Then, add p _k1 and p _k2 to the p _k corresponding to each side, k ₁ and k ₂ are the numbers of each side;

Step 5 Quick Wiring

Step 5.1 Wiring each line net, see Figure 5 for the flowchart, and the specific operations are as follows:

Step 5.1.1 reads in the two-pin segment sequence that is divided by the Prim algorithm and marked with serial numbers in the order of division;

Step 5.1.2 Mark any pin point in the first two-pin segment;

Step 5.1.3 Beginning with the pin segment referred to in 5.1.2, perform the following operations for each two-pin segment in the sequence of two-pin segments in order of number:

Step 5.1.3.1 checks whether both pins of the current two-pin segment are marked;

Step 5.1.3.2 If yes, then remove a two-pin segment and re-go to step 5.1.3.1; otherwise, use the unlabeled pin as a starting point and perform the following steps;

Step 5.1.3.3 Set the starting point as the current point u ^* and mark it as visited;

Step 5.1.3.4 According to the convention of bounding box wiring, find two feasible vertex sets V _p and two feasible edge sets E _p = {e _k1 , e _k2 } adjacent to u ^* , and select an edge as follows:

Utilize the known rand() function in the C/C++ programming language to generate a random number between [0, 1] through rand()/RAND_MAX, wherein RAND_MAX is the maximum value of the known defined rand() to generate a random number;

The above method generates a random number, if the random number is not greater than p _k2 c _k1 /(p _k1 c _k2 +p _k2 c _k1 ), then select the edge e _k1 corresponding to the molecule c _k1 , i.e. i=k1, otherwise select the edge e _k2 , i.e. i=k2;

Step 5.1.3.5 takes the other endpoint v _i of the selected side e _i as the new current point u ^* ;

Step 5.1.3.6 Check whether the current point is marked, if not marked, mark the point and select the next point according to the method of step 5.1.3.4; if marked, record all the paths passed;

Step 5.2 After all the wire nets are laid out, add 1 to the channel usage λ _k of each side that each wire net passes through, and count the usage on each side;

Step 5.3 calculates the congestion degree value η _k =λ _k /c _k of each edge;

Step 6 output

Step 6.1 writes the congestion estimation result and the fast routing result into the industry standard database platform OpenAccess launched by Si2;

Step 6.2 outputs the evaluation report.

To test the accuracy and objectivity of the distributability analysis algorithm, we compare it with two other methods related to crowding estimation. One is the existing congestion-driven SSTT router [T.Jing, X.L.Hong, H.Y.Bao, et al, "SSTT: Efficient Local Search for GSI Global Routing", J.Comput.Sci. & Technol.2003, 18( 5): pp.632-639.], which can provide the results of actual wiring for comparison. The other is the traditional congestion estimator implemented by us according to the existing technology [J.Lou, S.Krishnanioorthy, and H.S.Sheng, "Estimating routing congestion using probabilistic analysis," in PTOC.Int.Symp.on Phgsacal Design, 2001], We tentatively call it EOPA, which uses a probabilistic analysis model. We adopt 6 test examples with different sizes and crowding levels, as shown in Table 1. The experimental environment is a Linux server with 3.0GHz CPU and 4GB memory. All tested methods used the well-known [Andrew B. Kahng, Stefanus Mantik, and Dirk Stroobandt, "Toward accurate models of achievable routing" IEEE Tran. Computer-Aided Design, vol.20, Issue 5, May 2001 pp.648- 659.] in the output of the resource estimation method.

We use the trace length after FREe routing to approximate the lower bound of the wire length of each example (if we can get SMT, steiner minimal tree, then we can get a lower bound of the exact wire length). So we define the minimumusage ratio (MUR) as the bus length of the FREEe wiring and The ratio of , where c _e and l _e are the capacity and length of side e, respectively. Therefore, MUR can be used to approximately estimate the lower bound of the congestion degree value of each example, and thus more objectively explain the congestion situation of the test example itself. Columns 2 and 3 of Table 2a) list the MUR and the estimated approximate minimum bus length, respectively, and column 4 gives the bus length for SSTT routing.

Table 1 Description of Test Cases

Test case # of cells # of nets Grids freecpu 3111 3040 74×68 u05614 32498 36452 205×205 u08421 48810 54743 251×251 u11228 65058 72968 290×290 u14035 81242 91129 324×324 u28070 162162 181934 458×458

Columns 2, 3 and 5 in Table 2b) list the running times of EOPA, FREEe and SSTT, respectively. It can be seen that EOPA and FREEe, as dedicated congestion estimators, are much faster than the actual congestion-driven router SSTT. This provides relatively quick feedback on the layout.

We define sigma as the standard deviation of the congestion degree of each wireway for the chip with the wired network. Right now:

$\mathrm{Sigma}=\sqrt{\underset{e\∈\mathrm{E.}}{\mathrm{\Σ}}{({\mathrm{\η}}_e-\stackrel{\‾}{\mathrm{\η}})}^2}$ ,in $\stackrel{\‾}{\mathrm{\η}}=\frac{1}{\left|\mathrm{E.}\right|}\underset{e\∈\mathrm{E.}}{\mathrm{\Σ}}{\mathrm{\η}}_e$ , η _e is the congestion value of edge e.

Sigma can be used to reflect the distribution of the crowded area after routing, and can measure the uniformity of routing resources used on each side of the GRG. The closer the value of sigma is to zero, the more evenly the wiring resources are utilized, and the better the wiring quality will be.

Since FREe and SSTT have carried out the actual wiring to the line network respectively, the 4th and 6th columns of Table 2b) give their sigma values respectively. It can be seen that the sigma value of FREEe is close to that of SSTT, but slightly larger than that of SSTT. It shows that, to some extent, the better the winding optimization performance is, the more uniform the wiring will be. However, as a congestion estimator, such routing optimization congestion will make it lose the meaning of objective evaluation. Therefore, on the basis of no excessive wiring and optimization, we can not only keep the approximate minimum line length, but also achieve a more even utilization of wiring resources under such constraints, so as to objectively and accurately evaluate the post-layout layout. The congestion situation, and has a good consistency with the SSTT results.

To further illustrate, the capability of FREEe congestion estimation. Without loss of generality, we take u05614 as an example and give the congestion degree diagrams of EOPA, FREEe and SSTT respectively, as shown in Fig. 6a), b), c). It can be seen that the characteristics of Figure 6 b) and c) are relatively similar, which is precisely because the fast routing under the guidance of the congestion estimation probability can bring a congestion estimation with better consistency with SSTT. At the same time, FREEe has not lost its requirement of objectivity.

Table 2 Experimental results

a) Comparison of total resource usage between FREEe and SSTT

TestCases MUR EstimatedMinimumTotal Length(μm) SSTTTotal Length(μm) freecpu 57.22% 1.79×10⁷ 2.07×10⁷ u05614 60.67% 4.44×10⁸ 5.02×10⁸ u08421 83.09% 6.78×10⁸ 7.78×10⁸ u11228 74.91% 8.64×10⁸ 1.03×10⁹ u14035 167.78% 1.16×10⁹ 1.33×10⁹ u28070 174.12% 2.43×10⁹ 2.83×10⁹

Estimated Minimum Total Length refers to the bus length after wiring by FREEe.

b) Performance comparison

Comparing Figure 6a) and b), it can be seen that EOPA only gives some areas that will cause congestion in the average sense, while FREe can accurately show the size of those areas corresponding to the GRG side after adding the actual wiring. To a certain extent, there will be line congestion.

In addition, FREEe also provides a detailed report after congestion estimation. It contains the maximum congestion values for the horizontal and vertical sides, the sum of the overcapacity for the horizontal and vertical sides, and so on.

Description of drawings

Figure 1: Overall flow chart of the present invention.

Figure 2: Schematic of the general wiring.

Figure 3: Coordinate plot of the two-pin segment u-v and its bounding box with pins in the lower left-upper right corner.

Figure 4: Coordinate plot of the two-pin segment u–v of a flat point pair and its extended bounding box.

Figure 5: Flowchart for routing a single net.

Figure 6: Congestion plot for test example u05614.

Figure 7: A box in the GRG of example u05614.

Figure 8: The wiring situation of the control line network on the GRG in the example u05614.

Figure 9: The wiring situation of the m1/n7630 line net on the GRG in the example u05614.

Figure 10: The routing of the m2/n7766 wire net on the GRG in the example u05614.

Figure 11: Example u05614 midline network routing on GRG

(m1/U2\/mult1\/ADD1\/pog_array[2][32]).

Detailed ways

First, on the problem model we abstracted, use the classic Prim algorithm to obtain the minimum spanning tree (MST). And according to the order in which the branches of the minimum spanning tree are generated, each multi-terminal net is divided into two-pin section sequences. It is a network at both ends and remains unchanged. Secondly, use the existing technology to find the wiring distribution between the two pins for the two ends of the wire network or pin segment at the diagonal position; for the two pins in the same row or column, The extended bounding box technology proposed by the present invention is used to obtain the wiring distribution between the two pins. It helps it get around overcrowded areas. Then, using the estimated congestion information and guided by probability, the fast routing proposed by the present invention is performed for all nets. This routing technology can not only avoid routing congestion, but also make the number of wires passing through each possible path substantially uniform.

For the current multi-layer wiring technology in IC design, the routing area is no longer a wiring channel between units, but a complete chip plane. The grid method can be used to divide the entire chip plane into several regions called the general wiring unit GRC according to the rows and columns, and then generate the dual graph of the GRC, that is, the general wiring diagram GRG shown in Figure 2. GRG consists of N _row × N _col nodes and edges connecting these nodes. The coordinates of the node v row _{, col} corresponding to GRC _{row, col} are the center point of GRC _{row, col} . The edge connecting two nodes v _{row1, col1} and v _{row2, col2} is called e _k ; l _k represents the Manhattan distance between two nodes v _{row1, col1} and v _{row2, col2} , which is called the length of e _k ; c _k represents e The capacity of _k indicates the number of connections that can pass between the two GRCs corresponding to the two nodes v _{row1, col1} and v _{row2, col2} . Therefore, the pin point Pin to be connected in the line network is mapped to a series of corresponding nodes in the GRG where it is located. In this way, congestion estimation can be formalized as a problem of solving the occupied capacity of each GRG edge on this model and mapping it to the grid area of the dual graph GRC. In addition, the wiring tree of each net is also obtained in this process.

The overall flow chart of this distributability analysis method is shown in Figure 1.

In order to realize, or specifically implement the present invention, we give the following description about the implementation of the invention.

Implement the computer system of the present invention: the distributability analysis method designed in the present invention will be implemented on a specific computer system, and this computer system is specifically described as follows:

A Linux workstation;

Linux operating system;

The industry standard database platform OA (OpenAccess) launched by Si2;

Standard C/C++ programming language;

Vim editor, gcc/g++ compiler and linker, gdb debugging tool, etc.

Now, a MCNC circuit instance u05614 is used as an embodiment of the present invention, combined with the algorithm of the present invention, its distributability analysis is carried out. The scale of the example is as follows:

386 pressure soldering blocks, 32498 standard units, 36452 wire nets;

The GRC grid is divided into 205 rows and 205 columns;

The coordinates of the lower left corner (-82000, -82000); the coordinates of the upper right corner (82080, 82080).

Step 1 Initialize and build GRG:

Open the database OA, and read in the number of rows N _row =205 and the number of columns N _col =205 necessary for dividing the GRC grid on the multilayer wiring chip. Generate the dual graph GRG of the GRC.

Establish a coordinate system with the center of the chip as the origin, the coordinates of the lower left corner point are (-82000, -82000), and the coordinates of the upper right corner point are (82080, 82080). At this point, there are a total of 42025 vertices in the GRG graph. Each vertex has a corresponding position coordinates (x, y), for example: the lower left vertex v ₁ , 1 (-81580, -81580), its left vertex v _{1, 2} (-80760, -81580), its top Vertex v _{2, 1} (-81580, -80760), and chip top right vertex v _{205, 205} (81660, 81660). Each vertex can be represented by v _{row, col} (x, y), where row represents the row of the point in the GRG, col represents the column of the point in the GRG, and (x, y) represents the position in the coordinate system. There are a total of 83640 edges on GRG.

In order to better illustrate the problem, we take the vertex of 100 rows and 100 columns as the grid on the lower left corner of the GRG, as shown in Figure 7. Like edges, each vertex has a unique number to mark v _{50, 100} , v _{51, 100} , v _{51, 101} , v _{50, 101} are 10144, 10349, 10350, 10145 respectively. The numbering of the edges connecting the four vertices is shown in Figure 7.

Read in routing resources. In this way, each GRG edge will have a non-negative number as the capacity of the edge. For example: e ₁ corresponds to capacity c ₁ =15, e ₂ corresponds to capacity c ₂ =15, e ₈₃₆₀₁ corresponds to capacity c ₈₃₆₀₁ =9, and the last side e ₈₃₆₄₀ corresponds to capacity c ₈₃₆₄₀ =6.

Still looking at Fig. 7, the capacities corresponding to each side are: c ₆₂₀₆₆ =12, c ₁₀₃₀₀ =15, c ₆₂₂₇₀ =12, c ₁₀₀₉₆ =15.

Step 2 read in the netlist:

Read the coordinates of the netlist from the OA, and map the pins falling in a certain GRC to the coordinates of the center point of the GRC, that is, the corresponding vertices of the GRG, and represent them with the number of the vertices. In this example, the total number of nets is Mnet=36452, but nets 1 to 257 are special nets and we will not deal with them in this design process. The following enumerates the situations of several line networks:

Line 258: the source number is 19967, and there are 38 leakage points (26281, 28537, 28541, ... 19517).

Line 36451: the source number is 21895, and there are 2 leaks (21889, 21479).

Line 18355: the source number is 16977, and there are 2 leaks (16976, 16990).

Line 36452: the source number is 21480, and there are 3 leakage points (21476, 21886, 21890).

Step 3 Multi-terminal line network splitting

Using Prim's MST split algorithm results are as follows:

Net 258: There are 39 pins in total, which are divided into 38 ordered segments. A few are listed below, and are represented sequentially by the number pairs of vertices corresponding to the pins. (19967, 20371), (20371, 18732), (18732, 16881), ... (8654, 8228), (8228, 7206) are the 1st, 2nd, 3rd, ... 37th, 38th two quotations respectively feet.

Line 36451: There are 3 pins in total, which are divided into 2 ordered segments, which are (21895, 21889) and (21889, 21479).

Line 18355: There are 3 pins in total, which are divided into 2 sequential segments, which are (16977, 16976) and (16977, 16990).

No. 36452 wire network: there are 4 pins in total, which are divided into 3 ordered segments, which are (21480, 21890), (21890, 21886) and (21886, 21476).

Step 4 Pre-estimation

After pre-estimation, the corresponding use probability distribution value on each edge is obtained. Among them, there are a total of 26,296 two-terminal line nets and two-pin segments with two pins in the same row/column, and the estimation model technology of the extended bounding box is used for them. For example, e ₁ corresponds to the use probability distribution value p ₁ =1.16, e ₂ corresponds to p ₂ =1.16, e ₈₃₆₀₁ corresponds to p ₈₃₆₀₁ =3.40, and the last edge e ₈₃₆₄₀ corresponds to p ₈₃₆₄₀ =0.78.

Looking at Figure 7, it can be obtained that p ₆₂₀₆₆ =6.85, p ₁₀₃₀₀ =11.21, p ₆₂₂₇₀ =8.41, and p ₁₀₀₉₆ =11.39.

Step 5 Quick Actual Wiring

For each line network, wire according to the method of flow chart 5. For example, in Figure 7, starting from v _{50, 100} as the current point, generate a random number 0.43 between [0, 1], and compare it with p ₁₀₀₉₆ c ₆₂₀₆₆ /(p ₆₂₀₆₆ c ₁₀₀₉₆ +p ₁₀₀₉₆ c ₆₂₀₆₆ )=0.57 , the former is small, then select the edge e ₆₂₀₆₆ corresponding to c ₆₂₀₆₆ ; reach the next vertex through the selected edge, and use this vertex as the new current point. Repeat the same method until all wire meshes are finished.

The wiring situation of several wire nets is listed as follows:

Line 258: the name is control, and the wiring is shown as the thick connection in Figure 8.

No. 36451 line network: the name is m1/n7630, and the wiring is as shown in the thick connection in Figure 9.

No. 18355 line network: the name is m2/n7766, and the wiring situation is shown in the thick connection in Figure 10.

Line network No. 36452: the name is m1/U2\/mult1\/ADD1\/pog_array[2][32], and the wiring is shown as the thick connection in Figure 11.

After laying out the lines for all line nets, count the channel usage corresponding to each GRG edge and calculate the congestion value. For example, e ₁ corresponds to channel usage λ ₁ =1, congestion degree η ₁ =0.07 (η _k =λ _k /c _k ), e ₂ corresponds to λ ₂ =1, η ₂ =0.07, e ₈₃₆₀₁ corresponds to λ ₈₃₆₀₁ =5, η ₈₃₆₀₁ =0.56, the last edge e ₈₃₆₄₀ corresponds to λ ₈₃₆₄₀ =0, η ₈₃₆₄₀ =0.00.

Looking at Fig. 7, it can be obtained that λ ₆₂₀₆₆ =6, η ₆₂₀₆₆ =0.50, λ ₁₀₃₀₀ =4, η ₁₀₃₀₀ =0.27, λ ₆₂₂₇₀ =8, η ₆₂₂₇₀ =0.67, λ ₁₀₀₉₆ =17η ₁₀₀₉₆ =1.13.

Step 6 output

Write the results to OA, and output the report file. From the report, maxH: 2.9917 maxV: 5.8980 O_H: 17073.59 O_V: 34288.23 B_H: 1290.2151 B_V: 4274.4438 Sigma: 2.1634.

Among them, maxH is the maximum degree of crowding on the horizontal side;

maxV Maximum congestion on the vertical side;

O_H The sum of the squares of horizontal edge congestion;

O_V The sum of the squares of vertical edge crowding;

B_H The overcapacity (minus 1) congestion degree sum of the horizontal side;

B_V Overcapacity (minus 1) congestion degree sum of vertical sides;

The standard deviation of congestion on each side of Sigma is used to measure whether the wiring resources (capacity of each side) are evenly occupied.

In order to realize, or specifically implement the present invention, we give the following description about the implementation of the invention.

The computer system implementing the present invention: the distributability analysis method designed in the present invention is to be implemented on a specific computer system, and the computer system is specifically described as follows.

A Linux server;

Linux operating system;

The industry standard database platform OA (OpenAccess) launched by Si2;

Standard C/C++ programming language;

Vim editor, gcc/g++ compiler and linker, gdb debugging tool, etc.

Theorem The number of possible paths from u to v in the extended bounding box uv is F(m)= ^m2 +m+1, where m is the number of columns or rows separating u and v.

prove:

Without loss of generality, we assume that the positions of the two vertices in the coordinate system are u(0, 0) and v(m, 0) respectively, as shown in Figure 4. We allow at most one directed away and turning back trace in the extended frame. Therefore, there are three possible ways to get from v to u. The first is to go up from v and then right to A. The subsequent connections are the same as the upper left-bottom right relative positions, and the total number of possible paths is T(m-1, 1). The second is to go down from v and then to the right to B. According to the previous analysis, the total number of possible paths is also T(m-1, 1). The third is to proceed horizontally right from v directly to C, and the number of possible paths is F(m-1). It can be seen that F(m)=2T(m-1, 1)+F(m-1), and F(1)=3.

Solving the previous recursive formula, we can obtain F(m)=m ² +m+1, and the proof is complete.

Claims (1)

1. an integrated circuit cloth analytical approach fast is characterized in that, this method realizes successively according to the following steps in computing machine:

Step 1 initialization is also set up loose routing figure

Step 1.1 computing machine reads in and divides the necessary line number N of global routing cell GRC grid on the multilayer wiring chip _Row, columns N _Col

Step 1.2 is asked the dual graph of GRC:

Center with each grid among the GRC is new summit, and the central point that reconnects each adjacent mesh forms new limit, thereby obtains loose routing figure GRG;

Step 1.3 is that initial point is set up the Cartesian plane rectangular coordinate system with the chip center, and each wiring layer is projected on this coordinate plane on the described multilayer wiring chip of step 1.1;

The coordinate on each new summit described in step 1.4 markers step 1.2 is v _{Row, col}(x y), and is designated as V to the set on these new summits, row wherein, and col represents the row and column of this new summit place GRG respectively, and x, y are the coordinates of coordinate plane that step 1.3 is built;

Step 1.5 is described GRG vertex v _{Row, col}And the GRG limit e that connects per two adjacent vertexs _kNumber summit formula (row-1) * N respectively _Col+ col-1 numbering, limit e _kThen press row earlier and number from left to right from bottom to top, arrange in numerical order from bottom to top from left to right by row again;

Step 1.6 computing machine reads in every GRG limit e _kCapacity c _k, give limit e _kPassage use amount λ _kComposing initial value is 0;

Step 2 computing machine reads in the net table that characterizes the detailed connection of circuit

Step 2.1 is read in the sum M net of gauze in the circuit;

Step 2.2 computing machine is carried out each bar gauze:

Step 2.2.1 reads in the source point s and the leak source collection T of gauze;

Step 2.2.2 is mapped on each summit of described GRG having a few among the source point s of gauze and the leak source collection T,

And with summit numbering to above-mentioned some mark;

Step 2.2.3 is every gauze numbering by reading in order;

Step 3 splits the multiterminal gauze in the described gauze, but the two ends gauze maintains the original state;

Carry out following operation for each bar multiterminal gauze:

The minimum spanning tree that utilizes the Prim algorithm to try to achieve under the manhatton distance is divided the two pins section, the two pins section sequence that formation is constituted by two pins section stripe sequence, thereby a multiterminal gauze is divided into a two pins section sequence, described two pins section is meant in the vertex set of this multiterminal gauze, by at a distance of 2 near some pair sets that constitute, there is not other point of vertex set on to the path that constitutes by this;

The cabling probability on each limit of step 4 pre-estimation GRG;

Step 4.1 is set every limit e of GRG _kPairing cabling probable value p _kInitial value be 0;

Each two pins section of pair of every two ends gauze of step 4.2 or multiterminal gauze is done as follows:

Step 4.2.1 is as if two pin u, and v is in the lower left corner of GRG figure and the position in the upper right corner respectively, and u is a lower left corner pin, and v is a upper right corner pin;

Then set up with reference to using the Cartesian plane rectangular coordinate system as initial point with u, transverse axis is with the unit of classifying as, and is left positive dirction with level, if through m section horizontal grid, the longitudinal axis is with behavior unit, being positive dirction vertically upward, if through n section vertical grid, (m n) is in the I quadrant to some v, initial point is u (0,0), with u (0,0), (m n) is called bounding box u-v for the summit is constituted rectangle frame to v, and the length from the u point to any possible path of v point equals the semi-perimeter of bounding box u-v;

Thereby, obtain setting the cabling probability of horizontal sides AB or vertical edges AC by following formula through certain bar in the bounding box u-v, wherein: the B point is on the A point right side, and the C point is on the A point;

Cabling probability through horizontal sides AB is:

p _kl＝H(x，y)/T(m，n)0≤x≤m-1，0≤y≤n，

Wherein, T (m, n) expression from u (0,0) set out a v (expression formula is for m, the number of path that may exist between n):

$T(m,n)=\frac{(m+n)!}{m!n!},m>0,n>0;$

H (x, y) expression from initial point u (0,0) set out an A (x, y), and through with an A (x is the number of path of a certain specified level limit AB of left end point y), represents with following formula:

H(x，y)＝T(x，y)T(m-x-1，n-y)，0≤x≤m-1，0≤y≤n

T (x, y) expression from initial point u (0,0) to a some A (x, the number of path that may exist between y) draws by following formula:

$T(x,y)=\frac{(x+y)!}{x!y!},x>0,y>0,$

T (m-x-1, n-y) expression from a B (x+1, y) set out a v (m, the number of path that may exist between n) are represented with following formula:

$T(m-x-1,n-y)=\frac{[(m-x-1)+(n-y)]!}{(m-x-1)!(n-y)!},m>x+1,n>y;$

Cabling probability through vertical edges AC is:

p _k2＝V(x，y)/T(m，n)，0≤x≤m，0≤y≤n-1，

Wherein, V (x, y) expression from initial point u (0,0) set out an A (x, y) between through with an A (x is the number of path of a certain specific vertical edges AC of lower extreme point y), represents with following formula:

V(x，y)＝T(x，y)T(m-x，n-y-1)，0≤x≤m，0≤y≤n-1，

Wherein, T (m-x, n-y-1) expression from a C (x, y+1) set out point of arrival v (m, the number of path that may exist between n) are represented with following formula:

$T(m-x,n-y-1)=\frac{[(m-x)+(n-y-1)]!}{(m-x)!(n-y-1)!},m>x,n>y+1,$

Again the p of gained _K1, p _K2Be added to limit AB respectively, the cabling probability on the AC, k ₁, k ₂Be respectively limit AB, the numbering of AC;

Step 4.2.2 is as if two pin u, and v is in the lower right corner of GRG figure and the position in the upper left corner respectively, and u is a lower right corner pin, and v is a upper right corner pin;

Then set up with reference to use the Cartesian plane rectangular coordinate system as initial point with the pin u in the lower right corner, transverse axis is with the unit of classifying as, and is left positive dirction with level, as if passing through m left ^*Section horizontal grid, the longitudinal axis are with behavior unit, to be positive dirction vertically upward, if through n ^*The section vertical grid, some v (m ^*, n ^*) being in the I quadrant, initial point is u (0,0), with u (0,0), v (m ^*, n ^*) for being called, summit formation rectangle frame is bounding box u-v, the length from the u point to any possible path of v point equals the semi-perimeter of bounding box u-v;

Thereby, calculate the cabling probability of setting horizontal sides AB or vertical edges AC through certain bar in the bounding box u-v according to the method among the step 4.2.1, wherein, the B point is on the A point left side, and the C point is on the A point; As long as the m in the formula among the step 4.2.1, n changes m respectively into ^*, n ^*Get final product;

At last, again the p of gained _K1, p _K2Be added to limit AB respectively, the cabling probability on the AC, k ₁, k ₂Be respectively limit AB, the numbering of AC;

If step 4.2.3 is two pin u, when v is in the same row or column of GRG figure respectively, claiming two pins point right for flat spot, is that initial point is set up with reference to using the Cartesian plane rectangular coordinate system with a pin, and make another pin drop on the positive axis of the transverse axis or the longitudinal axis, when being in same delegation, another pin drops on the positive axis of transverse axis, when being in same row, another pin drops on the positive axis of the longitudinal axis, then, with the extended boundary frame estimation technique, calculate limit e by following method _kOn corresponding cabling probability:

Step 4.2.3.1 sets up the extended boundary frame according to following method:

Make the right bounding box of flat spot of same delegation/row, respectively expand delegation/row to the vertical/horizontal direction;

Step 4.2.3.2 on the bounding box propagation direction, allows once to deviate from described two pins u at most in bounding box, under the condition of the residing same row or column of v, (x y) is the cabling Probability p of a certain specific horizontal sides of left end point to be calculated as follows the point of process _K1With the cabling Probability p of calculating through point (x, 0) vertical edges up or down _K2: work as u, when v is in delegation,

p _k1＝H ^*(x，y)/F(m′)，0≤x≤m′-1，-1≤y≤1，

Wherein, m ' is a u, the columns between v,

F (m ') be illustrated in the possible path number from u to v among the extended boundary frame u-v, calculate by following formula:

F (m ')=m ' ²+ m '+1, m ' is the columns of being separated by between u and the v,

H ^*(x, 0) expression is the possible path number of the horizontal sides of left end point to process between point (x, 0) with this point (x, 0) from a u (0,0), calculates with following formula:

H ^*(x，0)＝F(x)+F(m′-x-1)-1，0≤x≤m′-1，

H ^*(x, ± 1) expression is the possible path number of the horizontal sides of left end point to process between point (x, ± 1) with this point (x, ± 1) from a u (0,0), calculates with following formula:

H ^*(x，±1)＝(x+1)(m′-x)，0≤x≤m′-1，

Wherein, F (x) is illustrated in the possible path number from u to (x, 0) among the extended boundary frame u-v, and expression formula is: F (x)=x ²+ x+1,

F (m '-x-1) being illustrated among the extended boundary frame u-v possible path number of (m ', 0) from (x+1,0) to v, expression formula is: F (m '-x-1)=(m '-x-1) ²+ (m '-x-1)+1;

p _k2＝V ^*(x，y)/F(m′)，0≤x≤m′-1，-1≤y≤1，

Wherein, m ' is a u, the columns between v,

V ^*(x, 0) expression is arrived point (x, 0) from u (0,0), and passes through the number of path of the vertical edges that is connected up or down with point (x, 0), calculates with following expression formula:

V ^*(x，0)＝m′，0≤x≤m′，

Work as u, when v is positioned at same row,

If u, the line number between the v is m ", with the value m of m ' in the above-mentioned expression formula " just substitution calculates corresponding p _K1, p _K2,

Then, again with p _K1, p _K2Be added to the p of each limit correspondence _kOn, k ₁, k ₂Be respectively the numbering on each limit; Step 5 connects up fast

Step 5.1 connects up to each bar gauze, and concrete operations are as follows:

Step 5.1.1 reads in after the division of Prim algorithm, and marks the two pins section sequence of sequence number by stripe sequence;

Any pin point in first two pins section of step 5.1.2 mark;

Step 5.1.3 pin section of indication from 5.1.2 begins, and presses the label order successively for each the two pins section in the two pins section sequence, carries out following operation:

Step 5.1.3.1 checks whether two pins of current two pins section all are labeled;

Step 5.1.3.2 is if get next two pins section so, and forward step 5.1.3.1 again to; Otherwise, with unlabelled pin as starting point, and step below carrying out;

Step 5.1.3.3 is made as current some u with starting point ^*, and to the accessed mistake of its mark;

Step 5.1.3.4 finds and u according to the agreement of bounding box wiring ^*Two adjacent feasible vertex set V _p

Set E with two feasible limits _p={ e _K1, e _K2, select a limit as follows:

Produce a random number between [0,1], if this random number is not more than p _K2c _K1/ (p _K1c _K2+ p _K2c _K1),

Select and molecule c so _K1Corresponding limit e _K1, i.e. i=k1, otherwise select limit e _K2, i.e. i=k2;

Step 5.1.3.5 is with selected limit e _iAnother end points v _iAs current new u ^*

Step 5.1.3.6 checks whether current point is labeled, if be not labeled, then mark this and according to the step

The method of rapid 5.1.3.4 is selected next point; If be labeled, then write down all through the path;

Behind the good line of step 5.2 a wired network cloth, to the passage use amount λ on the limit of every gauze process _kAdd up 1, add up the use amount on every limit;

Step 5.3 is calculated the crowding value η on each limit _k=λ _k/ c _k

Step 6 output

Step 6.1 will crowd estimated result and fast the wiring result write the industry member standard database platform OpenAccess that Si2 releases;

Step 6.2 output report of accessment and test.

Images