CN107832519B - Multilayer overall wiring method for high-performance X structure in ultra-large scale integrated circuit - Google Patents

Abstract

The invention relates to a high-performance X-structure multi-layer overall wiring method in a super large-scale integrated circuit. On the basis of the XGRouter router, the invention provides a new type of wiring method, a subgroup optimization algorithm and a labyrinth wiring based on the new wiring cost. The combination of the pre-wiring capacity reduction strategy in the initial stage, the design of the dynamic resource scheduling strategy, and then the introduction of the multi-layer wiring model, which simplifies the integer linear programming model of XGRouter, and finally builds a high-performance X-structure multi-layer overall wiring device. The simulation results of the standard test circuit show that, compared with other types of overall routers, the most important optimization objectives in multi-layer overall routing—the overflow number and the total cost of line length, both achieve the best results.

Description

High-performance X-structure multi-layer overall wiring method in VLSI

technical field

The invention relates to the technical field of integrated circuit computer-aided design, in particular to a high-performance X-structure multi-layer overall wiring method in an ultra-large-scale integrated circuit.

Background technique

As the size of semiconductors and interconnects continues to shrink, interconnects seriously affect many key design indicators. Therefore, the routing stage, which organizes the actual routing positions of interconnects, is currently used in very large-scale integration (very largescale integration, referred to as for short). VLSI) physical design becomes particularly important. The complex routing process is composed of two stages: general routing and detailed routing. In the overall routing, the routing of each net is assigned to each channel routing area, and the routing problem of each channel area is clearly defined. The detailed routing gives the specific location of each net in the channel area. Therefore, the quality of the overall routing seriously affects the success rate of detailed routing, which in turn plays a decisive role in the performance of the entire chip.

Overall routing is an extremely important part of the physical design of VLSI, so scholars have proposed many effective algorithms and overall routing techniques, which can be mainly divided into serial algorithms and parallel algorithms, especially serial algorithms. The overall wiring approach is able to handle large-scale problems. However, the serial algorithm has a serious dependence on the routing order of the net or the definition of the routing cost, and this potential characteristic seriously affects the overall routing quality. The parallel algorithm represented by integer linear programming can reduce the dependence of the wiring result on the order of the net, and obtain a better overall wiring scheme. Some of these methods represented by integer linear programming solve the integer linear programming model by first relaxing it into a linear programming model to reduce the time complexity of solving the programming model, and then using the random rounding method to convert the linear solution into a nonlinear solution. , so that the routing scheme obtained by the random rounding process may seriously deviate from the real solution.

Most of the overall routing algorithms are based on the Manhattan structure model. When the optimization strategy based on the Manhattan structure is used to optimize the length of the interconnecting line, its optimization ability is limited because the winding direction can only be horizontal and vertical. . Therefore, it is necessary to start from the root and change the traditional Manhattan structure, so researchers began to try to use the non-Manhattan structure as the basic model for wiring to achieve the optimization of the overall performance of the chip. Scholars have carried out research on non-Manhattan structures that can bring about a considerable reduction in line length and other physical design indicators. In particular, the emergence of a special industrial alliance to promote the X structure provides the basis for realization and verification of such research. The current research on the X-structure wiring mainly includes two aspects: the construction of the X-structure wiring tree and the overall routing algorithm design of the X-structure. With the introduction of the X structure, the routing algorithm design becomes more complex. However, some researches on the overall routing of the X-structure mainly focus on the line length optimization, and these algorithms are based on the early Steiner tree construction method, which leads to the fact that the overall routing algorithm of the X-structure is less effective than the overall routing algorithm of the Manhattan structure. The routing results of the partial work are worse than the routing results of the Manhattan structure in terms of the ability to optimize the total cost of the line length.

As the design of integrated circuits enters the nano field, the number of wiring metal layers increases, the line width is greatly reduced, and the wiring spacing is also greatly reduced, which greatly improves the performance and density of the circuit, so multi-layer wiring emerges as the times require. , and has attracted extensive attention from many research institutions. However, the existing research on the overall routing problem of non-Manhattan structure is limited to the research on the overall routing problem of single-layer structure. As far as we know, there is no research on the overall routing algorithm considering the two conditions of non-Manhattan structure and multi-layer structure. .

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a high-performance X-structure multilayer overall wiring method in VLSI, so as to overcome the defects existing in the prior art.

In order to achieve the above object, the technical scheme of the present invention is: a high-performance X-structure multi-layer overall wiring method in a very large-scale integrated circuit, comprising the following steps:

Step S1: In the initial wiring stage, establish the X-structure Steiner minimum tree;

Step S2: carry out multi-terminal line network decomposition;

Step S3: reducing the pre-wiring capacity in the initial wiring stage to half of the original capacity;

Step S4: judging whether the current wire nets at both ends meet the connectable conditions; if so, perform pre-connection and traverse all wire nets; otherwise, traverse all wire nets;

Step S5: After the traversal is completed, enter the main stage of wiring;

Step S6: find the most crowded area as the current wiring area;

Step S7: adding the wire nets at both ends completely located in the current wiring area to the wiring set;

Step S8 : by adding a new routing method and establishing an ILP model, the particle swarm optimization algorithm is used to solve the optimal solution in each routing area;

Step S9: judging whether the wire net corresponding to the optimal solution obtained based on the particle swarm optimization algorithm solution can be connected; if so, mark the wire net as connected, otherwise, mark it as unconnected;

Step S10: use the maze algorithm based on the new routing edge cost for routing;

Step S11: determine whether the wiring area can be expanded, if so, expand the wiring area according to the preset threshold, and go to the step S7; otherwise, go to the step S12;

Step S12: Based on the dynamic resource scheduling, and using the layer scheduling of the multi-layer wiring model, the overall wiring of the X-structure multi-layer is completed.

In an embodiment of the present invention, in the step S8, the new type of routing method includes: if the angle between the wire mesh pins at both ends of the direct connection is 0°, 45°, 90° or 135°, using Connect as follows:

Method ¹ : 450 sides and ¹³⁵⁰ sides are alternately connected;

Method ² : 450 sides, ¹³⁵⁰ sides and horizontal or vertical sides are alternately connected;

Method 3: The horizontal and vertical sides are alternately connected.

In an embodiment of the present invention, in the step S12, the dynamic resource scheduling includes: for sparse channels and congested channels with channel capacity correlations, under the condition that the total channel capacity remains unchanged, by setting the channel capacity dynamic The allocation threshold and resource allocation quota are dynamically allocated by channel capacity, and the channel capacity obtained by the two channels tends to adapt to the wiring requirements of the target network.

In an embodiment of the present invention, based on testing the feasibility of dynamic allocation of each connected channel capacity one by one, dynamic allocation of channel capacity is performed on the required channels.

In an embodiment of the present invention, dynamic allocation of channel capacity is performed between sparse channels and crowded channels that are channels related to each other in channel capacity.

In an embodiment of the present invention, the channel capacity dynamic allocation threshold is 2, and the resource allocation quota is 2.

Compared with the prior art, the present invention has the following beneficial effects:

(1) Compared with XGRouter, the main stage routing of the new router introduces a new type of routing method and maze routing based on the new routing cost, combined with the PSO algorithm to solve, adding a new type of routing method helps to improve the initial stage abandonment At the same time, moving the maze routing strategy to the main stage after using PSO for wiring in the box area each time, it will help the collection of undistributed nets in the current box area to achieve higher The routing rate completes the wiring work.

(2) Compared with XGRouter, the initial wiring of the new router reduces the pre-wiring capacity of the initial wiring stage to half of the original capacity, so that some wire nets and wiring resources can be left in the main stage for wiring, making more full use of the global PSO algorithm The optimization ability is further strengthened, and the new type of routing method and the maze routing based on the new routing cost are combined with the PSO algorithm to solve.

(3) Since the capacity of each wiring edge in XGRouter is constant, the capacity is static during the wiring process, which may cause some wiring edges to be underutilized and in a sparse state, and some wiring edges are overused and crowded state. In the design of the high-performance X-structure multilayer overall router FZU-Router, a dynamic resource scheduling strategy is introduced, and the routing resources are dynamically adjusted during the routing process to make more full use of the routing resources for routing, which further improves the overall router. The optimization ability in the two aspects of overflow number and total line length cost has reached the best.

(4) The high-performance X-structure multi-layer overall router FZU-Router constructed by the present invention is used to solve the multi-layer overall wiring problem, and the layer allocation strategy adopts the best multi-layer wiring model verified in the previous work. The assignment phase assigns segments of the relevant nets to the appropriate routing layers.

Description of drawings

FIG. 1 is a flowchart of a high-performance X-structure multi-layer overall wiring method in a VLSI according to the present invention.

FIG. 2( a ) is a schematic diagram of an initial pin distribution in an embodiment of the present invention.

FIG. 2( b ) is a schematic diagram of the wiring scheme of the Steiner minimum tree of the X structure in an embodiment of the present invention.

FIG. 3( a ) is a schematic diagram of two wire nets to be wired distributed on the wiring diagram according to an embodiment of the present invention.

FIG. 3( b ) is a schematic diagram of decomposing N2 and constructing candidate solutions for each two-end net in an embodiment of the present invention.

FIG. 4 is a schematic diagram of layer scheduling of a multi-layer wiring model according to an embodiment of the present invention.

FIG. 5 is a schematic diagram showing the pin distribution of four types of wire nets at both ends that can be directly connected in the initial wiring stage according to an embodiment of the present invention.

FIG. 6 is a schematic diagram of four situations in which direct connection cannot be made due to the limitation of the capacity of the wiring side in the initial wiring stage according to an embodiment of the present invention.

FIG. 7( a ) is a schematic diagram showing that the pins of N1 cross even-numbered grids in the newly added wiring edge selection method according to an embodiment of the present invention.

FIG. 7( b ) is a schematic diagram showing that the pins of N1 cross an odd-numbered grid in a newly added wiring edge selection method according to an embodiment of the present invention.

FIG. 7( c ) is a schematic diagram of N2 in a newly added wiring edge selection method in an embodiment of the present invention.

FIG. 8 is a schematic diagram of a combination strategy of using PSO in the main stage and labyrinth routing based on new routing edge cost in an embodiment of the present invention.

FIG. 9( a ) is a schematic diagram of capacity reduction without pre-wiring in the initial wiring stage according to an embodiment of the present invention.

FIG. 9( b ) is a schematic diagram of reducing the capacity of pre-wiring in the initial wiring stage according to an embodiment of the present invention.

FIG. 10 is a schematic diagram of channel capacity correlation in an embodiment of the present invention.

FIG. 11( a ) is a schematic diagram of not using dynamic resource allocation in an embodiment of the present invention.

FIG. 11(b) is a schematic diagram of dynamic allocation in an embodiment of the present invention.

FIG. 12 is a flowchart of Algorithm 1 in an embodiment of the present invention.

FIG. 13 is a flowchart of Algorithm 2 in an embodiment of the present invention.

FIG. 14 is a flowchart of Algorithm 3 in an embodiment of the present invention.

Detailed ways

The technical solutions of the present invention will be described in detail below with reference to the accompanying drawings.

Aiming at the overall wiring problem considering the two important conditions of non-Manhattan structure and multi-layer wiring structure, taking X structure as the representative of non-Manhattan structure, the present invention is based on the integer programming model (integer Linear programming (ILP) and particle swarm optimization (PSO), aiming at a series of deficiencies in the existing work, proposed four effective improvement strategies, and introduced a multi-layer wiring model and layer scheduling strategy. Thus, a high-performance X-structure multilayer overall router is constructed, called FZU-Router. The work of the present invention is the first time to effectively solve the multi-layer overall wiring problem of the X structure, and the simulation experiment results on the reference circuit of the multi-layer overall wiring problem also fully verify the feasibility and effectiveness of the relevant strategies and algorithms of the present invention. In the multi-layer wiring problem, the two most important indicators, the number of overflows and the total cost of line length, bring significant optimization effects.

Further, a high-performance X-structure multilayer overall wiring method in a VLSI provided by the present invention, as shown in FIG. 1 , includes the following steps:

Step S1: In the initial wiring stage, establish the X-structure Steiner minimum tree;

Further, in this embodiment, the Steiner minimum tree method of the X-structure is to connect a given set of pins at a minimum cost by introducing Steiner points. In addition to the traditional horizontal and vertical directions, the connecting lines also allow 45° and 135° winding directions. As shown in Figure 2 (a), an initial pin distribution is given, and Figure 2 (b) is a wiring scheme for constructing an X-structure Steiner minimum tree.

Step S2: carry out multi-terminal line network decomposition;

Further, in this embodiment, Figure 3 (a) shows two wire nets N ₁ and N ₂ to be wired and the maximum channel capacity is 2. In this embodiment, the multi-terminal net N ₂ is decomposed into three two-end nets (SG ₈ , SG ₆ and SG ₁ ) by the Steiner minimum tree algorithm, and corresponding wiring candidate solutions are established for all the two-end nets, as shown in FIG. 3 ( b) shown.

Step S3: reducing the pre-wiring capacity in the initial wiring stage to half of the original capacity;

Step S4: judging whether the current wire nets at both ends meet the connectable conditions; if so, perform pre-connection and traverse all wire nets; otherwise, traverse all wire nets;

Step S5: After the traversal is completed, enter the main stage of wiring;

Step S6: find the most crowded area as the current wiring area;

Further, in this embodiment, after the initial wiring stage is completed, the approximate crowded situation of the chip can be obtained, and the most crowded area of the chip can be found from the initial wiring result. In this embodiment, the grid size of 2×2 in the overall wiring diagram is selected as the initial wiring sub-area of the main stage, and the most crowded area refers to the area of 2×2 grid size. The area with the most sums.

Step S7: adding the wire nets at both ends completely located in the current wiring area to the wiring set;

Step S8: By adding a new routing method and establishing an ILP model, the particle swarm optimization algorithm is used to solve the optimal solution in each routing area.

Further, in this embodiment, many routing algorithms are commonly used to solve the overall routing problem by using the ILP model, and a relatively good routing scheme can be obtained. The method based on the ILP model, first, find all possible wiring trees as candidate solutions, and calculate the cost of each wiring tree, establish the corresponding linear equation system with capacity constraints, and finally, solve the linear equation system to obtain the final population wiring scheme.

In this embodiment, the process of the particle swarm optimization algorithm for solving the wiring problem based on the ILP model is shown in Algorithm 1.

Specifically, as shown in Figure 12, Algorithm 1 is implemented according to the following steps:

Step S81: initialization;

Step S82: perform mutation operation on the particles in sequence; perform the cross operation between the particle and its historical optimal solution; perform the cross operation between the particle and the global optimal solution of the population; calculate the fitness function value of the particle;

Step S83: judging that the fitness value of the particle p is smaller than its historical optimal value; if so, the current particle is regarded as the historical optimal solution;

Step S84: Judging that the fitness value of the particle p is less than the global optimal value of the population; if so, take the current particle as the global optimal solution of the population; otherwise, go to step S85;

Step S85: determine whether the maximum number of populations is reached, if not, go to step S82; if so, add 1 to the current iteration number, and determine whether the maximum number of iterations is reached; if so, end, otherwise, go to step S82.

Step S9: judging whether the wire net corresponding to the optimal solution obtained based on the particle swarm optimization algorithm solution can be connected; if so, mark the wire net as connected, otherwise, mark it as unconnected;

Step S10: use the maze algorithm based on the new routing edge cost for routing;

Further, in this embodiment, after completing the routing based on particle swarm optimization in the current routing area, there will often be some unconnected nets at both ends in the routing scheme. To route these unconnected nets, and as an important step to finally route all nets. Labyrinth routing takes into account the line length and crowding balance on the basis of the cost of new routing edges, and performs routing of unconnected nets. The cost of new routing edges in GRG is calculated as shown in Algorithm 2. Based on the new routing edge cost, the maze routing is continuously performed for the unconnected nets until there are no unconnected nets. The specific maze algorithm is shown in Algorithm 3.

Specifically, in this embodiment, as shown in Figure 13, Algorithm 2 is implemented according to the following steps:

Step S1001: determine whether the edge e _i of the two-terminal wire net has been passed by other sub-wire nets after the original multi-terminal wire net has been decomposed; if so, go to step S1002; otherwise, go to step S1003;

Step S1002: Obtain the new wiring edge cost through the following assignment operation:

cost ( e _i )=0;

Step S1003: Obtain the new wiring edge cost through the following assignment operation:

cost ( e _i )= cost ( e _i )+ length ( e _i );

cost ( e _i )= cost ( e _i )+ cong ( e _i );

where: length is the length of edge e _i in GRG, cong is the crowding of edge e _i in GRG.

Specifically, in this embodiment, as shown in Figure 14, Algorithm 3 is implemented according to the following steps:

Step S1011: Input the remaining net set RN that has not been routed after PSO-based wiring:

Step S1012: Initialize each two end wire nets i in the RN;

Step S1013: determine whether the current net i at both ends is greater than the maximum number of nets in the RN; if it is greater, end, otherwise go to step S1014;

Step S1014: Execute: priority_queue Q; add a pin of the net i to Q, and mark the pin as the point to be expanded;

Step S1015: determine whether Q is empty; if not, add 1 to the current serial number of the net i at both ends, and go to step S1013; if so, go to step S1016;

Step S1016: expand and expand Q.top points along all wiring directions with the size of one unit grid;

Step S1017: judge whether the identification of the point is not expanded; if not, go to step S1015; otherwise, update and calculate the wiring cost of the net i;

Step S1018: determine whether the mark of the point is not expanded; if not, go to step S1015; otherwise, add the point to Q, and go to step S1015.

Step S11: Determine whether the wiring area can be expanded, if so, expand the wiring area according to the preset threshold, and go to the step S6; otherwise, go to the step S12;

Step S12: Based on the dynamic resource scheduling, and using the layer scheduling of the multi-layer wiring model, the overall wiring of the X-structure multi-layer is completed.

In this embodiment, the layer scheduling of the multi-layer wiring model: in the layer scheduling process, the edges with wiring directions of 0° and 90° are allocated to odd-numbered layers, while the even-numbered layers are allocated wiring directions of 45° and 135° side, as shown in Figure 4.

Further, in the present embodiment, the purpose of the present invention is to provide a method for constructing the overall wiring problem of the X structure in consideration of the multi-layer process requirements of the introduction and popularization of the X structure in the VLSI, so as to avoid overflow. The two most important performance indicators in the multi-layer overall wiring, the number and the total line length cost, are the optimization goals, and the optimization of these two most important goals in the multi-layer overall wiring is finally achieved.

Further, in this embodiment, four enhancement methods are proposed, including:

(1) Add a new type of wiring. Thus, it is helpful to give up the distribution rate of the nets at both ends of the connection in the main stage in the initial stage, and denote this method as E1. Considering that in the initial routing stage of XGRouter, for the two-pin wire nets with slope values of 0, -1, +1, and ∞ formed by the two pins after decomposition (this type of wire net collection is called NA), if If the straight line is used to directly connect the two pins, and the capacity of the connecting side will not be exceeded, the two ends of the wire nets are directly connected with the straight line. If the maximum capacity limit of the routing edge is exceeded, the link of these nets is abandoned and connected in the main stage. However, in the main stage of XGRouter, due to the inappropriate routing edge selection method, it is impossible for these nets to get the chance to connect in the main stage. Therefore, E1 is introduced in the design of FZU-Router, and the addition of a new type of routing method helps to abandon the routing ratio of the two ends of the connection in the main stage at the initial stage.

(2) The combination of particle swarm optimization algorithm and labyrinth routing based on new routing cost helps to complete the routing work with a higher routing rate for the set of unrouted nets in the current routing area, and this method is recorded as E2 . Considering that in the algorithm flow of XGRouter, the main stage has been using continuously expanding area wiring, and the post-processing stage uses labyrinth wiring to continue wiring the unfinished wire nets, which will cause the wire nets not to be wired before each expansion, and in the next expansion. After that, it still cannot be routed, so a lot of unrouted wire nets are accumulated, which greatly affects the solution quality of the adopted PSO algorithm. Therefore, E2 is introduced in the design of FZU-Router, and the labyrinth routing strategy based on the new routing cost is moved to the main stage. After each routing area is routed with PSO, it is helpful for the collection of unrouted nets in the current routing area. The wiring work is done with a higher routing rate.

(3) The strategy of reducing the pre-wiring capacity in the initial stage enables part of the network to remain in the PSO algorithm in the main stage for wiring, making full use of the global optimization capability of the PSO algorithm, and further enhancing the optimization effect of the two strategies E1 and E2. And this method is denoted as E3. Considering that in the algorithm process of XGRouter, since the initial stage adopts the greedy idea for the network set NA, connecting with the shortest connection length and occupying the least wiring resources, it is easy to fall into some locally optimal solutions, while the main stage The PSO algorithm with global optimization capability is used to route the wire nets at both ends from a more overall resource perspective, which has a stronger global optimization capability. Therefore, the E3 strategy is introduced in the design of FZU-Router, which reduces the pre-wiring capacity of the initial wiring stage to half of the original capacity, so that some nets can be left in the PSO algorithm in the main stage for wiring, making full use of the global PSO algorithm. Optimization capabilities, while further strengthening the optimization effect of E1 and E2.

(4) Design a dynamic resource scheduling strategy, and introduce a multi-layer wiring model and layer scheduling strategy, thereby constructing a high-performance X-structure multi-layer overall router FZU-Router, which eventually overflows the number and line in the multi-layer wiring problem. The two most important indicators of long total cost bring significant optimization effects, and this method is recorded as E4. Considering that in the algorithm flow of XGRouter, the capacity of each wiring edge is constant, and the capacity is static during the wiring process, which may cause some wiring edges to be underutilized and in a sparse state, and some wiring edges are overused. while being crowded. In the design of FZU-Router, E4 is introduced, and the routing resources are dynamically adjusted in the routing process to make more full use of routing resources for routing, and further optimize the overall router's optimization capabilities in terms of overflow number and total wire length cost. .

Further, in this embodiment, in the initial wiring stage of XGRouter, for the two-pin wire nets with slope values of 0, -1, +1 and ∞ formed by the two pins after decomposition (this kind of wire nets) The set is called NA). If the straight line is used to directly connect the two pins and the capacity of the connecting edge will not be exceeded, then the straight line is used to directly connect the nets at both ends. As shown in Figure 5, the four types of wire net pin distributions at both ends of the direct connection can be considered, including four cases where the included angles between the two pins are 0 ⁰ , 45 ⁰ , 90 ⁰ and 135 ⁰ . If the straight line is used to directly connect the two pins, it will cause congestion and overflow, then abandon the direct connection of the two ends of the network that will cause overflow (this type of network collection is called NC), but connect it in the main stage. . As shown in Figure 6, if the wire nets at both ends that can be directly connected in Figure 5 are in the crowded area of the gray rectangle (that is, passing another wire in the gray rectangle area will cause overflow, which will seriously affect the routability of the chip) at the initial stage The stage fails to connect, XGRouter puts it in the main stage to connect, but the connection method still adopts the connection edge method as shown in Figure 5, resulting in these wire nets that were abandoned in the initial stage, still cannot be connected in the main stage, resulting in excessive There are many wire nets at both ends that are not connected, which greatly affects the solving performance of the PSO algorithm in the main stage.

Therefore, in this embodiment, in the main stage of the router FZU-Router, for the wire net set NC, the present invention provides a new type of routing method, so that these wire nets in the NC can be as much as possible in the main stage. Complete the wiring. These new types of wiring edge connection methods used in E1, as shown in Figure 7, for the horizontal or vertical relationship between the two ends of the wire net (N1) use Figure 7 (a) and 7 (b) two connection methods, respectively The 450-side and ¹³⁵⁰ -side alternate connection mode and ⁴⁵⁰ -side, ^{1350 -} side and horizontal or vertical side are alternately connected, wherein the pin of N1 in Fig. The pins of N1 span the odd-numbered grids; while the nets (N2) ^at both ends of the 450 or ¹³⁵⁰ relationship are connected as shown in Figure 7(c), that is, the horizontal and vertical sides are alternately connected. With the newly added three candidate wiring methods in FIGS. 7( a ) to 7 ( c ), there is a greater possibility that the main stage can reasonably avoid crowded areas.

Further, in this embodiment, based on the standard test circuit of ISPD07, the overall wiring results of the number of overflows (TOF) and the total line length cost (TWL) are compared without using and using E1, as shown in Table 1. . The overall wiring results with E1 versus without E1 (represented by E0 in the table) achieved a 16.63% reduction rate in the number of overflows, indicating that the improved strategy of E1 helps to connect as many ends as possible in the main stage that were abandoned by the initial wiring The net gathers NC to improve the distribution rate, so as to reduce the overflow as much as possible. Although it adds a small amount of wire length total cost, it brings considerable optimization for the most important optimization objective in the overall routing problem of multiple layers, the overflow number, which shows the effectiveness and necessity of E1.

Table 1 Comparison of wiring results without and with E1 strategy

Further, in this embodiment, after the FZU-Router adopts E2, the labyrinth routing strategy based on the new routing cost is moved to the main stage. After each time the PSO is used for routing in the box area, it is helpful for the current box not to be routed to the network. Aggregates perform routing work at higher routing rates.

In the algorithm flow of XGRouter, the main stage has been using the continuous expansion area wiring, and the post-processing stage uses the labyrinth wiring to continue the wiring of the unfinished wire nets, which will cause the wire nets not to be routed before each expansion, and still remain after the next expansion. It cannot be routed, so a lot of unrouted wire nets are accumulated, which greatly affects the solution quality of the PSO algorithm used. As shown in Figure 8, in XGRouter, P1 and P2 are in the box0 stage. Due to the existence of the gray crowded area, P1 and P2 can not complete the wiring in the box0 stage when using the XGRouter's edge connection method. And if you wait until Box expands to the entire chip, P1 and P2 may be connected by solid lines as shown in Figure 8, which may lead to excessively long windings, pay the total cost of excessive line length, and occupy more of routing resources, resulting in an increase in the number of overflows. In FZU-Router, the wiring scheme is ready to introduce labyrinth wiring immediately after the end of box0 to complete the wire net that PSO failed to complete the wiring, so that P1 and P2 can be connected by the dotted line as shown in Figure 8. Occupy the resources near box0, instead of waiting for all the expansion, the resources near box0 have been occupied. Using the E2 improvement strategy can effectively reduce the redundant occupation of wiring resources, thereby reducing the number of overflows and further improving the completion rate of wiring.

Table 2 Comparison of wiring results without and with E2 strategy

Further, the overall wiring results without and with the E2 improvement strategy are compared, as shown in Table 2. Compared with the overall wiring results without using the E2 strategy, a 77.01% reduction rate was achieved in the number of overflows, indicating that the improved strategy of E2 helps to use the wiring resources near the wire net as early as possible in the main stage, and more Effectively connect the wire nets at both ends to improve the distribution rate, so as to reduce the overflow as much as possible. Although a small amount of total line length cost (0.81% of the total line length cost) is paid, the most important optimization objective in the overall multi-layer routing problem, the overflow number, brings a large optimization, which shows that the E2 strategy is as effective as possible. Effectiveness and necessity of rational use of wiring resources.

Further, in this embodiment, the FZU-Router reduces the pre-wiring capacity of the initial wiring stage to half of the original capacity, so that part of the network can be left in the PSO algorithm in the main stage for wiring, making full use of the global optimization capability of the PSO algorithm. , and further strengthen the optimization effect of E1 and E2 strategies.

Since the initial stage adopts the greedy idea for the network set NA, connecting with the shortest connection length and occupying the least wiring resources, it is easy to fall into some local optimal solutions, while the main stage adopts the PSO algorithm with global optimization ability from the From a more overall resource perspective, wire nets at both ends are routed, which has stronger global optimization capabilities. In the XGRouter overall router, the initial routing algorithm of the greedy strategy is applied to all the wire nets at both ends that can be routed, so that the initial routing scheme falls into a more serious local optimal solution. Therefore, the new generation of multi-layer overall router FZU-Router adopts E3, and the pre-wiring capacity in the initial wiring stage is reduced to half of the original capacity, and some wiring resources and some wire nets at both ends are reserved for those with stronger global optimization capabilities. The PSO algorithm performs routing, so that the global optimization ability of the PSO algorithm can be fully utilized, and the optimization ability of the FZU-Router is improved.

As shown in Figures 9(a) and 9(b), the pre-wiring capacity reduction strategy is not adopted in the initial wiring stage in XGRouter, assuming that the wiring sequence of the nets at both ends in the initial wiring is N1 (including two pins N11 and N12) , N2 (including two pins N21 and N22), N3 (including two pins N31 and N32), here it is assumed that the maximum capacity of the wiring side is 2. The wiring strategy of XGRouter is adopted, that is, N1 and N2 are connected preferentially, while in the main stage, N3 needs to occupy a lot of wiring resources and the total cost of wire length is very wasteful, as shown in Figure 9(a). However, if the E3 improvement strategy of FZU-Router is adopted, half of the wiring resources are reserved. Therefore, after adopting the E3 strategy, the initial wiring is only connected to the N1 wire net, while the N2 and N3 wire nets are left in the PSO algorithm in the main stage. Trying to solve it, the PSO algorithm can measure the wiring mode of the N2 and N3 nets from a more global perspective, so as to obtain the solution as shown in Figure 9(b). It can be seen from this that the connection method shown in Figure 9(b) greatly reduces the occupation of unnecessary wiring resources, and completes the connection of the three nets N1, N2, and N3 with less wiring resources.

Further, in order to further expand the advantages of the E1 improvement strategy, the E3 improvement strategy is added, which helps to improve the optimization ability of the new generation overall router FZU-Router for the total cost of online length, and at the same time enhances the ability to reduce the number of overflows. In the initial routing phase, the channel capacity in the horizontal and vertical directions is limited to 1/2 of the set capacity. After adding the E3 improvement strategy, the number of nets at both ends of the wiring completed by the E1 improvement strategy is greatly increased, and the advantages of the PSO algorithm are also fully utilized, which will achieve better optimization results and further reflect the advantages of E1.

Further, as shown in Table 3, adding the initial wiring capacity setting of the E3 strategy on the basis of the E1 strategy can achieve a good optimization effect of 17.27% and 1.27% in terms of total overflow and total line length cost, respectively. As shown in Table 4, adding the initial wiring capacity setting of the E3 strategy on the basis of the E2 strategy can achieve a certain optimization effect of 0.02% and 0.39% in the total overflow and total line length cost, respectively. As shown in Table 5, adding the initial wiring capacity setting of the E3 strategy on the basis of the E1 and E2 strategies can achieve 1.38% and 1.45% optimization effects in terms of total overflow and total line length cost, respectively. To sum up, it can be shown that the introduction of E3 strategy is effective, especially for E1 strategy, E3 is particularly effective.

Table 3 Comparison of the wiring results of the E1 strategy without and with the E3 strategy

Table 4 Comparison of the wiring results of no and E3 strategies based on the E2 strategy

Table 5 Comparison of the results of not adopting and adopting E3 strategy on the basis of the combined effect of E1 and E2 strategies

Further, in this embodiment, if there is a capacity sharing the same channel wiring area between the horizontal side or the vertical side and the diagonal side, the two sides have channel capacity correlation.

It forms an angle of 45 degrees with the horizontal side and is located above the horizontal side, and the side whose left endpoints meet is related to the channel capacity of the horizontal side and shares the channel capacity of the specified horizontal side; it forms an angle of 45 degrees with the vertical side and is located in the channel capacity of the horizontal side. The side on the right side of the vertical side, and the side whose lower endpoints are congruent is related to the channel capacity of the vertical side, and shares the specified channel capacity of the vertical side. Under this provision, it is necessary to satisfy:

(1)

(1)

where C _l represents the channel capacity of the horizontal or vertical side, Cx represents the channel capacity of the diagonal side with a channel capacity correlation with the horizontal or vertical side, and _{Cs represents} the total channel routing capacity of the area . In this embodiment, the channel is the wiring edge, and the channel capacity is the wiring resource.

As shown in Figure 10, the channel routing capacity of AB and AD is given, AC and AB share the channel routing capacity of AB, AE and AD share the channel routing capacity of AD, that is, AC and AB have channel capacity correlation, AE and AD has channel capacity correlation.

Further, in this embodiment, after the overall wiring of part of the network is completed, by redistributing wiring resources to two types of wiring edges with channel capacity correlation, the channel capacity is concentrated to the channels with dense wiring, and each channel The remaining capacity of the channel exceeds an expected value as much as possible, which is beneficial to the subsequent wiring, that is, the dynamic allocation of channel capacity.

Further, in this embodiment, after the channel capacity is dynamically allocated as a routing resource, it is expected that the remaining routing capacity of two types of routing edges with channel capacity correlation can exceed a fixed value, that is, the dynamic allocation threshold of the channel capacity is set. .

Further, in this embodiment, after the overall wiring of part of the wire nets is completed, the remaining channel capacity does not exceed the channel capacity dynamic allocation threshold of the channel.

Further, in this embodiment, after the overall wiring of part of the nets is completed, a channel whose remaining channel capacity exceeds the sum of the dynamic allocation threshold of channel capacity and the amount of dynamic allocation of channel capacity is used as a sparse channel.

Further, in this embodiment, in the case of sparse channels and crowded channels with channel capacity correlation, under the condition that the specified total channel capacity is kept unchanged, dynamic allocation of channel capacity is used, and the channel capacity obtained by the two channels is It tends to adapt to the wiring requirements of the target network, which can make the subsequent wiring have a larger selection space, avoid the situation that the subsequent wiring needs to be detoured in some crowded areas, and can effectively reduce the overflow number of the final wiring result and the total cost of the line length. Shorten the running time of the algorithm.

Further, in this embodiment, the overflow phenomenon occurs because, on the premise that the number of wirings per channel does not exceed the channel capacity of the channel, an interconnectable path cannot be found between the two points of the wire nets at both ends of the target, That is, at least one channel between two points is blocked. If the blocked channel can be unblocked, an interconnectable path can be found between the two points. During the execution of the routing algorithm, the absolute uniformity of the wire net cannot be guaranteed, so there are channels with a lot of remaining capacity and channels with little remaining capacity in the entire routing area. At the same time, according to the wiring requirements, the total capacity between the channels related to the channel capacity only needs to meet the regulations, and there is no requirement for the allocation of capacity between the two channels. To sum up, using the dynamic allocation of channel capacity among the channels related to the channel capacity can unclog the blocked channels to the greatest extent, and can reduce the probability that the interconnection lines of the two ends of the network are blocked, and reduce the risk of the channel being blocked.

Therefore, it is difficult to predict whether a certain channel will be used in the routing process in the optimization process of the PSO algorithm. For the channel capacity-related channels that will not be used during the routing process and the channel capacity-related channels that are being routed, the effect of dynamic channel capacity allocation is difficult to guarantee. In order to avoid the impact of invalid work on the routing quality, after each box expansion , PSO wiring scheme has been determined, in the process of line network connection, it is most appropriate to test the feasibility of dynamic allocation of channel capacity for the connected channels one by one and to perform dynamic allocation of channel capacity for the required channels.

Further, in this embodiment, to achieve the purpose of dynamic allocation of channel capacity, dynamic allocation of channel capacity may be performed between sparse channels and congested channels that are channels related to each other in channel capacity.

There are two channels that are channel capacity related channels to each other. If one of the channels is a non-sparse and non-congested channel, if the remaining capacity is allocated according to the dynamic allocation of channel capacity, it becomes a congested channel, and its remaining capacity exceeds the dynamic allocation threshold of channel capacity, so it is not necessary to obtain channel capacity allocation. So dynamic allocation of channel capacity is meaningless. If both channels are congested channels, the purpose of dynamic allocation of channel capacity will never be achieved. If both channels are sparse channels, dynamic allocation of channel capacity is also meaningless. To sum up, to achieve the purpose of dynamic allocation of channel capacity, dynamic allocation of channel capacity can be performed between sparse channels and crowded channels that are related to each other in channel capacity.

Figure 11(a) shows the situation after the current part of the wiring is completed, in which the red broken line ABCD represents the wiring scheme selected by the PSO algorithm in the main stage, the channel identified by the blue line segment and the channel identified by the red line segment are the channel capacity-related channels. The number near it is the remaining capacity of the channel. At this time, the net connection of the main stage PSO algorithm routing scheme has not been performed. In the wiring scheme ABCD, the remaining capacities of channels AB, BC, and CD are 2, 4, and 3, respectively, and the channels that are related to each other's channel capacity are AE, BF, and CG, respectively, and the remaining remaining capacities are 3, 7, and 5, respectively.

Further, the dynamic allocation threshold of channel capacity is set to 2, and the resource allocation quota is set to 2. At this time, the main stage PSO algorithm selects the wiring scheme and starts the connection as shown in Figure 11(b), first connect AB, the remaining channel capacity of AB becomes 1, which is less than the threshold 2, which is a crowded channel, but its channel capacity The remaining capacity of the relevant channel AE is less than 4, it is not a sparse channel, and the conditions for dynamic channel capacity allocation are not met, and resource allocation is not performed. Reconnect to BC. The remaining channel capacity of BC is 3. If it exceeds 2, it is a non-congested channel. If the condition for dynamic channel capacity allocation is not met, resource allocation will not be performed. Finally, connect CD, the remaining channel capacity of CD is 2, if it does not exceed 2, it is a congested channel, and its channel capacity-related channel CG remaining capacity is 5, if it is greater than 4, it is a sparse channel, which satisfies the condition of dynamic allocation of channel capacity, then CG allocation 2 channel capacity for CD. Finally, the remaining capacity of CD becomes 4, and the remaining capacity of CG becomes 3, all of which are above the given channel capacity dynamic allocation threshold of 2, which is beneficial to subsequent wiring.

Table 6 Comparison of wiring results without and with E4

Further, through experiments, it is found that when the dynamic allocation threshold of channel capacity is too large, resources will be wasted, and if it is too small, it is difficult to meet the needs of resource allocation. When the dynamic allocation threshold of channel capacity is 2, the optimal result is obtained. When the amount allocated each time by the dynamic allocation of channel capacity is too large, the capacity allocation between the channels related to the channel capacity will be repeated, which will not only increase the time overhead of the algorithm, but also make the capacity of each channel difficult to adapt to the needs of wiring, and the wiring effect will change. Poor; when the amount allocated each time by the dynamic allocation of channel capacity is too small, the capacity obtained by the channel that needs to obtain capacity allocation is limited, and the improvement in time and wiring results is not ideal. Finally, it is found that when the channel capacity is dynamically allocated with a quota of 2 each time, the optimal wiring result will be obtained, and the time will also be greatly improved.

Finally, the dynamic allocation threshold of channel capacity is 2 and the quota for each allocation is 2 as the parameters of E4. In order to further verify the effectiveness of the E4 strategy, the present invention compares the overall wiring results of not adopting and adopting the E4 strategy. The specific comparison results are shown in Table 6. From Table 6, it can be seen that the algorithm using E4 has achieved 2.17% and 2.8% optimization effects in terms of total overflow and total line length cost, respectively, compared with the algorithm without E4. At the same time, the algorithm using E4 achieves a time speedup of 1.38 times in terms of CPU time compared to the algorithm not using E4. To sum up, it shows that the dynamic resource adjustment strategy is adopted, that is, the E4 strategy can achieve good optimization capabilities in three aspects: total overflow, total line length cost, and CPU time, which further illustrates the effectiveness and necessity of the E4 strategy.

Further, in this embodiment, in order for those skilled in the art to further understand the technical solution proposed by the present invention, the following is further described with reference to specific examples.

In order to verify the effectiveness of the method of the present invention in solving the multi-layer wiring problem, the method of the present invention and document [1]: Moffitt MD. Maizerouter: Engineering an effective global router. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(11): 2017–2026. And reference [2]: Chang YJ, Lee YT, Gao JR, et al. NTHU-Route2.0: A robust global router for modern designs. IEEE Transactions onComputer-Aided Design of The two serial overall routing algorithms proposed in Integrated Circuits and Systems, 2010, 29(12): 1931-1944. are experimentally compared on the ISPD07 benchmark circuit. These rectangular overall routing serial algorithms are based on the Manhattan structure and are all tested on the ISPD07 benchmark circuit, and the corresponding experimental results are given in Table 7. It can be seen from Table 7 that the method of the present invention achieves 23.94% and 11.40% of the optimization effects in terms of overflow number compared to the two algorithms in Reference [1] and Reference [2], especially compared to Reference [1] in Test Example 16 100% overflow reduction rate can be achieved on the test case, which can be optimized to no overflow. At the same time, the overflow reduction rate of 91.5% and 91.2% was achieved in test example 18, which effectively improved the chip's routability and reliability. manufacturability. Compared with the two algorithms in literature [1] and literature [2], the method of the present invention achieves a reduction rate of 22.26% and 17.17% of the total wiring cost, respectively, in terms of bus length. Especially compared to the literature [1], the bus length reduction rate of 34.17% can be achieved on the test example 16. The reasons why the method of the present invention can effectively reduce the number of overflows and the bus length compared with other serial algorithms include: because the method of the present invention introduces the X structure and performs overall wiring from a global perspective, the method of the present invention has relatively stronger line length optimization capabilities. , and can better overcome the dependence of these serial algorithms on the wiring order of the net, thereby effectively reducing congestion and overflow.

Table 7 Comparison of overall routing algorithms on ISPD07 with two serial algorithms

In order to further verify the effectiveness of the method of the present invention on the ISPD07 reference circuit, the method of the present invention is compared with the literature [3]: Cho M, Lu K, Yuan K, et al. Boxrouter 2.0: A hybrid and robust globalrouter with layer assignment for routability . ACM Transactions on DesignAutomation of Electronic Systems, 2009, 14(2): 1–21. and reference [4]: Roy AJ, MarkovIL. High-performance routing at the nanometer scale. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(6): 1066–1077. Two overall routing parallel algorithms are compared, and Table 8 gives the corresponding experimental results. It can be seen from Table 8 that the method of the present invention achieves 24.11% and 24.15% of the optimization effects in terms of overflow numbers compared with the two algorithms in literature [3] and [4], especially compared to literature [3] and [4]. Test instance 16 can achieve a 100% overflow reduction rate, which can be optimized to no overflow. At the same time, in test instance 18, a 92.9% and 93.18% overflow reduction rate can be achieved, which effectively improves the chip's deployability. flexibility and manufacturability. Compared with the two algorithms in the literature [3] and [4], the method of the present invention achieves a reduction rate of 20.24% and 16.33% of the total wiring cost in terms of bus length, respectively. Especially compared to the literature [3], the bus length reduction rate of 33.66% can be achieved on the test example 16.

Further, in this embodiment, the reasons why the method of the present invention can effectively reduce the number of overflows and the bus length compared with other parallel algorithms include: (1) FZU-Router introduces the X structure, which can obtain less bus length than the Manhattan structure. ; (2) FZU-Router uses the improved PSO algorithm to solve the FX-ILP model, which can solve the situation that the random rounding method is used to solve the ILP model that is prone to deviation, thus ultimately bringing about the optimization of the bus length. At the same time, the original design of FZU-Router is to further optimize the number of overflows, and secondly to optimize the total cost of the line length, which is consistent with the performance requirements of the multi-layer overall wiring, and can solve the multi-layer overall wiring problem more efficiently and with higher quality.

Table 8 Comparison of overall routing algorithms with two parallel algorithms on ISPD07

The above are the preferred embodiments of the present invention, all changes made according to the technical solutions of the present invention, when the resulting functional effects do not exceed the scope of the technical solutions of the present invention, belong to the protection scope of the present invention.

Claims (5)

1. A multilayer overall wiring method of a high-performance X structure in a very large scale integrated circuit is characterized by comprising the following steps:

step S1: in the initial wiring stage, establishing an X-structure Steiner minimum tree;

step S2: carrying out multi-terminal wire mesh decomposition;

step S3: reducing the pre-wiring capacity of the initial wiring stage to half of the original capacity;

step S4: judging whether the current two-end wire nets meet the connectable conditions or not; if yes, performing pre-connection, and traversing all the nets; otherwise, traversing all the nets;

step S5: after traversing, entering a wiring main stage;

step S6: searching a most crowded area as a current wiring area;

step S7: adding the two-end nets completely positioned in the current wiring area into a wiring set;

step S8: an ILP model is established through a newly added wiring mode, and an optimal solution is solved in a wiring area each time by adopting a particle swarm optimization algorithm;

step S9: judging whether the net corresponding to the optimal solution obtained by solving based on the particle swarm optimization algorithm can be connected or not; if yes, marking the net as connected, otherwise, marking the net as unconnected;

step S10: wiring by adopting a maze algorithm based on the cost of a new wiring edge;

step S11: judging whether the wiring region is expandable, if so, expanding the wiring region according to a preset threshold, and turning to the step S7; otherwise, go to step S12;

step S12: based on dynamic resource scheduling, adopting layer scheduling of a multilayer wiring model to complete multilayer overall wiring of the X structure;

in the step S12, the dynamic resource scheduling includes: for a sparse channel and a crowded channel with channel capacity correlation, under the condition that the total channel capacity is not changed, by setting a channel capacity dynamic allocation threshold and a resource allocation quota and adopting channel capacity dynamic allocation, the channel capacity obtained by dividing the two channels tends to adapt to the wiring requirement of a target network.

2. The method as claimed in claim 1, wherein in step S8, the adding routing method includes: for the included angle of the pins of the wire nets at two ends of the direct connection wire is 0 degree, 45 degrees, 90 degrees or 135 degrees, the connection is carried out in the following way:

the first method is as follows: 45⁰Edge sum 135⁰The edges are alternately connected;

the second method comprises the following steps: 45⁰Edge 135⁰Sides and horizontal sides or vertical sides are alternately connected;

the third method comprises the following steps: the horizontal and vertical sides are alternately connected.

3. The method of claim 1, wherein the dynamic allocation of channel capacity is performed for a channel of interest based on a test of the feasibility of dynamic allocation of channel capacity for each connection.

4. The very large scale integrated circuit high performance X-fabric multilayer population routing method of claim 1, wherein channel capacity is dynamically allocated between sparse channels and congested channels that are channels of channel capacity relative to each other.

5. The method as claimed in claim 1, wherein the dynamic channel capacity allocation threshold is 2 and the resource allocation quota is 2.

Images