CN107832519B - Multilayer overall wiring method for high-performance X structure in ultra-large scale integrated circuit - Google Patents
Multilayer overall wiring method for high-performance X structure in ultra-large scale integrated circuit Download PDFInfo
- Publication number
- CN107832519B CN107832519B CN201711060869.5A CN201711060869A CN107832519B CN 107832519 B CN107832519 B CN 107832519B CN 201711060869 A CN201711060869 A CN 201711060869A CN 107832519 B CN107832519 B CN 107832519B
- Authority
- CN
- China
- Prior art keywords
- wiring
- routing
- capacity
- channel
- channel capacity
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 60
- 238000005457 optimization Methods 0.000 claims abstract description 55
- 238000012360 testing method Methods 0.000 claims abstract description 11
- 239000002245 particle Substances 0.000 claims description 18
- 238000013468 resource allocation Methods 0.000 claims description 8
- 238000000354 decomposition reaction Methods 0.000 claims description 6
- 239000004744 fabric Substances 0.000 claims 1
- 230000000694 effects Effects 0.000 abstract description 17
- 230000009467 reduction Effects 0.000 abstract description 16
- 238000004088 simulation Methods 0.000 abstract description 2
- 239000010410 layer Substances 0.000 description 21
- 238000010586 diagram Methods 0.000 description 18
- 238000013461 design Methods 0.000 description 17
- 230000008569 process Effects 0.000 description 13
- 230000006872 improvement Effects 0.000 description 10
- 238000011160 research Methods 0.000 description 9
- 238000009826 distribution Methods 0.000 description 8
- 230000001965 increasing effect Effects 0.000 description 7
- 230000009286 beneficial effect Effects 0.000 description 3
- 238000010276 construction Methods 0.000 description 3
- PCTMTFRHKVHKIS-BMFZQQSSSA-N (1s,3r,4e,6e,8e,10e,12e,14e,16e,18s,19r,20r,21s,25r,27r,30r,31r,33s,35r,37s,38r)-3-[(2r,3s,4s,5s,6r)-4-amino-3,5-dihydroxy-6-methyloxan-2-yl]oxy-19,25,27,30,31,33,35,37-octahydroxy-18,20,21-trimethyl-23-oxo-22,39-dioxabicyclo[33.3.1]nonatriaconta-4,6,8,10 Chemical compound C1C=C2C[C@@H](OS(O)(=O)=O)CC[C@]2(C)[C@@H]2[C@@H]1[C@@H]1CC[C@H]([C@H](C)CCCC(C)C)[C@@]1(C)CC2.O[C@H]1[C@@H](N)[C@H](O)[C@@H](C)O[C@H]1O[C@H]1/C=C/C=C/C=C/C=C/C=C/C=C/C=C/[C@H](C)[C@@H](O)[C@@H](C)[C@H](C)OC(=O)C[C@H](O)C[C@H](O)CC[C@@H](O)[C@H](O)C[C@H](O)C[C@](O)(C[C@H](O)[C@H]2C(O)=O)O[C@H]2C1 PCTMTFRHKVHKIS-BMFZQQSSSA-N 0.000 description 2
- 230000000903 blocking effect Effects 0.000 description 2
- 230000007547 defect Effects 0.000 description 2
- 230000002708 enhancing effect Effects 0.000 description 2
- 238000012805 post-processing Methods 0.000 description 2
- 238000010187 selection method Methods 0.000 description 2
- 239000002356 single layer Substances 0.000 description 2
- 230000003068 static effect Effects 0.000 description 2
- 240000008042 Zea mays Species 0.000 description 1
- 235000016383 Zea mays subsp huehuetenangensis Nutrition 0.000 description 1
- 235000002017 Zea mays subsp mays Nutrition 0.000 description 1
- 230000001133 acceleration Effects 0.000 description 1
- 238000013459 approach Methods 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 230000000052 comparative effect Effects 0.000 description 1
- 238000011960 computer-aided design Methods 0.000 description 1
- 238000002474 experimental method Methods 0.000 description 1
- 230000010354 integration Effects 0.000 description 1
- 235000009973 maize Nutrition 0.000 description 1
- 239000002184 metal Substances 0.000 description 1
- 230000035772 mutation Effects 0.000 description 1
- 230000037361 pathway Effects 0.000 description 1
- 230000003334 potential effect Effects 0.000 description 1
- 239000004065 semiconductor Substances 0.000 description 1
- 238000005728 strengthening Methods 0.000 description 1
- 238000012795 verification Methods 0.000 description 1
- 239000002699 waste material Substances 0.000 description 1
- 238000004804 winding Methods 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/39—Circuit design at the physical level
- G06F30/392—Floor-planning or layout, e.g. partitioning or placement
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2111/00—Details relating to CAD techniques
- G06F2111/04—Constraint-based CAD
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2111/00—Details relating to CAD techniques
- G06F2111/06—Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Architecture (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
The invention relates to a multilayer overall wiring method of a high-performance X structure in a very large scale integrated circuit, which comprises the following steps on the basis of an XGROUTER router: adding a new type of wiring mode, combining a subgroup optimization algorithm with maze wiring based on new wiring cost, designing a dynamic resource scheduling strategy by using a reduction strategy of pre-wiring capacity in an initial stage, introducing a multilayer wiring model, simplifying an integer linear programming model of XGROUTER, and finally constructing a high-performance X-structure multilayer overall wiring unit. Simulation experiment results of a standard test circuit show that the optimal effect is achieved on two indexes, namely overflow number and total wire length cost, which are the most important optimization targets in multilayer overall wiring compared with other various overall wiring devices.
Description
Technical Field
The invention relates to the technical field of computer aided design of integrated circuits, in particular to a multilayer overall wiring method for a high-performance X structure in a very large scale integrated circuit.
Background
As the sizes of semiconductors and interconnection lines are continuously reduced, the interconnection lines seriously affect many critical design indexes, and thus, the wiring stage as the actual routing position of the interconnection lines becomes particularly important in the VLSI (very large scale integration) physical design of the present day. The complex wiring process is composed of two stages of general wiring and detailed wiring. In the overall wiring, the routing of each net is distributed to each channel wiring area, and the wiring problem of each channel area is clearly defined. While the detailed routing gives the specific location of each net in the channel region. Therefore, the quality of the overall wiring seriously affects the success rate of the detailed wiring, thereby playing a decisive role in the performance of the whole chip.
Global routing is an important part of the physical design of very large scale integrated circuits, so that researchers have proposed many effective algorithms and global routing techniques, which can be mainly divided into serial algorithms and parallel algorithms, and particularly, the global routing method represented by the serial algorithm can deal with large scale problems. But the serial algorithm has a serious dependency on the definition of the wiring order or wiring cost of the nets, and this potential property seriously affects the quality of the overall wiring. And the parallel algorithm represented by integer linear programming can reduce the dependency of the wiring result on the sequence of the net, and obtain a total wiring scheme with better quality. In the partial methods represented by the integer linear programming, the integer linear programming model is firstly relaxed into the linear programming model to reduce the time complexity of the programming model solving, and then the linear solution is converted into the nonlinear solution by using the random rounding method, so that the wiring scheme obtained in the random rounding process may seriously deviate from the real solution scheme.
Most of the overall wiring algorithms are related work based on a Manhattan structure as a model, and when the optimization strategy based on the Manhattan structure is used for optimizing the length of an interconnection line, the wiring direction can only be horizontal and vertical, so that the optimization capability is limited. Therefore, it is necessary to change the conventional manhattan structure from the basic point of view, so researchers have tried to perform wiring based on the non-manhattan structure to optimize the overall performance of the chip. Researchers have developed researches on non-Manhattan structures which can bring about considerable reduction of wire length and other physical design indexes, and particularly, special industrial alliance popularization X structures appear, so that realization and verification bases are provided for the researches. The current research on X-structure wiring mainly includes two aspects: the construction of the X-structure wiring tree and the design of the X-structure overall wiring algorithm. With the introduction of the X-structure, the routing algorithm design becomes more complex. However, some researches on the overall wiring of the X structure mainly focus on the optimization of the wire length, and the algorithms are based on the early Steiner tree construction method, so that the optimization effect of the overall wiring algorithm of the X structure relative to the overall wiring algorithm of the manhattan structure is not obvious, and even the partially-operated wiring result is worse than the wiring result of the manhattan structure in the optimization capability of the total cost of the wire length.
As integrated circuit design enters the nanometer field, the number of layers of wiring metal is increased, the line width is greatly reduced, and the wiring distance is also greatly reduced, so that the performance and density of the circuit are greatly improved, therefore, multilayer wiring is produced at the same time, and the attention of a plurality of research organizations is attracted. However, the conventional research on the overall wiring problem of the non-manhattan structure is only limited to the research on the overall wiring problem of the single-layer structure, and as far as we know, the research on the overall wiring algorithm considering two conditions of the non-manhattan structure and the multi-layer structure is not carried out.
Disclosure of Invention
The invention aims to provide a multilayer overall wiring method of a high-performance X structure in a very large scale integrated circuit, which overcomes the defects in the prior art.
In order to achieve the purpose, the technical scheme of the invention is as follows: a multilayer overall wiring method of a high-performance X structure in a very large scale integrated circuit comprises 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: and based on dynamic resource scheduling, adopting layer scheduling of a multilayer wiring model to finish the X-structure multilayer overall wiring.
In an embodiment of the present invention, in the step S8, the new type of routing manner 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: 450Edge sum 1350The edges are alternately connected;
the second method comprises the following steps: 450Edge 1350Sides and horizontal sides or vertical sides are alternately connected;
the third method comprises the following steps: 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 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.
In an embodiment of the present invention, the channel capacity dynamic allocation is performed on the required channel based on testing the feasibility of dynamic allocation of the channel capacity of each connection one by one.
In an embodiment of the present invention, channel capacity is dynamically allocated between a sparse channel and a congested channel of channels that are related to each other.
In an embodiment of the present invention, the dynamic channel capacity allocation threshold is 2, and the resource allocation quota is 2.
Compared with the prior art, the invention has the following beneficial effects:
(1) compared with the XGRouter, the main-stage wiring of the new wiring device introduces a new type of wiring mode and labyrinth wiring based on new wiring cost, and is combined to be solved by adopting a PSO algorithm, the new type of wiring mode is increased, so that the wiring rate of two-end nets which are abandoned to be connected in the initial stage in the main stage is improved, and meanwhile, after a labyrinth wiring strategy is moved to the main stage in each box area and the PSO is adopted for wiring, the wiring work of a set of unmachined nets in the current box area can be completed at a higher wiring rate.
(2) Compared with the XGRouter, the initial wiring of the new wiring device reduces the pre-wiring capacity of the initial wiring stage to half of the original capacity, so that part of the wire nets and wiring resources can be left in the main stage for wiring, the global optimization capability of the PSO algorithm is more fully utilized, and meanwhile, the new type of wiring mode and the maze wiring based on the new wiring cost are further enhanced and are combined to be solved by adopting the PSO algorithm.
(3) Since the capacity of each routing edge in the XGRouter is constant and the capacity is static during routing, there is a possibility that a part of the routing edges is used less and in a sparse state and a part of the routing edges is used too much and in a crowded state. A dynamic resource scheduling strategy is introduced into the design of the high-performance X-structure multilayer overall Router FZU-Router, and the routing resources are dynamically adjusted in the routing process, so that the routing resources are more fully utilized for routing, the optimization capability of the overall Router in the aspects of overflow number and total wire length cost is further improved, and the optimization capability is optimal.
(4) The high-performance X-structure multilayer overall Router FZU-Router constructed by the invention is used for solving the multilayer overall routing problem, and the layer allocation strategy adopts an optimal multilayer routing model verified in the previous work, and allocates the segments of the related nets to the appropriate routing layers in the layer allocation stage.
Drawings
FIG. 1 is a flow chart of a high performance X-structure multi-layer global wiring method in a very large scale integrated circuit according to the present invention.
Fig. 2(a) is a schematic diagram of an initial pin distribution according to an embodiment of the invention.
FIG. 2(b) is a schematic diagram of the layout scheme of the Steiner minimum tree with X structure according to an embodiment of the present invention.
FIG. 3(a) is a schematic diagram of two nets to be routed distributed on a routing diagram according to an embodiment of the present invention.
FIG. 3(b) is a schematic diagram illustrating the decomposition of N2 and the construction of candidate solutions for each two-terminal net according to 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 diagram illustrating four distributions of pins of a two-terminal net that can be directly wired during an initial wiring stage according to an embodiment of the present invention.
Fig. 6 is a schematic diagram illustrating four cases of the failure of direct connection due to the capacity limitation of the wiring edge in the initial wiring stage according to an embodiment of the present invention.
FIG. 7(a) is a schematic diagram of the pin crossing even grid of N1 in a new routing edge selection mode according to an embodiment of the present invention.
FIG. 7(b) is a schematic diagram of the pin-crossing odd grid of N1 in the new routing edge selection method according to an embodiment of the present invention.
FIG. 7(c) is a diagram of N2 in a new routing edge selection method according to an embodiment of the present invention.
FIG. 8 is a schematic diagram of a main stage of the present invention adopting PSO and maze routing based on new routing edge cost.
FIG. 9(a) is a diagram illustrating the reduction of the pre-wiring capacity during the initial wiring stage according to an embodiment of the present invention.
FIG. 9(b) is a diagram illustrating reduction of pre-wiring capacity at an initial wiring stage according to an embodiment of the invention.
Fig. 10 is a schematic diagram of channel capacity correlation according to an embodiment of the invention.
FIG. 11(a) is a diagram illustrating that dynamic resource allocation is not employed in an embodiment of the present invention.
FIG. 11(b) is a diagram illustrating dynamic allocation in an embodiment of the present invention.
FIG. 12 is a flowchart of algorithm 1 according to an embodiment of the present invention.
FIG. 13 is a flowchart of algorithm 2 according to an embodiment of the present invention.
FIG. 14 is a flowchart of algorithm 3 according to an embodiment of the present invention.
Detailed Description
The technical scheme of the invention is specifically explained below with reference to the accompanying drawings.
Aiming at the overall wiring problem considering two important conditions of a non-Manhattan structure and a multi-layer wiring structure, an X structure is taken as a representative of the non-Manhattan structure, and on the basis of the previous single-layer overall wiring algorithm research, four effective improvement strategies are provided based on an integer programming model (ILP for short) and a particle swarm optimization (PSO for short) aiming at a series of defects existing in the existing work, and a multi-layer wiring model and a layer scheduling strategy are introduced, so that a high-performance X-structure multi-layer overall wiring device called FZU-Router is constructed. The invention effectively solves the problem of multilayer overall wiring of an X structure for the first time, and the feasibility and the effectiveness of relevant strategies and algorithms of the invention are fully verified by simulation experiment results on a reference circuit of the multilayer overall wiring problem, and meanwhile, two most important indexes of overflow number and total cost of wire length in the multilayer wiring problem bring remarkable optimization effect.
Further, the present invention provides a method for multilayer global routing of a high performance X structure in a very large scale integrated circuit, as shown in fig. 1, comprising the following steps:
step S1: in the initial wiring stage, establishing an X-structure Steiner minimum tree;
further, in the present embodiment, the X-configuration Steiner min-tree approach connects a given set of pins with minimal cost by introducing Steiner points, which allow 45 ° and 135 ° routing directions in addition to the conventional horizontal and vertical directions. As shown in FIG. 2(a), an initial pin distribution is given, and FIG. 2(b) is a routing scheme for constructing an X-structured Steiner minimum tree.
Step S2: carrying out multi-terminal wire mesh decomposition;
further, in this embodiment, FIG. 3(a) shows two nets ready for routingN 1 AndN 2 and a maximum channel capacity of 2. Book (I)In the embodiment, the multi-terminal net is processed by a Steiner minimum tree algorithmN 2 Decomposed into 3 two-end nets (SG)8，SG6And SG1) And establishes corresponding wiring candidate solutions for all two-ended nets, as shown in FIG. 3 (b).
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;
further, in this embodiment, after the initial wiring stage is completed, the approximate crowded condition of the chip can be obtained, and the most crowded area of the chip can be searched from the initial wiring result. In the present embodiment, the size of 2 × 2 grid in the total wiring diagram is selected as the initial wiring sub-area in the main stage, and the most congested area refers to the area of 2 × 2 grid size, where the total sum of the wiring sides passed through in the initial wiring stage is the most.
Step S7: adding the two-end nets completely positioned in the current wiring area into a wiring set;
step S8: and solving an optimal solution in each wiring area by adding a wiring mode and establishing an ILP model based on a particle swarm optimization algorithm.
Further, in this embodiment, many routing algorithms commonly use the ILP model to solve the overall routing problem, and a relatively good routing scheme can be obtained. The method based on the ILP model comprises the steps of firstly, searching all possible wiring trees as candidate solutions, calculating the cost of each wiring tree, establishing a corresponding linear equation set with capacity constraint, and finally solving the linear equation set to obtain a final overall wiring scheme.
In the present embodiment, a process of solving the particle swarm optimization algorithm of the routing problem based on the ILP model is shown as algorithm 1.
Specifically, as shown in fig. 12, the algorithm 1 is implemented according to the following steps:
step S81: initializing;
step S82: performing mutation operation on the particles in sequence; performing a cross-operation of the particle with its historical optimal solution; performing cross operation of particles and a population global optimal solution; calculating a fitness function value of the particle;
step S83: judging that the fitness value of the particle p is smaller than the historical optimal value; if so, taking the current particle as a historical optimal solution;
step S84: judging that the fitness value of the particle p is smaller than the population global optimal value; if so, taking the current particle as a global optimal solution of the population; otherwise, go to step S85;
step S85: judging whether the maximum population number is reached, if not, turning to the step S82; if so, adding 1 to the current iteration frequency, and judging whether the maximum iteration frequency is reached; if so, the process is terminated, otherwise, the process goes to step S82.
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;
further, in this embodiment, after the routing based on the particle swarm optimization is completed in the current routing area, some unconnected nets at both ends often exist in the routing scheme, and therefore, a maze algorithm based on the cost of a new routing edge is designed to route these unconnected nets and is used as an important step for finally routing all nets. And the maze routing simultaneously considers the length of the wires and the congestion balance on the basis of the cost of a new routing edge, and routes the unconnected nets. Calculating the new routing edge cost in GRG is shown in algorithm 2. Based on the new routing edge cost, continuously performing maze routing for unconnected nets until unconnected nets do not exist, and the specific maze algorithm is shown as algorithm 3.
Specifically, in this embodiment, as shown in fig. 13, the algorithm 2 is implemented according to the following steps:
step S1001: determining edges of two-terminal sub-netse i Whether other sub-nets which are decomposed by the original multi-end net pass through; if yes, go to step S1002; otherwise, go to step S1003;
step S1002: and obtaining the new wiring edge cost through the following assignment operation:
cost(e i )=0；
step S1003: and obtaining 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 )；
wherein:lengthis a finger edgee i The length in the GRG is such that,congis a finger edgee i Congestion in GRG.
Specifically, in this embodiment, as shown in fig. 14, the algorithm 3 is implemented according to the following steps:
step S1011: inputting the remaining net set RN which is not wired after being wired based on the PSO:
step S1012: initializing each two-end net i in the RN;
step S1013: judging whether the current two-end line network i is larger than the maximum value of the line number in the RN; if yes, ending, otherwise, turning to the step S1014;
step S1014: executing: priority _ queue Q; adding a pin of a wire mesh i to Q, and marking the pin as a point to be expanded;
step S1015: judging whether Q is empty; if not, adding 1 to the serial number of the current two-end net i, and going to step S1013; if yes, go to step S1016;
step S1016: expanding and expanding Q.top points along all wiring directions by the size of one unit grid;
step S1017: judging whether the mark of the point is not expanded; if not, go to step S1015; otherwise, updating and calculating the wiring cost of the net i;
step S1018: judging 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: judging whether the wiring region is expandable, if so, expanding the wiring region according to a preset threshold, and turning to the step S6; otherwise, go to step S12;
step S12: and based on dynamic resource scheduling, adopting layer scheduling of a multilayer wiring model to finish the X-structure multilayer overall wiring.
In the present embodiment, the layer scheduling of the multilayer wiring model: in the layer scheduling process, sides having wiring directions of 0 ° and 90 ° are allocated to odd layers, and sides having wiring directions of 45 ° and 135 ° are allocated to even layers, as shown in fig. 4.
Further, in the present embodiment, an object of the present invention is to provide a method for constructing a multilayer global routing problem of an X structure in consideration of introduction and popularization of the X structure in a very large scale integrated circuit, which takes the most important performance indexes of two multilayer global routings, i.e., the overflow number and the total cost of wire length, as optimization targets, and finally achieves optimization of the two most important targets of the multilayer global routing.
Further, in this embodiment, four strengthening methods are proposed, including:
(1) a new type of wiring scheme is added. This helps to give up the routing rate of the connected two-terminal nets in the main stage in the initial stage, and this method is denoted as E1. Considering that, in the initial wiring stage of XGRouter, for the two-pin nets (this type of net set is referred to as NA) having slope values of 0, -1, +1, and ∞ of the straight line formed by the two pins after the decomposition, if the straight line is used to directly connect the two pins, the capacity of the connection side is not exceeded, the two-pin nets are directly connected by the straight line. If the maximum capacity limit of the routing edge is exceeded, the nets are relinquished and placed in the main stage for connection. However, improper routing edge selection is used in the main stage of XGRouter, which makes these nets unlikely to get a chance to connect in the main stage. Therefore, the introduction of E1 in the FZU-Router design helps to give up the routing rate of the connected nets at the main stage in the initial stage by adding a new type of routing.
(2) The combination of the particle swarm optimization algorithm and maze routing based on new routing cost is helpful for the unpaved wire net set in the current routing area to complete routing work at a higher routing rate, and the method is marked as E2. Considering that in the algorithm flow of the XGRouter, the main stage always adopts continuously expanded area wiring, and the post-processing stage adopts labyrinth wiring to continue wiring to the net which is not subjected to wiring, which may cause that the net which is not subjected to wiring before each expansion cannot be wired after the next expansion, so that a great number of nets which are not subjected to wiring are stacked, and the solution quality of the adopted PSO algorithm is greatly affected. Therefore, E2 was introduced in the FZU-Router design, and the maze routing strategy based on the new routing cost is moved to the main stage, and after each time the routing area is routed by using the PSO, the collection of the unmapped nets in the current routing area is facilitated to complete the routing work at a higher routing rate.
(3) The strategy of reducing the pre-wiring capacity in the initial stage enables the partial nets to be wired by the PSO algorithm in the main stage, makes full use of the global optimization capability of the PSO algorithm, and simultaneously further strengthens the optimization effect of the two strategies E1 and E2, and the method is marked as E3. Considering that in the algorithm flow of the XGRouter, because the initial stage adopts the greedy idea for the net set NA, the shortest connection length and the least occupied wiring resources are used for connection, which is likely to fall into some locally optimal schemes, and the main stage adopts the PSO algorithm with global optimization capability to perform the wiring of the nets at both ends from the perspective of more overall resources, which has stronger global optimization capability. Therefore, an E3 strategy is introduced into the design of FZU-Router, and the pre-routing capacity of the initial routing stage is reduced to half of the original capacity, so that the partial nets can be left in the PSO algorithm of the main stage for routing, the global optimization capability of the PSO algorithm is fully utilized, and the optimization effects of E1 and E2 are further enhanced.
(4) Designing a dynamic resource scheduling strategy, and introducing a multilayer wiring model and a multilayer scheduling strategy, thereby constructing a high-performance X-structure multilayer overall Router FZU-Router, and finally bringing a remarkable optimization effect on two most important indexes of overflow number and total wire length cost in a multilayer wiring problem, and marking the method as E4. Considering that in the XGRouter algorithm flow, the capacity of each routing edge is constant, and the capacity is static during routing, so that there is a possibility that a part of the routing edges are used less and in a sparse state, and a part of the routing edges are used too much and in a crowded state. E4 is introduced into the design of FZU-Router, and routing resources are dynamically adjusted in the routing process, so that the routing resources are more fully utilized for routing, and the optimization capability of the overall Router in terms of both overflow number and total cost of wire length is further optimized.
Further, in the present embodiment, in the initial wiring stage of XGRouter, for the two-pin nets (this type of net set is referred to as NA) having the slope values of 0, -1, +1, and ∞ of the straight lines formed by the two pins after the decomposition, if the two pins are directly connected by the straight lines and the capacity of the connection side is not exceeded, the two-end nets are directly connected by the straight lines. Four types of two-terminal net pin distribution situations that can be considered for direct connection, as shown in FIG. 5, include two pins with an included angle of 00,450,900And 1350Four cases. If the straight line is adopted to directly connect two pins, which can cause the situation of congestion and overflow, the two end nets (the net set is called NC) which can cause the overflow situation are abandoned to be directly connected, and the connection is carried out in the main stage. As shown in the figureAs shown in fig. 6, if nets at two ends that can be directly connected in fig. 5 cannot be connected in the initial stage due to the existence of a crowded area of a gray rectangle (i.e., overflow occurs in the gray rectangle area by passing through a winding, which seriously affects the routability of the chip), XGRouter puts them in the main stage for connection, but the connection method still adopts the connection edge method shown in fig. 5, which results in that nets that are abandoned in the initial stage cannot be connected in the main stage, which results in too many nets at two ends that cannot be connected, which greatly affects the solution performance of the PSO algorithm in the main stage.
Thus, in this embodiment, the present invention provides a new type of routing for a set of nets NC in the main stage of the Router FZU-Router so that these nets in the NC can be routed as completely as possible in the main stage. These new types of wiring edge connections used in E1, as shown in fig. 7, use two types of connections, 45 for the two-terminal nets (N1) in a horizontal or vertical relationship, as shown in fig. 7(a) and 7(b), respectively0Edge sum 1350Edge alternate connection mode and 450Edge 1350Side and horizontal or vertical side alternate connections, with pins of N1 of FIG. 7(a) spanning an even grid and pins of N1 of FIG. 7(b) spanning an odd grid; to 450Or 1350The two end nets (N2) of the relationship are connected as shown in fig. 7(c), that is, the horizontal side and the vertical side are alternately connected. With the newly added three alternative routing schemes of fig. 7(a) to 7(c), there is a greater possibility that the congested area can be reasonably avoided in the main stage.
Further, in this embodiment, the overall wiring results in terms of both the number of overflows (TOF) and the total cost of wire length (TWL) were compared for the unused and used E1 based on the standard test circuit of ISPD07, as shown in table 1. The overall routing results with E1 versus without E1 (denoted as E0 in the table) achieved a 16.63% reduction in the number of overflows, indicating that the improved strategy of E1 helps to connect as many net sets NC as possible from both ends of the initial route discard in the main stage, increasing the routing rate, and thus minimizing overflow. Although the total cost of a small amount of wire length is increased, the overflow number, which is the most important optimization target in the multi-layer overall wiring problem, brings considerable optimization, thereby showing the effectiveness and the necessity of E1.
TABLE 1 comparison of routing results without and with E1 strategy
Further, in this embodiment, after the E2 is adopted by FZU-Router, the maze routing strategy based on the new routing cost is moved to the main stage, and after the PSO is adopted in each box area for routing, it is helpful for the current box unpaved net set to complete the routing work with a higher routing rate.
In the XGROUTER algorithm flow, continuously expanded area wiring is adopted in the main stage, and labyrinth wiring is adopted in the post-processing stage to continue wiring on the net which is not subjected to wiring, so that the net which is not subjected to wiring before expansion each time can not be wired after the next expansion, and therefore a great number of nets which are not subjected to wiring are accumulated, and the solving quality of the adopted PSO algorithm is greatly influenced. As shown in fig. 8, in the XGRouter, P1 and P2 cannot complete wiring at box0 stage in the edge connection mode using XGRouter due to the existence of gray crowded area in box0 stage of P1 and P2. And if the P1 and P2 are connected by the solid line shown in fig. 8 after Box expands to the whole chip, the long routing may be caused, the total cost of the excessive routing length is paid, and more routing resources are occupied, thereby increasing the overflow number. In FZU-Router, the routing scheme prepares for the net that cannot be routed by PSO immediately after box0 is finished, so that P1 and P2 can be connected by dotted lines as shown in FIG. 8, and the resources around box0 are occupied as much as possible, rather than waiting for the full expansion, the resources around box0 are occupied. The adoption of the E2 improvement strategy can effectively reduce the redundant occupation of the wiring resources, thereby reducing the overflow number and further improving the completion rate of the wiring.
TABLE 2 comparison of routing results without and with E2 strategy
Further, the overall wiring results without and with the E2 improvement strategy were compared, as shown in table 2. Compared with the overall wiring result without the E2 strategy, the E2 strategy achieves a large reduction rate of 77.01% in the number of overflows, and shows that the improvement strategy of the E2 is beneficial to using the wiring resources near the nets as early and reasonably as possible in the main stage, connecting the nets at two ends more effectively, and improving the routing rate, so that the overflow condition is brought as little as possible. Although a small amount of total cost of wire length is paid (0.81 percent of total cost of wire length), the most important optimization target in the multi-layer overall wiring problem, namely the overflow number brings a large-scale optimization, thereby showing the effectiveness and the necessity of the E2 strategy in utilizing the wiring resources as reasonably as possible.
Further, in this embodiment, FZU-Router reduces the pre-routing capacity in the initial routing stage to half of the original capacity, so that the partial nets can remain in the PSO algorithm in the main stage for routing, thereby fully utilizing the global optimization capability of the PSO algorithm and further enhancing the optimization effects of the two strategies E1 and E2.
The initial stage adopts a greedy idea to connect the line network set NA, occupies the least wiring resources with the shortest connection length, is easy to fall into some local optimal schemes, and the main stage adopts a PSO algorithm with global optimization capability to perform wiring of the line networks at two ends from a more integral resource perspective, so that the global optimization capability is stronger. In the XGROUTER general router, an initial routing algorithm of a greedy strategy is applied to all routable two-end nets, so that an initial routing scheme is trapped in a relatively serious local optimal solution. Therefore, the new-generation multilayer overall Router FZU-Router adopts E3, the pre-wiring capacity in the initial wiring stage is reduced to half of the original capacity, partial wiring resources are reserved, and partial nets at two ends are handed to a PSO algorithm with stronger global optimization capacity for wiring, so that the global optimization capacity of the PSO algorithm can be fully utilized, and the optimization capacity of the FZU-Router is improved.
As shown in fig. 9(a) and 9(b), in the XGRouter, the pre-routing capacity reduction policy is not adopted in the initial routing stage, and it is assumed that the routing order of the nets at both ends in the initial routing is N1 (including two pins N11 and N12), N2 (including two pins N21 and N22), and N3 (including two pins N31 and N32), where it is assumed that the maximum capacity of the routing edge is 2. The routing strategy of XGRouter is adopted, i.e. N1 and N2 are preferentially connected, while N3 in the main phase requires a connection mode which occupies a very large number of routing resources and is very wasteful in total cost of wire length, as shown in fig. 9 (a). If the E3 improvement strategy of FZU-Router is adopted, half of the wiring resources are reserved, so after the E3 strategy is adopted, the initial wiring is only connected with the N1 net, and the N2 and N3 nets are left in the PSO algorithm of the main stage to try to solve, and the PSO algorithm can measure the wiring modes of the N2 and N3 nets from a more global perspective, so that the solution shown in FIG. 9(b) is obtained. It can be seen that, as shown in fig. 9(b), the connection method greatly reduces the occupation of unnecessary wiring resources, and completes the connection of three nets N1, N2, and N3 with fewer wiring resources.
Further, in order to further expand the advantages of the E1 improvement strategy, the E3 improvement strategy is added, thereby helping to improve the optimization capability of the total online length cost of the new generation of overall routers FZU-Router, and simultaneously enhancing the overflow number reduction capability. In the initial wiring stage, the channel capacity in the horizontal and vertical directions is limited to 1/2 of the set capacity. After the E3 improvement strategy is added, the number of nets at two ends for completing wiring through the E1 improvement strategy is greatly increased, the advantages of a PSO algorithm are fully utilized, a better optimization effect is achieved, and the advantages of E1 are further reflected.
Further, as shown in table 3, adding the initial routing capacity setting of the E3 policy to the E1 policy can achieve 17.27% and 1.27% good optimization effects in terms of both total overflow and total cost of wire length, respectively. As shown in table 4, adding the initial routing capacity setting of the E3 policy to the E2 policy can achieve certain optimization effects of 0.02% and 0.39% in terms of both total overflow and total cost of wire length. As shown in table 5, adding the initial routing capacity setting of the E3 strategy on the basis of the E1 and E2 strategies can achieve optimization effects of 1.38% and 1.45% in terms of both total overflow and total cost of wire length, respectively. In conclusion, the effectiveness of the introduction of the E3 strategy can be shown, and particularly, the E3 is particularly effective for the E1 strategy.
TABLE 3 comparison of routing results without and with E3 strategy based on E1 strategy
TABLE 4 comparison of routing results without and with E3 strategy based on E2 strategy
Table 5 compares the results of the E3 strategy with those of the E1 and E2 strategies
Further, in the present embodiment, if there is a capacity sharing the same channel wiring area between the horizontal or vertical side and the diagonal side, both sides have a channel capacity correlation.
The side which forms an included angle of 45 degrees with the horizontal side is positioned above the horizontal side, and the side with the left end point is related to the channel capacity of the horizontal side and shares the channel capacity of the specified horizontal side; and forming an included angle of 45 degrees with the vertical edge, locating at the right side of the vertical edge, and enabling the edge meeting the lower endpoint to be related to the channel capacity of the vertical edge and share the specified channel capacity of the vertical edge. Under this regulation, it is necessary to satisfy:
wherein,C l indicating the channel capacity of either a horizontal or vertical edge,C x representing diagonals having channel capacity dependence with horizontal or vertical edgesThe channel capacity of the side(s) is,C s representing the total channel routing capacity of the area. In this embodiment, the channel is a routing edge, and the channel capacity is a routing resource.
As shown in fig. 10, the channel wiring capacities of AB and AD are given, AC and AB share the channel wiring capacity of AB, AE and AD share the channel wiring capacity of AD, i.e., AC and AB have channel capacity dependency, AE and AD have channel capacity dependency.
Further, in this embodiment, after the overall routing of the partial nets is completed, routing resources are redistributed to two types of routing edges with channel capacity correlation, so that the channel capacities are concentrated to channels with dense routing, and the remaining capacity of each channel exceeds an expected value as much as possible, which is beneficial to subsequent routing, that is, dynamic channel capacity distribution is performed.
Further, in this embodiment, after the channel capacity is dynamically allocated as a routing resource, two types of routing edges having channel capacity dependency are expected, and the remaining routing capacity of the routing edges can exceed a fixed value, that is, a channel capacity dynamic allocation threshold is set.
Further, in this embodiment, after the overall routing of the partial nets is completed, the channels with the remaining channel capacity not exceeding the channel capacity dynamic allocation threshold are left.
Further, in this embodiment, after the overall wiring of the partial nets is completed, a channel whose remaining channel capacity exceeds the sum of the channel capacity dynamic allocation threshold and the dynamically allocated quota of channel capacity is taken as a sparse channel.
Further, in this embodiment, in the sparse channel and the congested channel having channel capacity correlation, under the condition that the specified total channel capacity is not changed, channel capacity dynamic allocation is used, channel capacity obtained by two channels tends to adapt to the wiring requirement of the target net, so that subsequent wiring has a larger selection space, the situation that subsequent wiring needs to be bypassed in a partially congested area is avoided, the overflow number and total cost of wire length of the final wiring result can be effectively reduced, and the operation time of the algorithm is shortened.
Further, in this embodiment, the overflow phenomenon occurs because no interconnectable path can be found between two points of the net at both ends of the target, i.e., at least one path between two points is blocked, while ensuring that the number of wires per path does not exceed the path capacity of the path. If the blocked channel can be unblocked, an interconnectable pathway can be found between the two points. In the process of executing the routing algorithm, the absolute uniformity of the net cannot be guaranteed, so that channels with a large residual capacity and channels with a few residual capacities exist in the whole routing area. Meanwhile, according to the wiring requirement, the total capacity among the channels related to the channel capacity only meets the regulation, and no requirement exists for the distribution of the capacity between the two channels. In conclusion, the channel capacity is dynamically allocated among the channels related to the channel capacity, so that the blocked channel can be dredged to the maximum extent, the probability of blocking interconnection lines of the two-end nets can be reduced, and the risk of blocking the channel is reduced.
Whether a certain channel will be used in the routing process is difficult to predict in the optimization process of the PSO algorithm. For the channel capacity related channel which is not used in the wiring process and the channel capacity related channel which is being wired, the dynamic allocation effect of the channel capacity is difficult to guarantee, in order to avoid the influence of invalid work on the wiring quality, after each box expansion is finished, the PSO wiring scheme is determined, and in the process of wire network connection, the connected channels test the feasibility of the dynamic allocation of the channel capacity one by one and carry out the dynamic allocation of the channel capacity on the required channel is most suitable.
Further, in this embodiment, to achieve the purpose of dynamically allocating channel capacity, channel capacity may be dynamically allocated between a sparse channel and a congested channel, which are channels related to each other.
Two channels are provided which are channels related to each other in channel capacity. If one of the channels is a non-sparse non-congested channel, if the residual capacity is allocated according to the dynamically allocated quota of the channel capacity, the channel becomes a congested channel, and the residual capacity per se exceeds the dynamically allocated threshold of the channel capacity, the channel capacity allocation is not required to be obtained, so that the channel capacity dynamic allocation is meaningless. If both channels are congested channels, the purpose of dynamic allocation of channel capacity can never be achieved. Dynamic allocation of channel capacity is also meaningless if both channels are sparse. In summary, to achieve the purpose of dynamically allocating channel capacity, channel capacity may be dynamically allocated between a sparse channel and a congested channel, which are channels related to each other.
Fig. 11(a) shows the current situation after the partial routing is completed, where the red broken line ABCD shows the routing scheme selected by the main-stage PSO algorithm, the channel identified by the blue line segment and the channel identified by the red line segment are channels related to each other in channel capacity, and the number near the channel is the remaining capacity of the channel. At this point, the net connections for the main stage PSO algorithm wiring scheme have not been made. The residual capacities of the channels AB, BC and CD in the wiring scheme ABCD are 2, 4 and 3, respectively, the channels which are the channels associated with the channel capacities are AE, BF and CG, respectively, and the residual capacities are 3, 7 and 5, respectively.
Further, a channel capacity dynamic allocation threshold value is set to be 2, and a resource allocation quota is set to be 2. At this time, after the main phase PSO algorithm finishes selecting the wiring scheme, the connection line shown in fig. 11(b) is started, AB is connected first, the remaining channel capacity of AB becomes 1, which is smaller than the threshold 2, and is a congested channel, but the remaining capacity of the channel capacity related channel AE is less than 4, and is not a sparse channel, and does not reach the condition of dynamic channel capacity allocation, and no resource allocation is performed. And C, connecting BC again, wherein the residual channel capacity of BC is 3 and exceeds 2, channels are not crowded, the condition of dynamic allocation of channel capacity is not met, and resources are not allocated. And finally, connecting the CD, wherein the residual channel capacity of the CD is 2 and does not exceed 2, the CD is a crowded channel, the residual capacity of the CG of the channel capacity related channel is 5 and is more than 4, the CD is a sparse channel, and the CG is allocated with 2 channel capacities to the CD when the condition of dynamically allocating the channel capacity is met. Finally, the remaining capacity of CD becomes 4 and the remaining capacity of CG becomes 3, both being above the threshold 2 for dynamic allocation of a given channel capacity, facilitating subsequent routing.
TABLE 6 comparison of wiring results without and with E4
Furthermore, experiments show that resource waste is caused when the dynamic allocation threshold of the channel capacity is too large, the requirement of resource allocation is difficult to meet when the dynamic allocation threshold of the channel capacity is too small, and the optimal result is obtained when the dynamic allocation threshold of the channel capacity is 2. When the amount of the channel capacity dynamic allocation distributed every time is too large, the capacity allocation among the channels related to the channel capacity can be repeated, so that the time overhead of the algorithm can be increased, the capacity of each channel can hardly adapt to the requirement of wiring, and the wiring effect is poor; when the dynamic allocation of channel capacity is too small, the channel required to obtain capacity allocation may have limited capacity, and the improvement in time and wiring results may be undesirable. Finally, it is found that when the channel capacity is dynamically allocated to have a quota of 2 per allocation, the optimal wiring result is obtained, and the time is greatly improved.
Finally, a channel capacity dynamic allocation threshold of 2 and an amount of 2 allocated each time are selected as parameters of E4. To further verify the effectiveness of the E4 policy, the present invention compares the overall wiring results without and with the E4 policy. Specific comparative results are shown in table 6. From table 6, it can be seen that the algorithm employing E4 achieves 2.17% and 2.8% optimization effects, respectively, with respect to the algorithm not employing E4, in terms of both total overflow count and total cost of wire length. While the algorithm employing E4 achieved a 1.38 time acceleration ratio in terms of CPU time relative to the algorithm not employing E4. In summary, it is described that the resource dynamic adjustment policy, that is, the E4 policy can obtain good optimization capabilities in three aspects of total overflow number, total cost of wire length, CPU time, and the like, and further describe the effectiveness and necessity of the E4 policy.
Further, in the embodiment, in order to enable 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 multilayer wiring problem, the method of the present invention is combined with document [1 ]: moffat MD. maize, Engineering an effective global route, IEEE Transactions on Computer-aid Design of Integrated Circuits and Systems, 2008, 27(11): 2017-: two serial global routing algorithms proposed in Chang YJ, Lee YT, Gao JR, et al, NTHU-Route 2.0A robust global router for model designs, IEEE Transactions on Computer-aid Design of Integrated Circuits and Systems, 2010, 29(12): 1931-1944, were experimentally compared on an ISPD07 reference circuit. These rectangular global routing serial algorithms are based on the manhattan architecture and are all tested on ISPD07 reference circuits, and the corresponding experimental results are given in table 7. As can be seen from Table 7, the method of the present invention achieves 23.94% and 11.40% optimization effects in terms of the overflow number compared with the two algorithms in documents [1] and [2], and particularly achieves 100% reduction rate of the overflow number on test example 16, i.e. optimization to no overflow, and 91.5% and 91.2% reduction rate of the overflow number on test example 18, compared with document [1], thereby greatly improving the distribution and manufacturability of the chip. The method of the invention respectively obtains 22.26% and 17.17% of total cost reduction rate of wiring in a rectangular bus face relative to two algorithms in the document [1] and the document [2 ]. In particular, the bus length reduction rate of 34.17% was achieved in test example 16 in comparison with document [1 ]. The reasons that the method of the invention can effectively reduce the overflow number and the bus length compared with other serial algorithms include: because the method introduces the X structure and carries out overall wiring from the global angle, the method has relatively stronger wire length optimization capability and can better overcome the problem of the dependence of serial algorithms on the wiring sequence of the wire network, thereby effectively reducing the crowding condition and the overflow condition.
TABLE 7 comparison of Overall routing Algorithm with two Serial algorithms on ISPD07
To further verify the validity of the inventive method on the ISPD07 reference circuit, the inventive method is compared with document [3 ]: cho M, Lu K, Yuan K, et al, Boxrouter 2.0, A hybrid and robust global router with layer assignment for routing, ACM Transactions on Design Automation of Electronic Systems, 2009, 14(2): 1-21, and document [4 ]: roy AJ, Markov IL, High-performance routing at the nanometer scale, IEEE Transactions on Computer-aid Design of Integrated Circuits and Systems, 2008, 27(6): 1066) 1077. two global routing parallel algorithms were compared, and corresponding experimental results are given in Table 8. As can be seen from Table 8, the method of the present invention achieves optimization effects of 24.11% and 24.15% in terms of the overflow number compared with the two algorithms in documents [3] and [4], and particularly achieves a 100% reduction rate of the overflow number on test example 16, i.e., optimizing the result to the case of no overflow, and achieves 92.9% and 93.18% reduction rates of the overflow number on test example 18, which greatly improves the distribution and manufacturability of the chip, compared with the two algorithms in documents [3] and [4 ]. The method of the invention respectively obtains 20.24% and 16.33% of total cost reduction rate of wiring in rectangular bus face relative to two algorithms in documents [3] and [4 ]. In particular, a bus length reduction rate of 33.66% was achieved in test example 16 as compared with document [3 ].
Further, in this embodiment, the reasons that the method of the present invention can effectively reduce the number of overflows and the bus length relative to other parallel algorithms include: (1) FZU-Router introduced an X-architecture that achieved less bus length than the Manhattan architecture; (2) FZU-Router adopts an improved PSO algorithm to solve the FX-ILP model, and can solve the problem that the solution of the ILP model by adopting a random rounding method is easy to generate deviation, so that the optimization of the total line length is finally brought. Meanwhile, the FZU-Router is designed primarily for further optimizing the overflow number and then optimizing the total cost of wire length, and is consistent with the performance requirement of the multilayer overall wiring, so that the multilayer overall wiring problem can be solved more effectively and qualitatively.
TABLE 8 comparison of Overall routing Algorithm with two parallel algorithms on ISPD07
The above are preferred embodiments of the present invention, and all changes made according to the technical scheme of the present invention that produce functional effects do not exceed the scope of the technical scheme 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: 450Edge sum 1350The edges are alternately connected;
the second method comprises the following steps: 450Edge 1350Sides 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.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201711060869.5A CN107832519B (en) | 2017-11-02 | 2017-11-02 | Multilayer overall wiring method for high-performance X structure in ultra-large scale integrated circuit |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201711060869.5A CN107832519B (en) | 2017-11-02 | 2017-11-02 | Multilayer overall wiring method for high-performance X structure in ultra-large scale integrated circuit |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN107832519A CN107832519A (en) | 2018-03-23 |
| CN107832519B true CN107832519B (en) | 2021-01-29 |
Family
ID=61651409
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201711060869.5A Active CN107832519B (en) | 2017-11-02 | 2017-11-02 | Multilayer overall wiring method for high-performance X structure in ultra-large scale integrated circuit |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN107832519B (en) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108733936A (en) * | 2018-05-28 | 2018-11-02 | 福州大学 | The discrete relaxation that DSA via layer triplex modes decompose |
| CN110133733B (en) * | 2019-04-28 | 2020-07-24 | 吉林大学 | Conductance-polarizability multi-parameter imaging method based on particle swarm optimization algorithm |
| CN110705204B (en) * | 2019-09-27 | 2023-03-24 | 福州大学 | Time sequence perception layer distribution method based on multi-stage strategy |
| CN110795907B (en) * | 2019-09-30 | 2021-05-18 | 福州大学 | X-structure Steiner minimum tree construction method considering wiring resource relaxation |
| US11501052B1 (en) * | 2021-05-27 | 2022-11-15 | Taiwan Semiconductor Manufacturing Company, Ltd | Conductor scheme selection and track planning for mixed-diagonal-Manhattan routing |
| CN113657067B (en) * | 2021-06-30 | 2023-07-21 | 福州大学 | Multi-strategy optimization-based multi-layer overall wiring method for very large scale integrated circuit |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH08194727A (en) * | 1995-01-18 | 1996-07-30 | Hitachi Ltd | Connection relation display method among arranged elements |
| CN1588381A (en) * | 2004-07-06 | 2005-03-02 | 清华大学 | Rectangular steiner tree method of super large size integrated circuit avoiding barrier |
| CN103902774A (en) * | 2014-03-31 | 2014-07-02 | 福州大学 | Overall wiring method for super-large-scale integrated circuit under X structure |
| CN103902775A (en) * | 2014-03-31 | 2014-07-02 | 福州大学 | Multilayer obstacle-avoiding Steiner minimal tree construction method for very large scale integration |
| CN104462628A (en) * | 2013-09-24 | 2015-03-25 | 复旦大学 | Construction method and device for barrier-bypassing eight-fork Steiner minimum tree |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8418113B1 (en) * | 2011-10-03 | 2013-04-09 | International Business Machines Corporation | Consideration of local routing and pin access during VLSI global routing |
-
2017
- 2017-11-02 CN CN201711060869.5A patent/CN107832519B/en active Active
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH08194727A (en) * | 1995-01-18 | 1996-07-30 | Hitachi Ltd | Connection relation display method among arranged elements |
| CN1588381A (en) * | 2004-07-06 | 2005-03-02 | 清华大学 | Rectangular steiner tree method of super large size integrated circuit avoiding barrier |
| CN104462628A (en) * | 2013-09-24 | 2015-03-25 | 复旦大学 | Construction method and device for barrier-bypassing eight-fork Steiner minimum tree |
| CN103902774A (en) * | 2014-03-31 | 2014-07-02 | 福州大学 | Overall wiring method for super-large-scale integrated circuit under X structure |
| CN103902775A (en) * | 2014-03-31 | 2014-07-02 | 福州大学 | Multilayer obstacle-avoiding Steiner minimal tree construction method for very large scale integration |
Non-Patent Citations (1)
| Title |
|---|
| 一种串扰和时延驱动的总体布线算法;庄昌文 等;《电子科技大学学报》;20000630;第29卷(第03期);第233-238页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN107832519A (en) | 2018-03-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN107832519B (en) | Multilayer overall wiring method for high-performance X structure in ultra-large scale integrated circuit | |
| JP2759573B2 (en) | Circuit board wiring pattern determination method | |
| Koh et al. | Manhattan or Non-Manhattan? A study of alternative VLSI routing architectures | |
| CN110795908B (en) | Bus sensing overall wiring method driven by deviation | |
| Li et al. | Routability-driven placement and white space allocation | |
| JP4227304B2 (en) | Outline wiring method and apparatus, and recording medium storing outline wiring program | |
| CN111814420B (en) | Overall wiring method based on topological optimization and heuristic search | |
| Wimer et al. | Optimal aspect ratios of building blocks in VLSI | |
| US20040216072A1 (en) | Porosity aware buffered steiner tree construction | |
| Cong et al. | An enhanced multilevel routing system | |
| CN106682306B (en) | Rapid FPGA wiring method | |
| CN113657067B (en) | Multi-strategy optimization-based multi-layer overall wiring method for very large scale integrated circuit | |
| CN111709205A (en) | FPGA wiring method | |
| Ao et al. | Delay-driven layer assignment in global routing under multi-tier interconnect structure | |
| CN115983187A (en) | Multi-strategy-based layer distribution method considering bus deviation | |
| Yao et al. | Pathfinding Model and Lagrangian-Based Global Routing | |
| Zhu et al. | Minideviation: an efficient multi-stage bus-aware global router | |
| Hyun et al. | Integrated power distribution network synthesis for mixed macro blocks and standard cells | |
| Cao et al. | DraXRouter: global routing in X-architecture with dynamic resource assignment | |
| Xiang et al. | An algorithm for simultaneous pin assignment and routing | |
| Ansari et al. | Advancement in energy efficient routing algorithms for 3-D Network-on-Chip architecture | |
| Hu et al. | A routing paradigm with novel resources estimation and routability models for X-architecture based physical design | |
| Dong et al. | Lithography-friendly analog layout migration | |
| CN116127906A (en) | High performance layer distribution method under advanced through hole column technology | |
| Zhong et al. | Whitespace insertion for through-silicon via planning on 3-D SoCs |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| TR01 | Transfer of patent right |
Effective date of registration: 20230105 Address after: 201306 2nd floor, no.979 Yunhan Road, Lingang New Area, China (Shanghai) pilot Free Trade Zone, Pudong New Area, Shanghai Patentee after: Shanghai Lixin Software Technology Co.,Ltd. Address before: No.2, Xueyuan Road, University Town, Shangjie Town, Minhou County, Fuzhou City, Fujian Province Patentee before: FUZHOU University |
|
| TR01 | Transfer of patent right |