CN112560389A

CN112560389A - Practical detailed wiring method based on track distribution

Info

Publication number: CN112560389A
Application number: CN202011551905.XA
Authority: CN
Inventors: 刘耿耿; 敬祎丹; 庄震; 黄兴; 郭文忠; 陈国龙
Original assignee: Fuzhou University
Current assignee: Fuzhou University
Priority date: 2020-12-24
Filing date: 2020-12-24
Publication date: 2021-03-26
Anticipated expiration: 2040-12-24
Also published as: CN112560389B

Abstract

The invention relates to a practical detailed wiring method based on track distribution, which comprises the following steps of obtaining an initial wiring scheme by adopting a track distribution algorithm; optimizing an initial wiring scheme by adopting a disconnection rewinding technology; optimizing the short-circuit area; and repairing the optimized result of the short circuit area, and optimizing the overlapped through holes to obtain a final wiring scheme. The invention can generate a detailed wiring scheme with higher quality.

Description

Practical detailed wiring method based on track distribution

Technical Field

The invention relates to the technical field of integrated circuit computer aided design, in particular to a practical detailed wiring method based on track distribution.

Background

Due to complexity, the wiring is usually divided into two stages, overall wiring and detailed wiring. In the global routing stage, a local area is selected as a routing guide for detailed routing. In the detailed routing phase, the pins of each net are connected together according to the guidelines. Design rule constraints are constantly changing as VLSI technology nodes evolve. Since detailed routing is the final stage of routing, design rule constraints need to be optimized as much as possible. Detailed routing becomes one of the most complex and time consuming stages.

Today, many global routers have been proposed, including FastRoute 4.0, CUGR, NCTUGR 2.0, and so forth. It is necessary to propose efficient detailed routers. To meet manufacturing requirements, many detailed routers have been proposed, such as dr. cu 2.0. However, many existing detailed routers do not adequately address the design rule constraints being considered. In 2018 and 2019, the ISPD contest was given detailed wiring propositions by Cadence, one of the three major EDA companies worldwide. Since then, many research efforts have emerged to distribute circuit optimization design rule constraints based on Cadence, including detailed labyrinthine routing-based routers, detailed ILP-based routers, and the like.

As detailed routing issues become more complex, and net densities become greater, the results of overall routing become increasingly difficult to match with the requirements of detailed routing. Therefore, both academia and industry try to introduce a track allocation method as an initial stage of detailed wiring in a detailed wiring process to make up for the mismatch between the overall wiring and the detailed wiring as much as possible. Previous work often overlooked local networks and network connectivity, resulting in inaccurate guidance of detailed wiring. Recently, some routability-driven track allocation algorithms have been proposed. Considering a negotiation-based track allocation algorithm for local networks, all wire segments extracted from the overall wiring scheme are allocated to the appropriate tracks with the goal of minimizing the overlap between the different components. A grid-by-grid trajectory allocation algorithm that considers local networks and network connectivity may guarantee connectivity for each network by minimizing the mismatch between trajectory allocation and detailed routing. The routability of the design can be effectively analyzed by considering the rapid channel-by-channel track distribution algorithm of network connectivity. In addition, a track allocation algorithm based on negotiation is integrated, and a detailed wiring scheme is effectively generated. However, in track assignment, many interrelated processes (including pin access and connection of wire segments) are handled separately, greatly affecting the routability of the final detailed routing scheme.

Disclosure of Invention

In view of the above, the present invention provides a practical detailed wiring method based on track allocation, which can generate a detailed wiring scheme with higher quality.

The invention is realized by adopting the following scheme: a practical detailed wiring method based on track distribution specifically comprises the following steps:

obtaining an initial wiring scheme by adopting a track distribution algorithm;

optimizing an initial wiring scheme by adopting a disconnection rewinding technology;

optimizing the short-circuit area;

and repairing the optimized result of the short circuit area, and optimizing the overlapped through holes to obtain a final wiring scheme.

Further, the obtaining of the initial wiring solution by using the track allocation algorithm specifically includes the following steps:

constructing a track allocation map for each network in the routing guide;

and selecting a proper track by adopting a maze wiring algorithm of design rule constraint perception based on the track distribution diagram to perform wiring to obtain an initial wiring scheme.

Further, the optimizing the initial wiring scheme by using the rewiring technology specifically includes:

in each iteration process, selecting a grid with violation, and widening the wiring guide of the violation grid by one width in four directions to expand a search space; then, based on the extended wiring guidance, a better wiring scheme is found by using a maze wiring algorithm sensed by a design rule; when no violation mesh can be optimized, the disconnect rewind phase is ended.

Further, the optimizing the short-circuit area specifically includes:

wire segments with crossing portions are first selected and then the topology of the net is relaxed by interlayer migration of the wire segments to find a more optimal routing scheme.

Further, the optimizing the short-circuit area specifically includes the following steps:

step S1: initializing the short circuit wire segment pair set SP as empty;

step S2: searching all adjacent wire segments s' of the wire segments s in the wiring plan DRP;

step S3: adding the short-circuited conductor segment pairs ss' into the set SP;

step S4: removing pairs of wire segments in the set SP from the routing plan DRP;

step S5: initializing a newly-added cost minimum value mc to be infinite;

step S6: carrying out layer migration combination on the short circuit wire segment pairs;

step S7: calculating the newly added cost of the current layer migration scheme;

step S8: judging whether the newly added cost is less than mc; if yes, go to step S9, otherwise go to step S10;

step S9: recording a current layer migration scheme, and updating mc;

step S10: judging whether a combination scheme of all layer migration is completed; if yes, go to step S11, otherwise, go back to step S6;

step S11: adding the recorded layer migration scheme to the wiring scheme DRP;

step S12: judging whether layer migration is finished for all short-circuit lead segment pairs, if so, ending the short-circuit area optimization stage; otherwise, the process returns to step S5.

Further, in the step S7, the current layer migration scheme includes a scheme of allocating the wire segment S to the m1 layer through via connection and a scheme of allocating the wire segment S' to the m2 layer through via connection; the calculation of the new cost ec adopts the following formula:

where R and R represent the design rule constraint and the set of design rule constraints without the minimum area constraint, respectively. W_rDenotes the weight of r, V_rRepresenting the number of design rule constraint r violations. In particular, V is constrained for the short circuit area_rIndicating the area of the short circuit.

Further, the repairing is performed on the optimized result of the short circuit region, and the overlapped through holes are optimized, so that the final wiring scheme is specifically:

and patching the positions of the through holes of all metal layers between the migrated wire section and the connected wire section, wherein the sizes of all patches are calculated based on the default direction of the metal layer.

Further, if the patched and rectangles of other nets generate a problem of design rule constraint violation, the metal layer is not patched.

Compared with the prior art, the invention has the following beneficial effects: in the post-optimization stage, the problem of design rule constraint violation generated in a local area can be effectively optimized by adopting the stitch-removing rewinding technology; meanwhile, interlayer migration is carried out on the short-circuited conducting wire section, and a short-circuit area conducting wire migration technology is designed, so that the short-circuit problem can be effectively eliminated, and the short-circuit area is reduced; meanwhile, after the track distribution scheme is determined, still some rectangles of the conducting wire segments or the through holes on the metal layer violate the minimum area constraint.

Drawings

FIG. 1 is a general flow chart of a router according to an embodiment of the present invention.

Fig. 2 is a flowchart of a short-circuit area wire migration algorithm according to an embodiment of the present invention.

Fig. 3 is a diagram of track allocation constructed in accordance with an embodiment of the present invention. The method comprises the following steps of (a) obtaining a wiring guide area diagram, (b) obtaining a wiring guide area connection relation diagram, and (c) obtaining a track allocation diagram.

Fig. 4 is a schematic diagram illustrating pin connection point selection according to an embodiment of the invention. Wherein, (a) is a pin layout diagram, and (b) is a pin connection point schematic diagram.

Fig. 5 is a schematic diagram illustrating a construction of a wiring pattern in a rewinding process of removing a wire according to an embodiment of the present invention. Wherein, (a) the wire net layout diagram, and (b) the wiring diagram of the labyrinth wiring.

Fig. 6 is a schematic diagram of a short-circuit region wire migration according to an embodiment of the invention. Wherein, (a) is a schematic diagram of the short circuit area, and (b) is a schematic diagram of the short circuit area after repair.

Fig. 7 is a schematic diagram of minimum area optimization according to an embodiment of the present invention. Wherein, (a) is a through hole position diagram, and (b) is a patch schematic diagram.

Detailed Description

The invention is further explained below with reference to the drawings and the embodiments.

It should be noted that the following detailed description is exemplary and is intended to provide further explanation of the disclosure. Unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this application belongs.

It is noted that the terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of example embodiments according to the present application. As used herein, the singular forms "a", "an" and "the" are intended to include the plural forms as well, and it should be understood that when the terms "comprises" and/or "comprising" are used in this specification, they specify the presence of stated features, steps, operations, devices, components, and/or combinations thereof, unless the context clearly indicates otherwise.

As shown in fig. 1, the present embodiment provides a practical detailed wiring method based on track allocation, where input data of the process is a guide area file, a rule base file, a design file, and output data is a detailed wiring scheme. The process comprises two sub-processes, namely an orbit allocation process and a post-optimization process. The method specifically comprises the following steps:

obtaining an initial wiring scheme by adopting a track distribution algorithm;

optimizing the short-circuit area;

In this embodiment, the obtaining of the initial wiring solution by using the track allocation algorithm specifically includes the following steps:

a first step of constructing a track allocation map for each network in a routing guide;

and secondly, selecting a proper track for wiring by adopting a maze wiring algorithm of design rule constraint perception based on the track distribution diagram to obtain an initial wiring scheme.

Specifically, in the stage of building the track allocation map, the connection relationship of the routing guide area is determined first, and the connectivity of the track allocation map is ensured, so that the pins of the net can be connected together in the subsequent selective track allocation process. In order to enable the wire segments in the routing scheme to be routed in the default direction of each layer as much as possible so that the routing scheme satisfies the routing priority constraint, the step connects the routing guide areas together through the through holes between the layers. Only when all the wiring guide areas cannot be connected into a connected network structure by the through holes, the wire sections in the non-default direction are used for connecting the connected wiring guide areas on the same layer. FIG. 3 is a schematic diagram showing the routing guide area connections of a net. FIG. 3 (a) is a layout diagram of a routing guide region, in which G_i,jRepresents the jth routing guide region, P, of the net on the ith metal layer_i,jThe jth pin of the ith rectangle of the net is represented, and the dashed lines represent the tracks within the routing guide area. FIG. 3 (b) is a connection diagram of the wiring guide region, and FIG. 3 (b) is a diagram of connection relationship between the wiring guide regionsThe five wiring guide regions shown in (a) are connected together by five through holes, V_i,jA jth via connected to an ith layer, which is a wiring layer to which a lower end of the via is connected, is shown.

After the connection relation of the wiring guide area is determined, the track distribution diagram can be established according to the connection relation. The track allocation map comprises three nodes: rail node, pin over-point and via over-point. The through hole over-point includes a plurality of choices, and the through hole position actually includes n × m choices provided that the number of tracks of the upper and lower layers determining the position thereof is n and m, respectively. However, for the structure of the track distribution diagram, once the track nodes on both sides of the through hole over point are determined, a unique through hole position is selected, so that the track distribution diagram provided by the invention abstracts the through holes in the connection relation of the routing guide area into the through hole over point. In addition, each pin also includes a plurality of pin connection points. However, by performing the track allocation based on the track allocation map and the maze routing algorithm, once the path searches for a suitable pin connection point, the track allocation process is completed, and the pin connection point does not need to be specially selected. Therefore, the track allocation map presented by the present invention also abstracts each pin as a pin over-point. Fig. 3 (c) shows a track allocation map corresponding to the connection relationship of fig. 3 (a). P_i,j、T_i,j,k、V_i,jRespectively representing pin over-points, rail nodes and via over-points. Since the track allocation map in (c) of fig. 3 is constructed based on the connection relationship in (b) of fig. 3, P_i,jCorresponds to the pin P in (b) of FIG. 3_i,j，V_i,jCorresponds to the through-hole V in (b) of FIG. 3_i,j，T_i,j,k corresponds to the wiring guide region G in FIG. 3 (b)_i,jThe k-th track of (2).

And secondly, taking the adjacent two layers of tracks into consideration, and extracting the track intersection points, in which the pins are located and the periphery of the track intersection points do not conflict with other graphs, as the pin connection points. Fig. 4 shows a pin connection point selection diagram. FIG. 4 (a) shows a pin layout diagram showing the pin and routing guide areas for nets on a first layer and first and second layersA layer track. P_iThe marked rectangle is a pin of the wire net, G_i,jThe rectangle indicated is the routing guide area for the net, the horizontal dashed lines indicate the first layer of tracks and the vertical dashed lines indicate the second layer of tracks. FIG. 4 (b) shows the corresponding pin connection point of FIG. 4 (a), wherein the square represents pin P₁Pin connection point of (2), circle represents pin P₂Pin connection point of (1), the triangle representing pin P₃Is connected to the pin. Based on the track distribution diagram, a high-quality track distribution scheme can be obtained through an effective maze routing algorithm. In the invention, a design rule-aware labyrinth wiring algorithm is adopted to obtain a track distribution solution.

Preferably, the post-optimization stage of this embodiment includes three steps, and the first step optimizes the routing scheme by using the wire-disconnecting rewinding technique. The second step is a short-circuit area wire transfer technology, which is used for carrying out interlayer transfer on the short-circuit wire segment, thereby effectively eliminating the short-circuit problem and reducing the short-circuit area. The third step is overlap via optimization to reduce short circuit violations and minimize area violations.

In the embodiment, the problem of poor flexibility of the track distribution algorithm in wiring in the local area is solved by using a design rule constraint perception disconnection rewinding technology, so that the number of problems violating the design rule constraint is reduced, and the quality of chip design is improved. In the post-optimization stage, the present embodiment performs the rewiring on the nets generating the violation problem of the design rule constraint by using the rewiring technology, so as to optimize the violation problem of the local design rule constraint, which is difficult to avoid in the initial track allocation stage. While DTA can achieve a high quality initial solution, it is not easy to locally reduce design rule violations. Therefore, in the first step of the post-optimization stage, a lane-breaking rewind technique is employed to reduce area violations. In each iteration process, firstly, a wiring diagram is constructed in a wiring guide area for a wire mesh needing design rule constraint optimization, then labyrinth wiring is carried out based on the wiring diagram, and finally effective post-processing operation is carried out. Fig. 5 shows a schematic diagram of the wiring pattern construction during the unwinding rewinding process. FIG. 5 (a) shows a net layout. G_i,jRepresents the jth routing guide region, P, of the net on the ith metal layer_i,jThe jth pin of the ith rectangle of the net is represented, and the dashed lines represent the tracks within the routing guide area. Fig. 5 (b) shows a wiring diagram corresponding to fig. 5 (a). The wiring diagram constructed by the disconnection and rewinding comprises three sides: a via, a default direction edge, and a non-default direction edge. And constructing a node at the intersection point of the layer and the track of the adjacent layer for each wiring guide area. Then, all nodes of the net are connected by using the through holes, the default direction edges and the non-default direction edges to form a wiring diagram. However, for the wiring diagram of the rewiring maze wiring, some nodes and edges need to be deleted on the basis of the wiring diagram to improve the efficiency of the algorithm, so that the wiring diagram only reserves the nodes and non-default direction edges of the overlapping part of the wiring guide areas of two adjacent layers and combines the default direction edges.

The method for optimizing the initial wiring scheme by adopting the disconnection rewinding technology specifically comprises the following steps:

in each iteration process, selecting a grid with violation, and widening the wiring guide of the violation grid by one width in four directions to expand a search space; then, based on the extended wiring guidance, a better wiring scheme is found by using a maze wiring algorithm sensed by a design rule; the intersection positions of the tracks on the adjacent metal layers are extracted as nodes of the wiring pattern for the maze wiring. The artwork has three edge types including via, default directional edge and non-default directional edge. The vias are used to connect nodes on adjacent metal layers. The default direction edges are used to connect nodes in the same routing guide according to the preferred routing direction of their metal layers. The non-default directional edges are used to connect nodes connected by vias along orthogonal directions that follow the preferred routing direction. Based on the wiring diagram, the violation behaviors can be effectively reduced through a maze wiring algorithm. Edge e in the artwork for efficient integration of the negotiation scheme into the iterative process_iThe cost of (c) is calculated as follows:

wherein hc is_iRepresenting a violation e_iHistorical cost of, rc_iRepresents the edge e_iM and M represent the routing index and the set of routing metrics, respectively. Wherein W_mAnd V_mRespectively representing the weight of m and the value of m.

When no violation mesh can be optimized, the disconnect rewind phase is ended. After the rewiring phase, there are often some conflicts, especially short conflicts, that cannot be reduced in the routing guide. Because short circuit is a very important wiring index, a short circuit area wire migration algorithm is provided to reduce short circuit conflicts in the optimization stage of the short circuit area. In the short circuit area caused by two overlapping wire segments, they can migrate to different metal layers outside the trace guide to reduce the number of shorts and the area of shorts.

In this embodiment, the optimizing the short-circuit area specifically includes:

Specifically, as shown in fig. 2, the optimizing the short-circuit area specifically includes the following steps:

step S1: initializing the short circuit wire segment pair set SP as empty;

step S5: initializing a newly-added cost minimum value mc to be infinite;

step S9: recording a current layer migration scheme, and updating mc;

step S11: adding the recorded layer migration scheme to the wiring scheme DRP;

Preferably, the inputs of the algorithm are net set N and a routing plan DRP containing all the graphs in the routing area, and the output is an updated routing plan DRP. The various rectangles in the DRP are stored in a form of a balanced binary search tree. The first step initializes a set SP of shorted conductor segment pairs to be empty, each shorted conductor segment pair comprising two conductor segments with an overlap region between the two conductor segments causing a short circuit. The second to third steps search all pairs of short-circuited conductor segments. The process searches each wire segment s in the wire segment set Sn for each net n, and each wire segment s' around s in the wiring scheme DRP in turn. The segments of wire around s are obtained from a balanced binary search tree. If a short circuit occurs between two conductor segments, the short-circuited conductor segment pair is stored in the SP. The fourth step through the last step processes each short-circuit wire segment pair in turn. The fourth step removes the shorted wire segment pairs sp from the routing plan DRP. The fifth step initializes the new cost minimum cm of the new wiring scheme to infinity. The sixth step to the ninth step consider all combination schemes of layer migration of two short-circuited conductor segments, and assuming that the number of layers of the wiring area is l, there are l × l combination modes. Since the number of metal layers will not typically exceed ten, considering all combination schemes does not result in a substantial increase in run time. The seventh step calculates a new cost of the scheme p of the current layer migration, p1 represents a scheme of distributing the wire segment s to the m1 layer through via connection, p2 represents a scheme of distributing the wire segment s' to the m2 layer through via connection, p includes p1 and p2, and mc represents the new cost. And the eighth step of judging whether the newly added cost of the current scheme p is less than mc or not, and if the newly added cost of the current scheme p is less than mc, recording the current optimal layer migration scheme p and updating mc. The eleventh step adds the optimal layer migration scheme to the wiring scheme DRP. Wherein m1 is the number of metal layers to which the first wire s is assigned, and if n metal layers are shared, the value range of m1 is 1 to n; m2 is the number of metal layers to which the second wire s' is assigned.

In this embodiment, in the step S7, the current layer migration scheme includes a scheme of allocating the wire segment S to the m1 layer through via connection and a scheme of allocating the wire segment S' to the m2 layer through via connection; the calculation of the new cost ec adopts the following formula:

Preferably, for a detailed wiring scheme, the quality is evaluated according to the criteria published by the ISPD contest in 2019. Each routing metric is given a weight to each cell. A score of the wiring plan is calculated from the wiring index. The present embodiment works to minimize the score of the routing scheme as follows:

in the formula, M and M represent a wiring index and a wiring metric set, respectively. Wherein W_mAnd V_mRespectively representing the weight of m and the value of m. In particular, for the line length index V_mIndicating the length of the wire, for the number of vias V_mIndicating the number of vias.

Fig. 6 provides a schematic illustration of a short-circuited area wire migration technique. FIG. 6 (a) is a schematic view of a short-circuit region where two conductor segments S1 and S2 at the first layer occurThe overlap results in a short circuit, the overlap area being represented by a cross-hatched rectangle. Fig. 6 (b) is a schematic diagram after repairing the short-circuited region problem. For the sake of illustration, it is assumed here that the conductor segment S is₂Migration to the second layer does not cause other problems to occur that violate the design rule constraints. By cutting the conductor section S₂Migration to the second layer may avoid the occurrence of shorts while reducing the number of violations of the short constraint and the area of the short. In order to ensure connectivity while transferring the wire segments, through holes are added simultaneously to maintain connection. As shown in fig. 6 (b), in order to transfer the wire segment S2 to the second layer, through holes V need to be added to both ends of the wire segment₁And V₂And ensuring connectivity. This technique is essentially based on the relaxation of the wire mesh topology on the basis of the wire segments, which, although it leads to an increase in the number of vias, can effectively avoid the occurrence of short-circuit problems. Therefore, an increased number of vias is acceptable.

The short circuit number and the short circuit area can be effectively reduced through the short circuit area wire migration technology, and meanwhile, the number of violations of other design rule constraints is not greatly increased. The short circuit is used as an important constraint for measuring the connectivity of the wire network, and the significance for repairing the short circuit problem is very important. Therefore, this optimization strategy is very efficient and necessary. Although interlayer migration of the wire segments can effectively reduce the short circuit problem, migration of the wire segments across multiple layers can cause interconnection of multiple through holes, and further cause violation of minimum area constraints on metal layers connected by the through holes. In order to avoid the degradation of the minimum area constraint index generated when the short circuit problem is optimized, the invention provides a repair strategy aiming at the short circuit region wire migration technology. This strategy avoids violating the minimum area constraint by patching the metal layer in which the via is located.

In this embodiment, the repairing is performed on the optimized result of the short-circuit region, and the overlapped through holes are optimized, so as to obtain a final wiring scheme specifically as follows:

In this embodiment, if the rectangular shapes of the patch and other nets violate the design rule constraint, the metal layer is not patched.

Figure 7 gives a schematic illustration of patching. Fig. 7 (a) shows the positions of the vias in a certain layer and the rectangles of other surrounding nets after the transition between the conductor segments. V_iDenotes the ith overlapping via, VP_iRepresents V_iLocation of (2), R_iRepresents V₁The ith rectangle to which the other surrounding nets belong. len (a)_IIs shown in VP_iIn the direction of increasing coordinate of the default direction of the metal layer, VP_iAnd all R_iMinimum positive distance of (len)_DIs shown in VP_iIn the direction of decreasing coordinates of the default direction of the metal layer, VP_iAnd all R_iIs measured. Default routing direction coordinate increasing direction distance wpl_IDefault routing direction coordinate decreasing direction distance wpl_DIncreasing the direction distance wnpl to the non-default direction coordinate_IAnd a non-default directional coordinate decreasing the directional distance wnpl_DThe calculation of (c) is as follows:

wnpl_I＝wnpl_D＝defaultWidth/2；

wherein defaultWidth represents the default width of the metal layer. minArea represents the minimum legal area of the metal layer.

Fig. 7 (b) shows a schematic diagram of a via Patch, and Patch1 represents the Patch as printed, as shown by the rectangle of the grid pattern. The positioning position of the patch is consistent with the position of the through hole, and the distances from the positioning position to the four sides of the patch are wpl_I、wpl_D、wnpl_IAnd wnpl_D. The four distances respectively represent default routing directionsIncreasing the direction distance to the coordinate, decreasing the direction distance of the default routing direction coordinate, increasing the direction distance of the non-default direction coordinate and decreasing the direction distance of the non-default direction coordinate.

As will be appreciated by one skilled in the art, embodiments of the present application may be provided as a method, system, or computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.

The present application is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the application. It will be understood that each flow and/or block of the flow diagrams and/or block diagrams, and combinations of flows and/or blocks in the flow diagrams and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

The foregoing is directed to preferred embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow. However, any simple modification, equivalent change and modification of the above embodiments according to the technical essence of the present invention are within the protection scope of the technical solution of the present invention.

Claims

1. a practical detailed wiring method based on track distribution, is characterized in that, comprises the following steps:

The initial routing scheme is obtained by using the track allocation algorithm;

Optimize the initial wiring scheme by using the wire removal and rewinding technology;

Optimize the short-circuit area;

Repair the results of the optimization of the short-circuit area, and optimize the overlapping vias to obtain the final routing scheme.

2. a kind of practical detailed wiring method based on track allocation according to claim 1, is characterized in that, described adopting track allocation algorithm to obtain initial wiring solution specifically comprises the following steps:

Construct the track assignment map for each net in the routing guide;

Based on the track allocation diagram, the design rule constraint-aware labyrinth routing algorithm is used to select the appropriate track for routing, and obtain the initial routing scheme.

3. A kind of practical detailed wiring method based on track allocation according to claim 1, it is characterized in that, described adopting wire removal and rewinding technology to optimize the initial wiring scheme is specifically:

During each iteration, grids with violations are selected and the routing guidelines of the offending grids are widened by one width in four directions to expand the search space; then, based on the extended routing guidelines, design rule-aware Labyrinth routing algorithm to find a better routing scheme; when there are no offending meshes to optimize, end the unwinding and rewinding phase.

4. A practical detailed wiring method based on track allocation according to claim 1, wherein the optimization of the short-circuit area is specifically:

Firstly, the wire segments with crossed parts are selected, and then a better wiring scheme is found by migrating the topology of the slack wire mesh between layers of the wire segments.

5. A practical detailed wiring method based on track allocation according to claim 4, wherein the optimization of the short-circuit area specifically comprises the following steps:

Step S1: initialize the short-circuit wire segment pair set SP to be empty;

Step S2: Search all adjacent wire segments s' of the wire segment s in the wiring scheme DRP;

Step S3: adding the short-circuited wire segment pair ss' to the set SP;

Step S4: remove the wire segment pairs in the set SP from the wiring scheme DRP;

Step S5: Initialize the newly added cost minimum value mc to be infinite;

Step S6: performing layer migration combination on the short-circuit wire segment pair;

Step S7: Calculate the new cost of the current layer migration scheme;

Step S8: determine whether the newly added cost is less than mc; if so, go to step S9, otherwise go to step S10;

Step S9: record the current layer migration scheme, and update mc;

Step S10: judge whether the combination scheme of all layer migrations is completed; if so, go to step S11, otherwise, return to step S6;

Step S11: adding the recorded layer migration scheme to the wiring scheme DRP;

Step S12: Determine whether the layer migration is completed for all short-circuit wire segment pairs, and if so, end the short-circuit area optimization stage; otherwise, return to step S5.

6. A practical detailed wiring method based on track allocation according to claim 5, characterized in that, in the step S7, the current layer migration scheme comprises a scheme of allocating the wire segment s to the m1 layer through a via connection and The scheme of allocating the wire segment s' to the m2 layer through the through-hole connection; the calculation of the new cost ec adopts the following formula:

where r and R represent the design rule constraint and the set of design rule constraints without minimum area constraints, respectively. W _r represents the weight of r, and V _r represents the number of violations of the design rule constraint r.

7. A practical detailed wiring method based on track allocation according to claim 1, characterized in that, the results of the optimization for the short-circuit area are repaired, and the overlapping vias are optimized to obtain the final wiring scheme specifically:

Patch the via positions of all metal layers between the migrated wire segment and its connected wire segment. The size of all patches is calculated based on the default orientation of the metal layer.

8. A practical detailed routing method based on track allocation according to claim 7, characterized in that, if the patch and the rectangle of other nets produce a problem of design rule constraint violation, the metal layer is not patched .