CN117272917A - Bus topology perception global wiring method based on multiple strategies - Google Patents

Abstract

The invention discloses a bus topology perception global wiring method based on multiple strategies, aiming at the defects that the number of line segments is increased, the utilization rate of wiring space is reduced and the consistency of a bus topology structure cannot be ensured caused by a FLUTE algorithm, adopting a congestion topology reconstruction strategy to search an equilibrium point between the consistency of the bus topology structure and the line length of a wire network so as to optimize a wiring scheme; aiming at the problem that the mixed unidirectional monotone wiring HUMR possibly generates conflict of wiring resources, so that the wiring in the final result generates large topology deviation, a wire stripping and re-distribution algorithm considering bus topology is adopted, and the whole congestion value is considered when re-distribution is carried out, so that the topology deviation among different signal bits can be ensured to be minimum.

Description

Bus topology-aware global routing method based on multi-strategy

Technical field

The invention relates to the technical field of computer-aided design of integrated circuits, and in particular to a multi-strategy-based bus topology-aware global wiring method.

Background technique

As the semiconductor industry develops into the nanometer era, the scale of modern electronic systems has grown rapidly. In the entire Very Large Scale Integration (VLSI) wiring process, wiring is divided into two major stages for processing, namely global wiring and detailed wiring. Global wiring can be divided into the 2D wiring stage and the layer allocation stage. First, the multi-layer wiring resources are mapped to the 2D plane, and then the wiring is completed on the 2D plane to obtain an initial 2D wiring result. Then each element in the 2D wiring result is The wires are assigned to each metal layer to obtain the final 3D wiring scheme. A bus is a group of signal bits that connect multiple terminals (pins) and transmit data or control signals. With the advancement of technology, the number of bus structures for multi-chip modules, I/O pins and on-chip memories has increased, making bus wiring more and more important, and making manual wiring an extremely complex task.

Each signal bit of the bus can be routed through traditional routing methods, but the increase in clock frequency has led to special routing constraints during the bus routing process, including length matching constraints and topology consistency constraints. For the same bus, each signal bit needs to coordinately transmit the signal. If the difference in signal arrival time is too large, the transmitted information will be incorrect, resulting in a weakening of the chip's data processing capability, resulting in a reduction in chip performance. Therefore It is very necessary to consider the topology and length of the bus during the global wiring process. In addition, for global wiring problems that consider buses and non-buses, existing global wiring algorithms cannot effectively handle the problem of consistent bus topology.

Contents of the invention

In order to solve the problems existing in the existing technology, the present invention proposes a multi-strategy-based bus topology-aware global wiring method, including the following key strategies: First, after estimating wiring resources through the FLUTE algorithm, a method based on The congestion topology reconstruction algorithm is used to optimize the topology structure and effectively improve the utilization of wiring space; secondly, a heuristic dewiring and redistribution model is constructed to complete the rewiring of the multi-signal bus and effectively reduce the bus delay. ; Finally, an iterative scheme for adaptively adjusting the wiring range and wiring cost function is proposed to expand the wiring utilization of the wiring process and effectively optimize the consistency of the bus topology. Experimental results on multiple benchmark tests show that the algorithm and related strategies proposed by the present invention can effectively optimize the bus topology, thereby obtaining a high-quality 2D wiring scheme.

The main design points of the present invention include the following points:

In view of the shortcomings of the FLUTE algorithm that leads to an increase in the number of line segments, a reduction in the utilization of wiring space, and the inability to ensure the consistency of the bus topology, a congestion-based topology reconstruction strategy is adopted to find a balance between the consistency of the bus topology and the length of the line network. points to optimize the wiring scheme;

In order to solve the problem that hybrid unidirectional monotonic wiring HUMR may cause conflicts in wiring resources, resulting in large topological deviations in the final wiring, a dewiring and redistribution algorithm that considers the bus topology is used to consider the overall congestion when redistributing. value to ensure that the topological deviation between different signal bits can be minimized.

And, in the iterative wiring process, since the determination of the historical cost function has a non-negligible impact on the final wiring result, a cost function cost(N) based on historical deviations is proposed, and the historical cost function automatically changes with the iterative process. Adapt to modifications and adjustments.

In order to achieve the above objects, the present invention adopts the following technical solutions:

A bus topology-aware global wiring method based on multi-strategy, which is characterized by: in view of the shortcomings of the FLUTE algorithm that leads to an increase in the number of line segments, a reduction in the utilization of wiring space, and the inability to ensure the consistency of the bus topology, a congestion-based topology reconstruction is adopted Strategy to find a balance point between bus topology consistency and line network length to optimize the wiring plan;

In order to solve the problem that hybrid unidirectional monotonic wiring HUMR may cause conflicts in wiring resources, resulting in large topological deviations in the final wiring, a dewiring and redistribution algorithm that considers the bus topology is used to consider the overall congestion when redistributing. value to ensure that the topological deviation between different signal bits can be minimized.

Furthermore, in view of the shortcomings of the FLUTE algorithm that leads to an increase in the number of line segments, a reduction in the utilization of wiring space, and the inability to ensure the consistency of the bus topology, a congestion-based topology reconstruction strategy is adopted to balance the consistency of the bus topology and the length of the line network. Find a balance point among them to optimize the wiring plan, including the following steps:

Step 11: Select a group of wire nets with the highest wiring cost;

Step 12: Traverse all pseudo-Steiner points in the line network group and confirm the congestion level around them;

Step 13: Eliminate the pseudo-Steiner points with the greatest congestion and reconstruct the line network at both ends through the Prim algorithm;

Step 14: Remove and redistribute the wire network at both ends constructed in Step 13.

Further, each pseudo-Steiner point that may be eliminated is traversed, the congestion cost V _total is calculated based on the line network at both ends, and the point with the largest congestion cost is eliminated; V _total is calculated as follows:

The degree of congestion is used to calculate the cost function V _path required to construct the line network at both ends. The calculation method is:

Among them, path represents the path with the pseudo-Steiner point as the endpoint, e∈path represents each edge in the path, d(e) represents the congestion value of edge e, n represents the number of paths with the pseudo-Steiner point as the endpoint, D( path _i ) represents the sum of the congestion costs of the path, and c(e) represents the capacity of edge e.

Furthermore, in order to solve the problem that hybrid unidirectional monotonic wiring HUMR may cause conflicts in wiring resources, resulting in large topological deviations in the wiring in the final result, a dewiring and redistribution algorithm that considers the bus topology is used to consider when redistributing The overall congestion value ensures that the topological deviation between different signal bits can be minimized, including the following steps:

Step 21: Remove the wiring paths between the selected bus pin pairs and the non-bus pin pairs in the wiring area, and remove the non-bus wiring paths to ensure sufficient wiring space in the wiring area;

Step 22: By considering the overall wiring space, select the wiring path with the most sufficient wiring resources for the first signal bit. Each subsequent path is calibrated with the first signal bit path to ensure that the topological deviation and wiring cost are minimized. ;

Step 23: Route the remaining non-bus pin pairs to ensure connectivity in the final result.

Furthermore, during the iterative wiring process, the cost function cost(N) based on historical deviations is used, and the historical cost function is adaptively modified and adjusted along with the iterative process; the calculation method of cost(N) is as follows:

Among them, p represents the wiring path; b _e is the wiring cost and includes the cost of placing the edge; c _t is the congestion cost of the area where the edge is placed; d _t is the bus topology deviation cost;

Among them, ε is a custom parameter; i is the number of iterations; c(e) represents the number of wiring tracks available between adjacent G-Cells, and d(e) represents the number of actually used wiring tracks.

Further, the deviation cost d _t is added to the cost function; the calculation method of d _t is as follows:

Among them, α and β are customized parameters, and B is the number of bus line net groups.

Compared with the prior art, the main differences and advantages of the present invention and its preferred solutions include:

1. During the wiring process, after estimating wiring resources based on the FLUTE algorithm, a congestion-based topology reconstruction algorithm is proposed to optimize the topology and effectively improve the wiring space utilization.

2. Design a heuristic dewiring and redistribution model to complete the rewiring of the bus with multiple signal bits. In addition, a pathfinding algorithm that considers the topology is used in the dewiring and redistribution model. By considering the routing space, Distribute and find the most suitable bus path to effectively reduce bus delay.

3. During the iterative wiring process, an iterative scheme is proposed to adaptively adjust the wiring range and wiring cost, further optimizing the consistency of the bus topology. Experimental results show that the algorithm and related strategies proposed by the present invention can effectively reduce the topological deviation of the bus.

Description of the drawings

Figure 1 is a schematic diagram of the bus topology model; (a) 2D wiring scheme; (b) real disparity map 2D topology violation example.

Figure 2 is an illustration of topology reconstruction according to an embodiment of the present invention; (a) initial line network; (b) FLUTE algorithm to construct a two-end line network; (c) construction based on wiring cost; (d) construction based on congestion cost.

Figure 3 is an explanatory diagram of wire removal and redistribution according to an embodiment of the present invention; (a) initial pin distribution; (b) determination of the first path; (c) sufficient wiring resources; (d) insufficient remaining wiring resources.

Detailed ways

In order to make the features and advantages of this patent more obvious and easy to understand, examples are given below and explained in detail as follows:

It should be noted that the following detailed description is illustrative and is intended to provide further explanation of the present application. Unless otherwise specified, all technical and scientific terms used in this specification have the same meanings commonly understood by one of ordinary skill in the art to which this application belongs.

It should be noted that the terms used herein are only for describing specific embodiments and are not intended to limit the exemplary embodiments according to the present application. As used herein, the singular forms are also intended to include the plural forms unless the context clearly indicates otherwise. Furthermore, it will be understood that when the terms "comprises" and/or "includes" are used in this specification, they indicate There are features, steps, operations, means, components and/or combinations thereof.

The solution of the present invention is further introduced below in conjunction with specific examples:

1. Global wiring process model:

A bus net group consists of multiple bus pin groups. Each pin group of the same bus net group contains multiple pins. The pins of the same pin group are arranged in parallel with each other and each pin of the same bus net group The number of pins in the pin group is the same, and the pins are defined as signal bits. For each signal bit in the pin group, there is a corresponding signal bit in the other pin group; each signal bit is connected The number of wire segments is called the number of bus segments; the bus topology consists of wiring segments of specific paths and wiring directions. Figure 1(a) shows a wiring example of a group of 4-bit bus nets. The bus net group consists of 2 pin groups, and the two pin groups contain 4 pins that need to be connected in pairs ( bit1, bit2, bit3, bit4), its bus topology consists of three bus segments, and the wiring direction of each segment is consistent.

In bus wiring problems, the impact of inconsistent 2D topology must be considered. As an example of topology violation shown in Figure 1(b), the number of bus segments in the connection between bit1, bit2 and bit3 is different; the bus between bit2 and bit4 The number of line segments is the same but the directions of the wiring segments are different. This structural inconsistency will lead to inconsistent arrival times of signals starting at the same time, which directly affects the quality of the chip.

The global wiring problem considering the bus topology is: given a z-layer global wiring diagram G ^z = (V ^z ,E ^z ), a non-bus net set N = {n ₁ , n ₂ ,..., n _m } and A set of bus nets B = {b ₁ , b ₂ ,…, b _n }, and for each non-bus net there is a set of pins P = {p ₁ , p ₂ ,…, p _k }, if As a bus line network group, a group of bus pin groups BP = {bp ₀ , bp ₁ ,..., bp _r } is given, where bp ₀ is defined as the source pin group and bp _j is defined as the sink pin group; and Given the wiring capacity C={c ₁ ,c ₂ ,...,c _z } of each wiring layer, the obstacle set O={o ₁ ,o ₂ ,...,o _i }. According to the position of the G-Cell where the pin is located, the set P is mapped to the vertex of G ^z = (V ^z , E ^z ). We need to route all bus and non-bus pin groups and ensure that the weighted sum of C _total is minimum. C _total is calculated as follows:

Among them, α and β are constants, C _w represents the ratio of the actual wire length of bus _i wiring to the theoretical shortest wire length, #bits represents the number of signal bits in bus _i , and C _s represents the bus network. The ratio of the actual number of line segments in group bus _i wiring to the theoretical shortest number of line segments. #segs represents the number of line segments in group bus _i .

2. Topology reconstruction strategy:

Since the bus net group usually has more than 2 pin groups, the wiring quality depends to a large extent on the topology of the wiring net group. In order to ensure that the length of the line network is the shortest, the FLUTE algorithm will generate a pseudo-Steiner point and generate multiple two-end line nets based on this point, which is equivalent to treating the pseudo-Steiner point as a must-pass point during the wiring process, resulting in constraints in the wiring process. Increased,routable space reduction. Although its wire length is the shortest, the number of wire segments will be greatly increased, the utilization of wiring space will be greatly reduced, and the consistency of the bus topology cannot be guaranteed. Therefore, the present invention first proposes a congestion-based topology reconstruction strategy, which can find a balance point between the consistency of the bus topology structure and the length of the line network to optimize the wiring plan. The core idea of this algorithm is to eliminate some pseudo-Steiner points in crowded areas through the congestion cost map, and then reconstruct the line network at both ends to optimize the consistency of the topology while reducing the number of line segments.

The algorithm steps are as follows:

Step 1: Select a group of nets with the highest wiring cost.

Step 2: Traverse all Steiner points in the line network group and confirm the congestion level around them.

Step 3: Eliminate the Steiner points with the greatest congestion and reconstruct the line network at both ends through the Prim algorithm.

Step 4: Remove the wire nets at both ends constructed in step 3 and redistribute them.

As shown in Figure 2(a), given a bus pin group with three pin groups, the bus net group has one source point and two sink points. The green point is the pseudo-Steiner point found through the FLUTE algorithm. In this algorithm, the wiring space around the pseudo-Steiner point will be traversed. The black squares in Figure 2(b) represent areas with higher congestion levels. Since only the shortest wire length is considered when building pins in the initial stage without considering congestion, some of these pseudo-Steiner points may have a negative impact on subsequent routing. If the path passing through the pseudo-Steiner point passes through a large number of black squares, the pseudo-Steiner point will be eliminated and re-planned.

After eliminating pseudo-Steiner points and regenerating the topology through the Prim algorithm, if the line length is used as the calculation cost of the Prim algorithm, the topology shown in Figure 2(c) will be generated. When the wiring cost and wiring congestion are used as the calculation cost, the topology result shown in Figure 2(d) is produced. Although the wiring length of Figure 2(d) is longer than the result shown in Figure 2(b), it passes through less congested areas than Figure 2(c), and can effectively avoid areas with excessive congestion while ensuring the safety of subsequent wiring. Bus topology consistency. In addition, the wire nets that produce topological deviations are generally wire nets with a larger span, that is, a wiring net group with a larger wiring area. Such wiring can try to avoid the central area where wiring pins are densely packed, and finding a path along the border can also free up more wiring space for other wire nets with smaller wiring ranges.

Therefore, the key to the congestion-based topology reconstruction strategy is to determine the pseudo-Steiner points that need to be eliminated and the cost function used to construct a new two-end line network. Traverse each pseudo-Steiner point that may be eliminated, calculate the congestion cost V _total based on its two-end line network, and then eliminate the point with the largest congestion cost. V _total is calculated as follows:

In addition, the most critical thing for constructing a two-end line network through Prim's algorithm is to calculate the cost between two points. Therefore, the congestion level is used to calculate the cost function V _path required to construct a two-end line network. The calculation method is:

Among them, path represents the path with the pseudo-Steiner point as the endpoint, e∈path represents each edge in the path, d(e) represents the congestion value of edge e, n represents the number of paths with the pseudo-Steiner point as the endpoint, D (path _i ) represents the sum of congestion costs of the path, and c(e) represents the capacity of edge e.

3. Wire removal and redistribution strategy based on bus topology

Hybrid Unilateral Monotonic Routing (HUMR) is given a redistributed bounding box, and each point in it is regarded as an "intermediate point". The routing path consists of two paths within the rerouted bounding box. Calculate the cost from the starting point and end point of each wiring path to the "middle point", and select the two paths with the lowest cost to form the final path. In addition, since such a wiring method sequentially finds the optimal path in each iteration, conflicts in wiring resources may occur, resulting in large topological deviations in the wiring in the final result. In order to avoid this situation, the present invention proposes a wire removal and redistribution algorithm that takes the bus topology into consideration. The overall congestion value is taken into account when redistributing to ensure that the topological deviation between different signal bits can be minimized. The algorithm mainly consists of the following steps:

Step 1: First, remove the wiring paths between the selected bus pin pairs and the non-bus pin pairs in the wiring area, and remove the non-bus wiring paths to ensure sufficient wiring space in the wiring area;

Step 2: By considering the overall wiring space, select the wiring path with the most sufficient wiring resources for the first signal bit. Each subsequent path is calibrated with the first signal bit path to ensure that the topological deviation and wiring cost are minimized. ;

Step 3: Finally, route the remaining non-bus pin pairs to ensure connectivity in the final result.

The congestion-driven rewiring technology is explained below through the example of Figure 3. For a bus with four signal bits, the location of the bus pin group as shown in Figure 3(a) determines its wiring space as a 6×5 rectangular grid; and due to the complexity of wiring, The wiring resources are also inconsistent, and then the path that can pass the most signal bits is selected based on the congestion level as shown in Figure 3(b).

After the first wiring path is obtained, subsequent wiring will be considered in two cases. The first case is that the number of signal bits is less than the maximum number of wiring allowed by the initial path, then all signal bits of the bus line network group are selected. The first wiring path is used as the final wiring scheme as shown in Figure 3(c) to ensure the deviation of the final wiring scheme and the consistency of the topology.

The second case is that the number of signal bits wired is greater than the maximum number of wires allowed by the initial path. In order to ensure the consistency of the bus topology, path search is performed by translating the movable wires. After moving the path, a space with sufficient wiring resources is found for routing. The final wiring result is shown in Figure 3(d). Therefore, the key to congestion-driven heavy technology is to determine the location of the initial path and the moved path.

In this iterative wiring process, since the determination of the historical cost function has a non-negligible impact on the final wiring result, the present invention proposes a cost function cost(N) based on historical deviations, and the historical cost function increases with the iteration The process is adaptively modified and adjusted. cost(N) is calculated as follows:

Among them, p represents the wiring path; b _e is the wiring cost, which includes the cost of placing the edge; c _t is the congestion cost of the area where the edge is placed; d _t is the bus topology deviation cost.

Among them, ε is a custom parameter; i is the number of iterations; c(e) represents the number of wiring tracks available between adjacent G-Cells, and d(e) represents the number of actually used wiring tracks. b _e will decrease as the number of iterations increases, so as to ensure that the impact of edge placement on routing can be weakened as the iterations progress, so that pin pairs are expected to be routed to areas with small congestion values without short lines. long but excessive congestion. However, for bus pin groups, the decrease in the wire length cost function as iterations progress may cause the bus deviation to increase. Therefore, in order to eliminate this effect as much as possible, the deviation cost d _t is added to the cost function. d _t is calculated as follows:

Among them, α and β are customized parameters, and B is the number of bus line net groups.

The above are only preferred embodiments of the present invention, and are not intended to limit the present invention in other forms. Any skilled person familiar with the art may make changes or modifications to equivalent changes using the technical contents disclosed above. Example. However, any simple modifications, equivalent changes and modifications made to the above embodiments based on the technical essence of the present invention without departing from the content of the technical solution of the present invention still fall within the protection scope of the technical solution of the present invention.

This patent is not limited to the above-mentioned best implementation. Under the inspiration of this patent, anyone can come up with various other forms of bus topology-aware global wiring methods based on multi-strategy. All methods made within the scope of the patent application of this invention are equal. Changes and modifications shall fall within the scope of this patent.

Claims (6)

1. A bus topology-aware global wiring method based on multi-strategy, which is characterized by: in view of the shortcomings of the FLUTE algorithm that leads to an increase in the number of line segments, a reduction in the utilization of wiring space, and the inability to ensure the consistency of the bus topology, a congestion-based topology is adopted Reconstruction strategy seeks a balance point between bus topology consistency and line network length to optimize the wiring plan; In order to solve the problem that hybrid unidirectional monotonic wiring HUMR may cause conflicts in wiring resources, resulting in large topological deviations in the final wiring, a dewiring and redistribution algorithm that considers the bus topology is used to consider the overall congestion when redistributing. value to ensure that the topological deviation between different signal bits can be minimized. 2. The bus topology-aware global wiring method based on multiple strategies according to claim 1, characterized in that: the FLUTE algorithm leads to an increase in the number of line segments and a reduction in the utilization of wiring space, and cannot guarantee the consistency of the bus topology. To overcome the shortcomings, a congestion-based topology reconstruction strategy is adopted to find a balance point between the consistency of the bus topology and the length of the line network to optimize the wiring plan, which specifically includes the following steps: Step 11: Select a group of wire nets with the highest wiring cost; Step 12: Traverse all pseudo-Steiner points in the line network group and confirm the congestion level around them; Step 13: Eliminate the pseudo-Steiner points with the greatest congestion and reconstruct the line network at both ends through the Prim algorithm; Step 14: Remove and redistribute the wire network at both ends constructed in Step 13. 3. The multi-policy based bus topology aware global wiring method according to claim 2, characterized in that: Traverse every pseudo-Steiner point that may be eliminated, calculate the congestion cost V _total based on its two-end line network, and then eliminate the point with the largest congestion cost; V _total is calculated as follows: The degree of congestion is used to calculate the cost function V _path required to construct the line network at both ends. The calculation method is: Among them, path represents the path with the pseudo-Steiner point as the endpoint, e∈path represents each edge in the path, d(e) represents the congestion value of edge e, n represents the number of paths with the pseudo-Steiner point as the endpoint, D( path _i ) represents the sum of the congestion costs of the path, and c(e) represents the capacity of edge e. 4. The bus topology-aware global routing method based on multi-policy according to claim 3, characterized in that: HUMR may cause conflicts in routing resources for mixed unidirectional monotonic routing, resulting in a large topology in the final result. To solve the problem of deviation, we adopt a line-breaking and redistribution algorithm that considers the bus topology. We consider the overall congestion value when redistributing to ensure that the topological deviation between different signal bits can be minimized. This includes the following steps: Step 21: Remove the wiring paths between the selected bus pin pairs and the non-bus pin pairs in the wiring area, and remove the non-bus wiring paths to ensure sufficient wiring space in the wiring area; Step 22: By considering the overall wiring space, select the wiring path with the most sufficient wiring resources for the first signal bit. Each subsequent path is calibrated with the first signal bit path to ensure that the topological deviation and wiring cost are minimized. ; Step 23: Route the remaining non-bus pin pairs to ensure connectivity in the final result. 5. The multi-strategy based bus topology aware global wiring method according to claim 4, characterized in that: In the iterative routing process, the cost function cost(N) based on historical deviations is used, and the historical cost function is adaptively modified and adjusted along with the iterative process; the calculation method of cost(N) is as follows: Among them, p represents the wiring path; b _e is the wiring cost and includes the cost of placing the edge; c _t is the congestion cost of the area where the edge is placed; d _t is the bus topology deviation cost; Among them, ε is a custom parameter; i is the number of iterations; c(e) represents the number of wiring tracks available between adjacent G-Cells, and d(e) represents the number of actually used wiring tracks. 6. The multi-strategy based bus topology aware global wiring method according to claim 5, characterized in that: Add the deviation cost d _t to the cost function; d _t is calculated as follows: Among them, α and β are customized parameters, and B is the number of bus line net groups.