CN115114884B - Multi-strategy optimization-based wiring method for obstacle detouring X structure under time sequence relaxation constraint - Google Patents
Multi-strategy optimization-based wiring method for obstacle detouring X structure under time sequence relaxation constraint Download PDFInfo
- Publication number
- CN115114884B CN115114884B CN202210874384.4A CN202210874384A CN115114884B CN 115114884 B CN115114884 B CN 115114884B CN 202210874384 A CN202210874384 A CN 202210874384A CN 115114884 B CN115114884 B CN 115114884B
- Authority
- CN
- China
- Prior art keywords
- obstacle
- barrier
- steiner
- point
- route
- 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
- 238000005457 optimization Methods 0.000 title claims abstract description 40
- 238000000034 method Methods 0.000 title claims abstract description 17
- 230000004888 barrier function Effects 0.000 claims abstract description 49
- 238000010276 construction Methods 0.000 claims abstract description 10
- KDYFGRWQOYBRFD-UHFFFAOYSA-N succinic acid Chemical compound OC(=O)CCC(O)=O KDYFGRWQOYBRFD-UHFFFAOYSA-N 0.000 claims description 8
- 238000004904 shortening Methods 0.000 claims description 3
- 238000004804 winding Methods 0.000 claims description 3
- 238000004364 calculation method Methods 0.000 claims description 2
- 238000011144 upstream manufacturing Methods 0.000 claims description 2
- 230000000694 effects Effects 0.000 description 3
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000002035 prolonged effect Effects 0.000 description 1
- 230000003068 static effect Effects 0.000 description 1
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/394—Routing
-
- 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/398—Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM]
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Computer Networks & Wireless Communication (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
The invention relates to a wiring method of a barrier-surrounding X structure under time sequence relaxation constraint based on multi-strategy optimization. Comprising the following steps: first, an unobstructed euclidean minimum tree construction strategy is proposed, utilizing the improved Prim algorithm to construct an unobstructed euclidean minimum spanning tree on a pin given by the user. Secondly, a barrier X structure Steiner minimum tree construction strategy is provided. And converting the barrier-free Euclidean minimum tree into an X-structure Steiner minimum tree by selecting a connecting mode, adding pseudo Steiner points according to the intersection points of the connecting lines and the barrier groups, and enabling all the connecting lines to form a barrier-surrounding X-structure Steiner minimum tree. Third, a timing relaxation optimization strategy is proposed. And (3) carrying out local optimization by reasonably utilizing the space in the barrier group, and carrying out redistribution optimization and radius optimization on paths with negative relaxation values to obtain a barrier-surrounding X-structure Steiner minimum tree meeting time sequence relaxation constraint. The invention achieves the optimal result on the worst negative relaxation (Worst NEGATIVE SLACK, WNS) of the most important indicators of the time sequence relaxation constraint.
Description
Technical Field
The invention relates to the technical field of chip design, in particular to a wiring method of a barrier-surrounding X structure under time sequence relaxation constraint based on multi-strategy optimization.
Background
As circuit density in very large scale integrated circuits increases rapidly, their interconnect effect directly affects the final circuit performance during the routing phase of the very large scale integrated circuit physical design. In the design of integrated circuits, the physical design time is longest, and the routing phase is one of the most important flows in the physical design. The advantages and disadvantages of the wiring scheme directly affect the size, operating speed, and power consumption of the chip. Because of wiring obstacles such as macro units, pre-wiring nets and the like in the design of very large scale integrated circuit chips, attention is paid to the problem of wiring of a Steiner minimum tree with obstacle detouring. Meanwhile, as feature sizes of integrated circuit designs become smaller, the proportion of the time delay of the interconnect line in the total time delay is also larger and larger. While conventional wiring generally aims at shortening the bus length, the effect of timing in wiring is ignored. When the wiring scheme cannot meet the time sequence constraint, the physical design period is prolonged, and the design cost of the circuit is increased. Therefore, timing optimization is necessary in the wiring stage.
Disclosure of Invention
The invention aims to provide a wiring method of a barrier-winding X structure under time sequence relaxation constraint based on multi-strategy optimization, which can effectively wind barriers and optimize the line length and WNS so as to optimize the performance of a chip.
In order to achieve the above purpose, the technical scheme of the invention is as follows: a wiring method of a barrier-surrounding X structure under time sequence relaxation constraint based on multi-strategy optimization comprises the following steps:
s1, providing an unobstructed Euclidean minimum tree construction strategy: constructing an unobstructed Euclidean minimum tree on a pin given by a user by utilizing an improved Prim algorithm;
S2, providing a barrier-surrounding X structure Steiner minimum tree construction strategy: selecting a connecting mode to convert an unobstructed Euclidean minimum tree into an X-structure Steiner minimum tree, adding pseudo Steiner points according to the intersection points of the connecting lines and obstacles or obstacle groups, and enabling all the connecting lines to be obstacle-wound to form an obstacle-wound X-structure Steiner minimum tree;
S3, providing a time sequence relaxation optimization strategy: and (3) performing local optimization by utilizing the space in the barrier group, and performing redistribution optimization and radius optimization on the paths with negative relaxation values to obtain the barrier-surrounding X-structure Steiner minimum tree meeting the time sequence relaxation constraint.
Compared with the prior art, the invention has the following beneficial effects: the invention obtains the optimal result on the worst negative relaxation (WorstNegative Slack, WNS) of the most important index of the time sequence relaxation constraint; the invention can effectively detour obstacles and optimize the line length and WNS, thereby optimizing the performance of the chip.
Drawings
Fig. 1 is an unobstructed euclidean minimum tree.
Fig. 2 is 4 choices of pseudo Steiner points.
Fig. 3 is a barrier X structure steper tree.
FIG. 4 is a timing optimized barrier X structure Steiner tree.
Detailed Description
The technical scheme of the invention is specifically described below with reference to the accompanying drawings.
The invention discloses a wiring method of a barrier-surrounding X structure under time sequence relaxation constraint based on multi-strategy optimization, which comprises the following steps:
s1, providing an unobstructed Euclidean minimum tree construction strategy: constructing an unobstructed Euclidean minimum tree on a pin given by a user by utilizing an improved Prim algorithm;
S2, providing a barrier-surrounding X structure Steiner minimum tree construction strategy: selecting a connecting mode to convert an unobstructed Euclidean minimum tree into an X-structure Steiner minimum tree, adding pseudo Steiner points according to the intersection points of the connecting lines and obstacles or obstacle groups, and enabling all the connecting lines to be obstacle-wound to form an obstacle-wound X-structure Steiner minimum tree;
S3, providing a time sequence relaxation optimization strategy: and (3) performing local optimization by utilizing the space in the barrier group, and performing redistribution optimization and radius optimization on the paths with negative relaxation values to obtain the barrier-surrounding X-structure Steiner minimum tree meeting the time sequence relaxation constraint.
The specific implementation example of the invention is as follows:
1. improved Prim algorithm:
The starting source point is set to be the marked point, the set of marked points is V 0, and the set of unmarked points is V 1. In addition to pins p 1, each pin p i corresponds to a dis i, recording the shortest line length of that pin to the other pins. And calculating the distance between the newly added point of V 0 and each point contained in V 1, replacing the numerical value if the distance is smaller than the data of the corresponding dis array, setting the point with the determined connection line as the marked point, adding the minimum subscript in the array to V 0, deleting from V 1 until V 1 is empty, and completing the construction of the barrier-free Euclidean minimum tree as shown in figure 1.
2. Obstacle judgment:
firstly traversing all sides of a Euclidean minimum tree, judging whether the sides pass through barriers, if so (if the number of the passed barriers is greater than 1, combining a plurality of barriers into 1 barrier group), calculating the coordinate positions of pseudo Steiner points which need to be added according to the passed barriers or the barrier group, adding the coordinate positions into an endpoint set of the sides, and continuously judging whether newly added connecting lines pass through the barriers; if each line of the edge does not pass the obstacle, the edge is marked as not passing the obstacle. The barrier boundary is divided into four sides up, down, left and right (the top left corner vertex belongs to the left side, the top right corner vertex belongs to the top side, the bottom right corner vertex belongs to the right side, and the bottom left corner vertex belongs to the bottom side). Some obstacles which are unlikely to intersect with the connecting line are roughly eliminated. Let the coordinates of the two end points of the line segment be (x 1,y1) and (x 2,y2) respectively, so that xmax＝max(x1,x2),xmin＝min(x1,x2),ymax＝max(y1,y2),ymin＝min(y1,y2). when the x coordinate of the top right corner vertex of the obstacle is smaller than x min, the y coordinate is smaller than y min or the x coordinate of the top left corner vertex of the obstacle is larger than x max, and the y coordinate is larger than y max, the line cannot intersect with the obstacle. And because the pins and the pseudo Steiner points are not inside the barrier, the wire passing through the barrier must pass through both sides of the barrier boundary.
3. Selecting a connection mode:
As shown in fig. 2, four connection methods are known between two end points, and if the route 0 or the route 1 does not pass through the obstacle, the route 0 or the route 1 is selected; if both route 0 and route 1 pass the obstacle and either route 2 or route 3 does not pass the obstacle, then route 0 or route 1 is selected (if route 1 passes the obstacle or the obstacle group boundary perimeter is less than route 0, then route 1 is selected, otherwise route 0 is selected); if route 0, route 1, route 2, and route 3 all pass through the obstacle, the one that passes through the obstacle or the shortest perimeter of the obstacle group boundary is selected.
4. Determination of pseudo Steiner points:
calculating the path selection between the two pins by using a path selection algorithm, and directly skipping the connecting line if the connecting line path does not pass through the obstacle after the connecting line mode is determined; if the connection line passes through the barrier group, deleting the pseudo Steiner point in the connection line and connecting the two end points. Calculating two-point coordinates of a connecting line passing through the barrier group, dividing the barrier group into two parts by the connecting line, comparing half circumferences of the barrier group divided into two parts by the connecting line with two pins, selecting the vertex of the half side with the shorter circumference as a pseudo Steiner point, and adding the pseudo Steiner point into an endpoint set of the side. All the wires are traversed to form a barrier-winding X structure Steiner minimum tree, as shown in figure 3.
5. Time sequence relaxation:
The timing analysis is based on static timing analysis (STATICTIMINGANALYSIS, STA), the analysis result of STA is mainly used for evaluating the importance degree of each element and each wire net in a specific layout, the key index is timing relaxation, and when the relaxation value is not negative, the timing constraint of the corresponding node reaches the requirement. Timing optimization requires increasing the negative slack to improve circuit accuracy.
The invention calculates the time delay of the connection line by using an Elmore time delay model. In this model, the wiring is replaced with uniformly distributed pi-type capacitive resistive circuits, where the capacitance on one half of the circuits is at the upstream node and the capacitance on the other half of the circuits is at the downstream node, r 0 and c 0 represent resistance and capacitance per unit length, respectively (r 0＝0.56Ω/μm;c0 =0.48 fF/μm).
The time delay calculation formula of the connection line between the points i and j is as follows
Elmore(i,j)＝∑l∈Path(i,j)r×Ct(l) (1)
Where Path (i, j) represents the Path between points i and j, r represents the resistance of the connection, C t (l) represents the capacitance downstream of point l, the formula is as follows
Ct(i)＝ci+∑n∈succ(i)Ct(n) (2)
Where c i represents the capacitance at i, and succ (i) represents the set of successor nodes of i.
The timing relaxation at a point i can be defined as
Wherein,For the actual arrival time of point i,The required arrival times for point i are respectively expressed as
Where FO (i) is the set of all nodes connected to point i by directed edges.
Where P is all vertices except the source point and WNS is the minimum negative slack.
The time delay of the circuit is calculated by using an Elmore time delay model, and the purpose of increasing the required arrival time and reducing the actual arrival time is achieved by increasing the relaxation value of the pin vertex to reduce the line length as much as possible.
6. Local optimization:
In the constructed barrier-surrounding X structure Steiner minimum tree, if the connecting line passes through a plurality of barriers, the barriers are formed into a barrier group. Local optimization exploits the available space inside the barrier group to further reduce line length. The reduction of the internal wire length of the barrier group can reduce the time delay of the wire connection, thereby increasing the loose value of the pins.
In the obstacle detouring strategy, the number of each connecting line passing through the obstacle is recorded, two pseudo Steiner points added on the boundary of the obstacle group are traversed, and whether the pseudo Steiner points are on the top points of the obstacle or not is judged. If the pseudo Steiner point is not located on the obstacle vertex, deleting the pseudo Steiner point, then starting to search for the obstacle vertex closest to the vertex, and setting the obstacle vertex as the newly added pseudo Steiner point.
7. And (3) heavy distribution optimization:
When the pseudo Steiner point on the boundary of the obstacle group is selected, the circumferences of the obstacle group divided into two parts by the connecting line at this time are selected and compared, and the vertex having the smaller circumference is set as the pseudo Steiner point. However, since the selection of the portion with the smaller circumference does not necessarily select the optimal pseudo Steiner point, the connection line on the critical path needs to be unwound and rewound, and the portion with the larger circumference is used for each step of obstacle detouring, and compared with the time sequence relaxation of the portion with the smaller circumference selected Zhou Changjiao, if the relaxation value is increased, the portion with the longer circumference is selected to add the pseudo Steiner point.
8. Radius optimization:
Since the pin with the negative slack and the worst negative slack is generally on the longest path (i.e., radius) from the source point to the sink point, the slack of the pin on the radius can be increased by shortening the radius.
After constructing the barrier-free Euclidean minimum tree, traversing from a source point, finding a path with a radius, skipping a previous pin from a sink point, directly connecting with the previous pin, comparing the worst negative slack value after updating with the worst negative slack value before updating, and if the worst negative slack value becomes larger, reserving updating, otherwise, not reserving. The vertex before the sink is traversed continuously until the source point.
FIG. 4 is a Steiner tree of a barrier-surrounding X structure after time sequence optimization by the method of the invention.
The above is a preferred embodiment of the present invention, and all changes made according to the technical solution of the present invention belong to the protection scope of the present invention when the generated functional effects do not exceed the scope of the technical solution of the present invention.
Claims (6)
1. A wiring method of a barrier-surrounding X structure under time sequence relaxation constraint based on multi-strategy optimization is characterized by comprising the following steps:
s1, providing an unobstructed Euclidean minimum tree construction strategy: constructing an unobstructed Euclidean minimum tree on a pin given by a user by utilizing an improved Prim algorithm;
S2, providing a barrier-surrounding X structure Steiner minimum tree construction strategy: selecting a connecting mode to convert an unobstructed Euclidean minimum tree into an X-structure Steiner minimum tree, adding pseudo Steiner points according to the intersection points of the connecting lines and obstacles or obstacle groups, and enabling all the connecting lines to be obstacle-wound to form an obstacle-wound X-structure Steiner minimum tree;
S3, providing a time sequence relaxation optimization strategy: carrying out local optimization by utilizing the space in the barrier group, and carrying out redistribution optimization and radius optimization on a path with a negative relaxation value to obtain a barrier-surrounding X-structure Steiner minimum tree meeting time sequence relaxation constraint;
In step S2, the determination method of the pseudo stepiner point is as follows: after determining the connection mode of the two pins, if the connection route does not pass through the obstacle, directly skipping the connection; if the connecting line passes through the obstacle, deleting a pseudo Steiner point in the connecting line, and connecting the two pins; calculating two-point coordinates of a connecting line passing through the obstacle, dividing the obstacle into two parts by the connecting line, comparing half circumferences of the obstacle divided into two parts by the connecting line with two pins, selecting the vertex of the half-side obstacle with the shorter half circumference as a pseudo Steiner point, and adding the pseudo Steiner point into an endpoint set of the corresponding side; traversing all the connecting lines to enable all the connecting lines to be wound, and forming a Steiner minimum tree of a winding obstacle X structure; if the number of the connecting lines passing through the barriers is greater than 1, combining a plurality of barriers into 1 barrier group, and determining the pseudo Steiner points in the same way;
In step S3, the time delay of the connecting line is calculated by using an Elmore time delay model, in the Elmore time delay model, the connecting line is replaced by a pi-type capacitance-resistance circuit which is uniformly distributed, wherein the capacitance on one half of the circuit is positioned at an upstream node, the capacitance on the other half of the circuit is positioned at a downstream node, and r 0 and c 0 respectively represent the resistance and the capacitance of unit length;
The calculation formula of the time delay of the connection line between the points i and j is as follows:
Elmore(i,j)＝∑l∈Path(i,j)r×Ct(l) (1)
Where Path (i, j) represents the Path between points i and j, r represents the resistance of the wire, and C t (l) represents the capacitance downstream of point l, as follows:
Ct(i)＝ci+∑n∈succ(i)Ct(n) (2)
Where c i represents the capacitance at i, and succ (i) represents the set of successor nodes of i;
the timing relaxation at a point i, defined as
Wherein,For the actual arrival time of point i,The required arrival times for point i are expressed as:
Wherein FO (i) is the set of all nodes connected to point i by directed edges;
Calculating the time delay of the circuit by using an Elmore time delay model, and increasing the relaxation value of the pin vertex is to reduce the wire length as much as possible so as to achieve the purposes of increasing the required arrival time and reducing the actual arrival time;
in step S3, the local optimization method is as follows:
In the constructed barrier-surrounding X structure Steiner minimum tree, if the connecting line passes through a plurality of barriers, forming a barrier group by the plurality of barriers; the available space inside the barrier group is utilized in a local optimization mode to further reduce the wire length, and the reduction of the wire length inside the barrier group can reduce the time delay of a connecting wire, so that the loose value of the pins is increased;
Recording the number of each connecting line passing through the obstacle, traversing two pseudo Steiner points added on the boundary of the obstacle group, and judging whether the pseudo Steiner points are on the top points of the obstacle; if the pseudo Steiner point is not located on the obstacle vertex, deleting the pseudo Steiner point, then starting to search for the obstacle vertex closest to the vertex, and setting the obstacle vertex as the newly added pseudo Steiner point.
2. The routing method of the barrier X structure under the timing relaxation constraint based on multi-strategy optimization according to claim 1, wherein in step S1, the manner of constructing the barrier-free euclidean minimum tree on the pins given by the user by using the modified Prim algorithm is as follows: setting a starting source point as a marked point, setting a set of marked points as V 0, and setting a set of unmarked points as V 1; each pin p i corresponds to one dis [ i ] except for the pin p 1, and the shortest line length from the corresponding pin to other pins is recorded; and calculating the distance between the newly added point of V 0 and each point contained in V 1, replacing the numerical value if the distance is smaller than the data of the corresponding dis array, setting the point with the determined connection line as the marked point, adding the minimum subscript in the array to V 0, deleting from V 1 until V 1 is empty, and completing the construction of the barrier-free Euclidean minimum tree.
3. The routing method of the barrier-surrounding X structure under the time sequence relaxation constraint based on multi-strategy optimization according to claim 1, wherein in the step S2, barrier judgment is required to be carried out on a barrier-free Euclidean minimum tree constructed in the step S1, namely: traversing all sides of the barrier-free Euclidean minimum tree, judging whether the corresponding sides pass barriers, combining a plurality of barriers into 1 barrier group if the number of the passed barriers is larger than 1, if the corresponding sides pass the barriers, calculating the coordinate positions of pseudo Steiner points which need to be added according to the barriers or the barrier groups passed by the corresponding sides, adding the coordinate positions into an endpoint set of the corresponding sides, and continuously judging whether newly added connecting lines pass the barriers; and marking the corresponding edge as not passing through the obstacle if each connecting line of the corresponding edge does not pass through the obstacle.
4. The wiring method of the obstacle detouring X structure under the time sequence relaxation constraint based on the multi-strategy optimization according to claim 1, wherein in the step S2, the connection mode is selected by: four connection modes are known between the two pins, and if the route 0 or the route 1 does not pass through the obstacle, the route 0 or the route 1 is selected; if both route 0 and route 1 pass the obstacle and either route 2 or route 3 does not pass the obstacle, selecting either route 0 or route 1, wherein route 1 is selected if route 1 passes the obstacle or the obstacle set boundary perimeter is less than route 0, otherwise route 0 is selected; if route 0, route 1, route 2 and route 3 all pass through the obstacle, selecting the route with the shortest perimeter of the obstacle or obstacle group boundary; the obstacle group is a combination of a plurality of obstacles in the case where the number of the link lines passing through the obstacle is greater than 1.
5. The routing method of the obstacle detouring X structure under the time sequence relaxation constraint based on the multi-strategy optimization according to claim 1, wherein in the step S3, the re-distribution optimization mode is as follows:
When the pseudo Steiner points on the boundary of the barrier group are considered to be selected, the perimeter of the barrier group divided into two parts by the connecting line at the moment is selected and compared, and the vertex with the smaller perimeter is set as the pseudo Steiner point; however, since the portion with smaller circumference is not necessarily selected to be the optimal pseudo Steiner point, the connection line on the corresponding path needs to be unwound and rewound, and the portion with larger circumference is used for each step of obstacle detouring, and compared with the time sequence relaxation of the portion with smaller circumference being selected Zhou Changjiao, if the relaxation value is increased, the portion with longer circumference is selected to be added with the pseudo Steiner point.
6. The routing method of the obstacle detouring X structure under the time sequence relaxation constraint based on the multi-strategy optimization according to claim 1, wherein in the step S3, the radius optimization mode is as follows:
since the pin with the negative slack and the worst negative slack is on the longest path from the source point to the sink point, i.e., the radius, the slack of the pin on the radius is increased by shortening the radius;
After constructing an unobstructed Euclidean minimum tree, traversing from a source point, finding a path with a radius, skipping a previous pin from a sink point, directly connecting with the previous pin, comparing the worst negative relaxation value after updating with the worst negative relaxation value before updating, and if the worst negative relaxation value is bigger, reserving updating, otherwise, not reserving; the vertex before the sink is traversed continuously until the source point.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210874384.4A CN115114884B (en) | 2022-07-22 | 2022-07-22 | Multi-strategy optimization-based wiring method for obstacle detouring X structure under time sequence relaxation constraint |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210874384.4A CN115114884B (en) | 2022-07-22 | 2022-07-22 | Multi-strategy optimization-based wiring method for obstacle detouring X structure under time sequence relaxation constraint |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN115114884A CN115114884A (en) | 2022-09-27 |
| CN115114884B true CN115114884B (en) | 2024-06-25 |
Family
ID=83334823
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210874384.4A Active CN115114884B (en) | 2022-07-22 | 2022-07-22 | Multi-strategy optimization-based wiring method for obstacle detouring X structure under time sequence relaxation constraint |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN115114884B (en) |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110795907A (en) * | 2019-09-30 | 2020-02-14 | 福州大学 | X-structure Steiner minimum tree construction method considering wiring resource relaxation |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111723544A (en) * | 2020-06-18 | 2020-09-29 | 福州大学 | Steiner tree construction method considering barrier internal wiring under X structure |
| CN112528592B (en) * | 2020-12-23 | 2022-06-14 | 福州大学 | Multi-stage optimization-based X-structure wiring method considering wiring resource relaxation |
| CN112733484B (en) * | 2021-01-22 | 2022-06-14 | 福州大学 | X-structure Steiner tree construction method under Slew constraint based on multi-strategy optimization |
| CN113935275A (en) * | 2021-10-12 | 2022-01-14 | 福州大学 | Construction method of barrier X structure Steiner minimum tree under time sequence relaxation constraint |
-
2022
- 2022-07-22 CN CN202210874384.4A patent/CN115114884B/en active Active
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110795907A (en) * | 2019-09-30 | 2020-02-14 | 福州大学 | X-structure Steiner minimum tree construction method considering wiring resource relaxation |
Non-Patent Citations (1)
| Title |
|---|
| 考虑布线资源松弛的X结构Steiner最小树算法;汤浩;刘耿耿;郭文忠;陈国龙;;模式识别与人工智能;20200515(第05期);第401-412页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN115114884A (en) | 2022-09-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4227304B2 (en) | Outline wiring method and apparatus, and recording medium storing outline wiring program | |
| US6442745B1 (en) | Method and apparatus for layout-constrained global routing | |
| US6009248A (en) | Delay optimization system to conduct optimization for satisfying delay constraints on the circuit and method therefor | |
| US6671864B2 (en) | Method and apparatus for using a diagonal line to measure an attribute of a bounding box of a net | |
| US9665679B2 (en) | Systems and methods for designing integrated circuits with consideration of horizontal and vertical wiring demand ratios | |
| US6516455B1 (en) | Partitioning placement method using diagonal cutlines | |
| WO2021082867A1 (en) | Skew-driven global wiring method employing bus sensing | |
| US9817941B2 (en) | Methods, systems, and articles of manufacture for implementing high current carrying interconnects in electronic designs | |
| JPH10335472A (en) | Method and device for designing layout | |
| JP2003016131A (en) | Method and device for interconnection | |
| Held et al. | Global routing with timing constraints | |
| CN111553125A (en) | Ultra-large-scale integrated circuit detailed wiring method considering advanced technology | |
| Hsu et al. | Multi-layer global routing considering via and wire capacities | |
| CN104063558A (en) | Large scale integrated circuit path wiring method based on linear programming | |
| CN117556758A (en) | FPGA layout wiring method for optimizing time sequence | |
| CN115114884B (en) | Multi-strategy optimization-based wiring method for obstacle detouring X structure under time sequence relaxation constraint | |
| CN112985443A (en) | Path planning method and device and terminal equipment | |
| US6567966B2 (en) | Interweaved integrated circuit interconnects | |
| Kao et al. | Cross point assignment with global rerouting for general-architecture designs | |
| Liu et al. | High-quality global routing for multiple dynamic supply voltage designs | |
| Daboul et al. | Global interconnect optimization | |
| CN116888599A (en) | Method and device for layout of circuit units of integrated circuit | |
| JP3530025B2 (en) | Schematic wiring determination method and storage medium | |
| Zuber et al. | Wire topology optimization for low power CMOS | |
| Bai et al. | An effective detailed routing algorithm considering advanced technology nodes |
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 |