CN1304996C - Rectangular steiner tree method of super large size integrated circuit avoiding barrier - Google Patents

Abstract

The right-angle Steiner tree method of VLSI obstacle avoidance belongs to the technical field of computer-aided design of integrated circuits, especially the field of VLSI wiring design, and is characterized in that: an endpoint division method based on a complete Steiner tree (FST) is proposed, and then divided out In each subset of , the ant colony method and the greedy FST method are used to construct sub-Steiner trees for different situations, and finally the idea of detour method is used to connect all sub-Steiner trees. The algorithm can deal with line nets with multiple endpoints (including two endpoints); it can deal with complex obstacles (including concave polygon obstacles); it can handle large-scale problems well in a short period of time. It realizes the right-angle Steiner tree construction method for avoiding obstacles, optimizing line length and time efficiency in VLSI wiring under the condition that the line network to be connected has multiple endpoints.

Description

Cartesian Steiner Tree Method for Obstacle Avoidance in VLSI

technical field

Integrated circuit computer-aided design is the field of IC CAD technology, especially the field of VLSI wiring design.

Background technique

In integrated circuit (IC) design, physical design is one of the main steps, but also the most time-consuming step. A computer-aided design technique related to physical design is called layout design. In layout design, wiring is an extremely important link.

The design scale of integrated circuits is currently developing from very large scale (VLSI), very large scale (ULSI) to G scale (GSI), and the design concept of system-on-chip (SOC) has emerged. The research on the construction method of the minimum rectangular Steiner tree (rectilinear Steinerminimal tree, RSMT) is an important issue in VLSI/ULSI/GSI/SOC layout design, especially in wiring research. The right-angle Steiner tree is to restrict the edges that make up the Steiner tree to be right-angle edges, that is, the edges can only be horizontal or vertical. In the actual wiring process, because the macro module, IP module and pre-wiring will all become obstacles, the RSMT method considering obstacles becomes a very worthwhile research problem. However, so far, people's research has mostly focused on the barrier-free situation. In contrast, the research on the RSMT method with barriers is still relatively blank, and it is necessary to conduct in-depth research. For the practical application of wiring, it is one of the key issues in wiring to study the Steiner tree construction method considering the obstacles, which has great practical significance.

Among the related domestic and foreign researches that have been reported and can be consulted, the research situation on the "construction method of right-angle Steiner tree considering obstacles" can be listed, analyzed and summarized as follows:

For the relatively simple case where the wire net only contains two endpoints, people have done a lot of research, and there are already some relatively mature methods.

Lee proposed the maze method in 1961 ([C.Y.Lee, An Algorithm for Connections and Its Applications, IRE Trans.On Electronic Computers, 1961, 346-365.]), which can be used to solve the problem between the two ends of the two-end line network wiring under obstacles. the shortest path between. But since the method is always symmetric throughout the search, this increases the time and storage space required for the search. In 1978, Soukup proposed an asymmetric search method with fixed meaning ([J.Soukup, Fast Maze Router, Proc.Of 15th Design Automation Conference, 1978, 100-102.]), which improved the search efficiency. But this method cannot guarantee to find the optimal solution. Another improved method was proposed by Hadlock in 1977, called Hadlock's minimum detour method ([Hadlock, A Shortest Path Algorithm for Grid Graphs, Networks, 1977.7, 323-334.]). The time and space complexity of the above two improved maze methods are both O(hw), where h and w are the number of grids. The biggest disadvantage of the maze method is that it needs to search a larger layout space, so it takes a lot of time and storage space. Its advantage is that it is guaranteed to find a solution in any case where there is a solution.

In order to overcome the shortcomings of the maze method, Hightower in 1969 ([D.W.Hightower, A solution to the Line Routing Problem on the Continuous Plane, Proc.Of the 6th Design Automation Workshop, 1969, 1-24.]), Mikami and Tabuchi in 1968 ([Mikami K. and Tabuchi K., AComputer Program for Optimal Routing of Printed Circuit Connectors, IFIPS Proc., 1968, H47, 1475-1478]) respectively proposed a line search method. Its computation time and space complexity are both O(L), where L is the number of lines produced by the method.

Another representative method is the literature [J.M.Ho, M.Sarrafzadeh and A.Suzuki, "An Exact Algorithm For Single-Later Wire-Length Minimization", Proceedings of IEEEInternational Conference of Computer Aided Design, pp.424-427 , 1990.] proposed a method for minimizing the two-end wire net in single-layer detailed wiring. It uses a method called "homotopic transformation" to optimize the transformation of the line network. The so-called "homotopy" means not changing the overall layout of the line network. The author puts forward: when there is no "empty U" in the path (the line formed by three consecutive line segments, which is shaped like the letter U, is called a "U", "empty U" refers to the U-shaped line in the middle of the U-shaped line. When there is still room to move up), it can be determined as the shortest path. This method is only applicable to the processing of the two-end line network, and it can get the optimal path.

Three papers: [Zhou Zhi, The Minimum Steiner Tree Problem in Obstacle Manhattan Space (Master's Dissertation). Hefei: University of Science and Technology of China, 1998.], [Zhou Zhi, Chen Guoliang, Gu Jun. Use the O(tlogt) connection graph to find the shortest path when there are obstacles. Journal of Computer Science, 1999, 22(5): 519-524.] and [Zhou Zhi, Jiang Chengdong, Huang Liusheng, Gu Jun, "Use the generalized connection graph of Q(t) to find the shortest path when there are obstacles", Journal of Software, 2003, 14(2):pp.166-174.] introduces the generalized connection graph GG, whose average complexity is Θ(t), where t is the number of polar edges of obstacles (the three adjacent sides of a polygon,,, if and If it is just opposite, it is the polar edge). GG has certain advantages in complexity. In these literatures, it is proposed to use GG to construct the minimum Steiner tree of the two-terminal network, and it is also proposed that GG can be used to construct the multi-terminal network, but they have not been implemented yet.

In contrast, there are relatively few Cartesian Steiner tree methods considering obstacles for multi-end line networks. Compared with two-point line nets, the multi-endpoint case is much more complicated. Especially in the case of obstacles, it is difficult to find the optimal solution in a time acceptable to people. The method involved in this patent application is a heuristic method for multi-end point line networks, which can solve the Steiner tree of large-scale line networks under obstacles of different shapes in a relatively short period of time. The following will list the currently existing methods for considering the multi-terminal network of obstacles, and compare them with the methods involved in this patent application, so as to point out the differences between them.

Literature [Chen Desheng, Sarrafzadeh M.A wire-length minimization algorithm for single-layer layout[A]. In: Proceedings of IEEE/ACM International Conference of Computer Aided Design (ICCAD), Santa Clara, USA, 1992.390-393.] for single-layer The multi-terminal line network in the layout is studied, and the minimization method based on the TPT transformation and the concept of "line segment visibility" is proposed. Its time complexity is O(max(mn, mlogm)), where n and m are the number of line segments specifying the network N to be connected and all the network sets L, respectively. This method is relatively simple, and it keeps the "topology structure" unchanged (topology preserving) during the conversion process. However, the fixed topological structure limits the degree of freedom of TPT conversion, so that the result depends to a large extent on the initial wiring before conversion, so the result is not ideal in some cases.

Literature [Yukiko KUBO, Yasuhiro TAKASHIMA, Shigetoshi NAKATAKE, Yoji KAJITANI. Self-reforming routing for stochastic search in VLSI interconnection layout[A]. In: Proceedings of IEEE/ACM Asia-Pacific Design Automation Conference (ASP-DAC), Yokohama Japan, 2000.87-92.] proposed to use flip and dual-flip technology to optimize the original wiring. In this paper, it is proved that any tree connected to the wire net can be converted into any other shape tree by using flip and dual-flip, which makes the conversion of this method have more degrees of freedom than the above-mentioned TPT conversion. However, due to the simulated annealing technique used in this method, the execution time is very long. Its time complexity is much greater than the method involved in this patent application.

Literature [Zheng S Q, Lim J S, Iyengar S S. Finding obstacle-avoiding shortest paths using implicit connection graphs[J]. IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems. 1996, 15(1): 103-110. ] introduces a strongly connected graph GC whose complexity is O(e2), where e is the total number of edges of obstacles. It uses both A* and heuristics without redirection based on the "detour" value. In addition, three patents: [Ranko Scepanovic, Cupertino; Cheng-Liang Ding, SanJose. Toward optimal steiner tree routing in the presence of rectilinear obstacles, 5491641, Feb.13, 1996], [Ranko Scepanovic, Cupertino; Cheng-Liang Ding, SanJose. Toward optimalsteiner tree routing in the presence of rectilinear obstacles, 5615128, Mar.25, 1997], and [Ranko Scepanovic, Cupertino; Cheng-Liang Ding, SanJose. Toward optimalsteiner tree routing in the presence of Mar. 99 obstacles, 0870 .9, 1999] also use a similar strong connection graph "escape graph graph", through the maze method or the method of Steinerizing the minimum spanning tree (spanning tree) to find the Steienr of the multi-point line network under obstacles Tree. This type of method will have a better solution effect when the obstacle situation is relatively simple, but when the obstacle shape is complex and the number of edges is large, the strong connection graph they are based on will become very complicated. The efficiency is relatively poor. Therefore, this type of method is only suitable for relatively simple obstacles. However, the method involved in this patent application can be applied to various complicated obstacle situations.

Literature [Liu Jian, Zhao Ying, Shragowitz E, Karypis G.A polynomial timeapproximation scheme for rectilinear Steiner minimum tree construction in the presence of obstacles[A].In: Proceedings of IEEE International Symposium on Circuits on Circuits-AS-1, 2Scda0, A70) (ISC 784.] introduces the Guillotine-cut technique in geometric optimization methods. The complexity of this method is polynomial time without obstacles. Although this method can be applied to situations with obstacles, the solution cannot be completed in polynomial time, and research work on complexity simplification is still needed.

Literature [Ganley J L, Cohoon J.P. Routinga multi-terminal critical net: Steinertree construction in the presence of obstacles [A]. In: Proceedings of IEEEInternational Symposium on Circuits and Systems (ISCAS). London, UK, 1994.113-116.] The point of view is: since the situation of 3-point and 4-point is relatively simple, they can be divided into 3-point group (greedy 3-Steinerization, G3S) or 4-point group (greedy 4-Steinerization, G4S) to achieve. For the Steiner tree problem with obstacles, the time complexity of G3S is O(k2n), while that of G4S is O(k3n2). Where n is the number of optional Steiner points, and k is the number of iterations performed, which is less efficient. batched3-Steinerization (B3S) selects three-point groups in batches, and the time complexity is O(rkn), where r is the number of repetitions, which improves the solution efficiency. But how to choose a three-point group or a four-point group is the core problem of this method, which determines the quality of the solution results of this method. In the case of barrier-free, the usual method is to group closer points together. This method is more reasonable and the results obtained are better. However, in the case of obstacles, it is necessary to consider the obstacles and the distribution of points when selecting a point group. Therefore, the problem of how to select a suitable point group is much more complicated. However, no clear solution to this core problem is given in the literature. Although the time complexity of this method is not very high, it is necessary to do follow-up optimization work to make this method obtain optimized results.

The latest progress is that the literature [Yang Yang, Qi Zhu, Tong Jing, Xianlong Hong, Yin Wang. "Rectilinear Steiner Minimal Tree among Obstacles.In: Proceedings of IEEE ASICON, Beijing, China, 2003, 348-351.] proposed Time complexity is the method of O(mn). The running time and results of this method are all ideal, and it is the most ideal method of the currently announced effect. But this method still has shortcomings: the shape of the processing obstacle is limited to the situation of convex polygons, The method of going around obstacles depends on the construction result of the initial Steiner tree, and is not suitable for larger-scale wire networks. The method involved in this patent application is different from the thinking of this method, and we can obtain better wire length results. Please refer to the experimental data comparison and description given in the following "Experimental Data of the Effect of the Method of the Invention" for details.

In addition, the literature [Huang Lin, Zhao Wenqing, Tang Pushan. A construction method of Steiner tree with floating endpoints. Journal of Computer Aided Design and Graphics. Vol.10, No.6, 1998.11.] In the specific analysis and method description, there is no explanation for the obstacle.

Contents of the invention

The object of the present invention is to propose a right-angle Steiner tree method for avoiding obstacles in VLSI. The right-angle Steiner tree is to restrict the edges that make up the Steiner tree to be right-angle edges, that is, the edges can only be horizontal or vertical.

The general thinking of the present invention is: at first obtain the complete Steiner tree FST (fulsome Steinertree) of all points to be connected, that is, if all endpoints of a right-angled Steiner tree are leaf nodes, we just call it a complete Steiner tree so. Steiner tree full Steiner tree (FST). And delete the FST that intersects with the obstacle; then construct the sub-Steiner tree in the sub-graph composed of the remaining FST. Tree and sub-tree are the most common concepts in "data structure". The Steiner tree and the sub-Steiner tree here also conform to The relationship between the above trees and subtrees; finally, use the detour method to connect all sub-Steiner trees into a complete Steiner tree.

Here FST refers to a complete Steiner tree, all of its endpoints are leaf nodes.

The idea of the present invention: propose an FST-based endpoint division method, and then use the ant colony method and the greedy FST method to construct sub-Steiner trees for different situations in each subset, and finally use the detour method to connect all sub-trees. Steiner tree; specifically, it contains the following steps in order:

(1) initialization;

(2) Construct FST: Construct FST set F according to the endpoints of the line network;

(3) Endpoint division: delete all FSTs intersecting with obstacles in the set F to obtain a new FST set F', wherein the connected FSTs divide the endpoints into n separate subsets Ti (i=1,...,n);

(4) Constructing subtrees: For each subset Ti, construct a subtree Si according to the FST set forming Ti, we use the following two methods to construct subtrees:

(4.1) For the subset Ti whose number of endpoints is less than 20, use the method based on ant colony to construct the subtree. Ant colony: We refer to it as "ant colony optimization method" for short here. It is a typical modern optimization calculation method like simulated annealing method, tabu search method, genetic method, etc., and can be used to solve different practical application problems;

(4.2) For the subset Ti with the number of endpoints greater than 20, use a greedy search strategy based on FST to construct a subtree;

(5) Using the method of detour, calculate the shortest path between every two subtrees, so as to connect Si (i=1,...,n) into a complete Steiner tree.

The present invention is characterized in that it contains the following steps in sequence:

(1) Initialization, the computer reads in the following preset data from the outside:

Network information: the network number, the physical position of the pins to be connected in the network, represented by two-dimensional Cartesian coordinates, which is the endpoint;

Obstacle information: the column of points forming the polygon of the obstacle;

(2) Construct a complete Steiner tree collection with the development kit of GeoSteiner3.1 according to the end points of the line network, expressed by FST, referred to as F;

(3) Endpoint division: Delete all FSTs that intersect with obstacles in the set F obtained in step (2), and obtain a new FST set, denoted by F', where the connected FSTs divide the endpoints into n separate subsets Ti , i=1,...,n;

(4) Construction subtree: for each subset Ti that step (3) obtains, according to the FST set construction sub-Steiner tree that forms Ti, represented by Si, this step will adopt following two methods respectively according to the number of endpoints:

(4.1) For the subset Ti whose number of endpoints is less than 20, use the method based on ant colony to construct the subtree, and the steps are as follows:

(4.1.1) Setting: the initial pheromone value on the edge of the subset Ti is represented by τ, and τ is the pheromone value;

(4.1.2) Place one ant at each endpoint of each Ti. Since we design and adopt the technology based on the ant colony optimization method, we must use the noun "ant" in the ant colony optimization method when the problem is formalized. Only in this way can the problem be solved based on the ant colony optimization method. And be numbered, represented by antName; at the same time, each ant maintains a taboo table to record the points that have been visited; set the maximum number of iterations;

(4.1.3) Choose an ant m, and calculate the probability of selecting each vertex adjacent to m by the following formula, i represents the vertex where ant m is located, and j represents the adjacent vertex of vertex i, (i, j ) represents the edge connecting vertex i and vertex j, p _{i, j} represents the probability that ant m chooses vertex j as the next vertex to reach:

Among them, the set N is a vertex set, which is connected to the vertex where the current ant m is located through the edges on Ti, and is not composed of vertices it has visited;

η _j ^m : When the current ant m is at the vertex i, the visibility of a certain vertex j among the vertices connected to the ant m:

${\mathrm{<span\; class="notranslate">\; \&eta;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&gamma;</span>}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; \&psi;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}}$

Ψ _j ^m : the shortest distance from vertex j to the vertices visited by all other ants, which is a known quantity, c(i, j): the length from vertex i to vertex j,

τ _ij : update value of pheromone concentration on edge (i, j):

τ _i,j = (1-ρ)·τ _i,j +ρ·Δτ _i,j

Δτ _ij : When each side is selected, the amount of pheromone added on it:

Among them, c(S _t ) is the bus length of the currently retained minimum right-angle Steiner tree, and E _t is its edge set;

The above-mentioned α, β, γ, ρ, and Z are all constants, preset, and their ranges are as follows:

α ∈ [1, 5], β ∈ [1, 5], γ ∈ [1, 4], ρ ∈ [0, 1], Z ∈ [1, ∝],

Among them, α, β, γ, and Z are integers, and ρ is a real number;

The above tabulist is a taboo list, and ktabulist(m) indicates the visibility of point k that is not in m’s taboo list;

(4.1.4) According to the probability p _ij obtained in step (4.1.3), the ant m selects the edge (i, j) to pass through;

(4.1.5) Add vertex j to the taboo table of ant m;

(4.1.6) If the former ant m encounters another ant m', remove the ant m from the ant set, and add the endpoint in m's taboo list to the taboo list of another ant m';

(4.1.7) Update the content of the pheromone on the edge (i, j);

(4.1.8) Increase the number of iterations by 1, repeat steps (4.1.2)-(4.1.8), iterate until the maximum value of the set number of iterations;

(4.2) For the subset Ti with the number of endpoints greater than 20, use the greedy search strategy based on FST to construct the subtree, which contains the following steps in turn:

(4.2.1) Delete the FST that intersects with the obstacle, and the remaining FST is called the candidate FST, and then calculate the desirability η(t) of all candidate FSTs:

η(t)=c(t) ^λ /t(t) ^ω

Among them, t represents the FST that needs to calculate the degree of desire, c(t) represents the bus length of t, t(t) is the number of endpoints of FST, λ and ω are constants, preset, and their ranges are as follows:

λ∈[1,4], ω∈[1,4], where λ, ω are integers;

(4.2.2) Select the FST with the minimum desirability of the candidate set, i.e. f, and add f to the current solution set Y;

(4.2.3) Delete all FSTs that are incompatible with f in the candidate FSTs. Here, the incompatibility of two trees means that the two trees contain two or more identical endpoints, or have one or more edges overlapping;

(4.2.4) Delete all endpoints covered by f in the endpoint set;

(4.2.5) If the candidate FST set is not empty, then repeat the steps of (4.2.2)-(4.2.4), select a new FST to add to the current solution, until the candidate FST set is empty;

(4.2.6) If there are remaining elements in the endpoint set, add them to the current solution;

(5) Use the minimum return value method, that is, the detour method, to calculate the shortest path between every two subtrees, thereby connecting Si, i=1,..., n, into a complete Steiner tree, and calculating the distance between the two subtrees The method of the shortest path is: for all the endpoints belonging to these two subtrees, find the shortest path two by two, and take the shortest path as the shortest path between the two subtrees; calculate the two endpoints, that is, point s to point t, the method of the shortest path between has the following steps:

(5.1.1) Construct the escape graph according to the obstacle and the endpoints s, t. Here, the escape graph is expanded from the horizontal and vertical edges of the obstacle to both ends until it encounters an obstacle, so that the expanded line segments intersect to form a Connection Diagram;

(5.1.2) Initialize the candidate point set as point {s}, the visited point set is empty, set the current point as s;

(5.1.3) Add all points that are adjacent to the current point on the escape map and have not been visited to the set of candidate points, and calculate the return value of these newly added points according to the following rules:

The definition of the return value of the directed edge u→v: Given a directed edge u→v and a final target point t, let L be a straight line passing through the point t and perpendicular to the directed edge u→v, then:

When u and v are on the same side of L, and the distance from u to L is farther than v, then the return value of u→v=0;

When u and v are on the same side of L, and the distance from u to L is closer to v, then the return value of u→v=the length of line segment u→v;

When the line segment u→v and L intersect at w, then the return value of u→v=the length of the line segment w→v;

Therefore, the return value of a point can be defined as follows: during the pathfinding process from the source point to the target point, the return value of a certain point is the sum of the return values of all paths from the source point to the point;

(5.1.4) Select the point q with the smallest return value in the candidate set to add to the access point set, and set the current point as q;

(5.1.5) If the final target point t is not in the candidate point set, repeat steps (5.1.1)-(5.1.4);

(5.1.6) If the final target point t is in the candidate point set, add t to the access point set, and the shortest path found in this way is the path formed by the point columns in the access point set according to the order in which they were added.

Method of the present invention has following characteristics:

Firstly, the method of the present invention can deal with line nets with multiple endpoints (including two endpoints); it can deal with complex obstacles (including concave polygon obstacles). That is, the scope of application of the method of the present invention is wider. Simultaneously, the method of the present invention does not only provide a conception or an embryonic form of thinking like some documents, but an IC CAD tool that can run on a specific device (workstation) and serves the wiring process, with specific implementation descriptions.

Secondly, compared with the existing multi-end point line network Steiner tree construction method considering obstacles, the method of the present invention has better performance in dealing with the scale of the problem and the line length. The method of the present invention can calculate the situation that 500 end-point line nets wind around 100 right-angle obstacles within 30 minutes, and for the situation below 7 end-points, our method can obtain the result in about 0.1 second; simultaneously use this method to solve The line length results are also very good. The method of the present invention is superior to existing methods in comprehensive effect, please refer to the description of the experimental data given in "Experimental data of the effect of the method of the present invention" for details.

The experimental data of the method effect of the present invention

The computer system for the experiment is described in detail as follows:

A Sun V880 workstation;

Unix operating system;

C++ programming language;

Vi editor, gcc compiler, gdb debugging tool, etc.;

In the test, the parameters are set as follows: ant colony method: α=1, β=1, γ=1, ρ=0.5, Z=10000, MAX_LOOP=100; greedy FST method: λ=1, ω=4.

The wire net in the MCNC circuit is used as a test example, and for the following 9 wire nets, the method of the present invention and the method of the latest research progress---"2-step" method of Yang Yang et al [Yang Yang, Qi Zhu, Tong Jing, Xianlong Hong, YinWang. "Rectilinear Steiner Minimal Tree among Obstacles.In: Proceedings of IEEE SICON, Beijing, China, 2003, 348-351.] The comparison of the test results is listed as follows, each example is tested 10 times, and the average, maximum The worst/best cases are recorded as follows: NetID Endpoints 2-step[2] Ours[1] Best[4] Ave[4] Worst[4] C2: 22 2 0% 0% 0% 0% C2: 33 2 0% 0% 0% 0% C2: 2 3 0% 0% 0% 0% C2: 17 3 1.87% 0% 0% 0% C2: 504 4 3.80% 0% 0% 0% C2: 59 3 4.46% 0% 0% 0% C2: 609 4 4.89% 0% 0% 0% C2: 67 5 5.48% 0% 0% 0% C2: 177 6 7.28% 0% 0.19% 1.32% C2: 98 4 21.4% 0% 0% 0% C2: 117 3 1.87% 0% 0% 0% C2: 18 4 3.80% 0% 0.06% 0.45% Average / 5.31% 0% 0.02% 0.15%

[1] Ours: The redundancy of RSMT length under obstacles generated by the method of the present invention [3].

[2] The "2-step" method solves the generated RSMT length under obstacles.

[3] Redundancy = (result Steiner tree total length - optimal Steiner tree total length) / optimal Steiner tree total length × 100%. The "optimal Steiner tree bus length" here is obtained by manual calculation.

[4] Best, Ave, Worst are the best result, average result and worst result respectively.

From the above test results, it can be calculated that the average value of the line length redundancy of the wiring tree solved by the method of the present invention is 0.02%, which is much smaller than the 2-step redundancy (5.31%).

Using randomly generated test examples, the method of the present invention is also compatible with the "G4S" method of Ganley et al. [Ganley J L, Cohoon J.P. Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles [A]. In: Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS).London, UK, 1994.113-116.] (G4S is an existing Steiner method that can efficiently deal with multi-terminal obstacles) The comparison of test results is listed as follows: Endpoints G4S[5] Ours[1] Wire[6] CPU-time[7] 5 9.2 9.8 0.02 10 9.1 9.1 0.10 15 9.4 9.4 0.25 20 9.0 9.2 0.38 50 - 9.1 2.75 100 - 8.8 3.66 500 - 9.1 559 1000 - 8.9 1240

[5] G4S: Steiner Ratio [8] of the solution result of G4S method.

[6]Wire: Use our method to solve the Steiner Ratio of the result (Steiner Ratio)[8].

[7] CPU-time: The running time of our method.

[8] Steiner ratio (Steiner Ratio)=(minimum spanning tree bus length-Steiner tree bus length)/minimum spanning tree bus length×100%.

It can be seen that when the number of endpoints is less than 20, our method is better than G4S. When the number of endpoints is greater than 20, G4S can no longer handle it, but our method can still get relatively stable results, and the running time is also shorter. shorter.

Description of drawings

Fig. 1: flow chart of core part of the present invention.

Figure 2: Flowchart of Step 1.

Figure 3: (a) Step 1 initial graph (with FST intersected with obstacles);

(b) Step 1 result example diagram (remove all FSTs that intersect with obstacles).

Figure 4: Example graph of the result of step 2.

Figure 5: Flowchart of Step 3.

Figure 6: Example diagram of the result of step 3.

Figure 7-Figure 15: Schematic diagram of the construction process of net17:

Figure 7: Initial layout.

Figure 8: The resulting FST ensemble.

Figure 9: Implementation results of sub-graph division (step 1).

Figure 10: Detailed process of step 2:

(1) Initial state; (2) First move; (3) Get the result.

Figure 11: Step 2 completion result.

Figure 12: Preparation process for computing the shortest path from t1 to t3:

(a) Initial escape graph; (b) escape graph after adding a source point;

(c) The escape graph after adding a target point; (d) Mark all nodes.

Figure 13: (a) initial state; (b) first point selection;

(c) The second point selection; (d) The third point selection;

(e) 4th point selection; (f) 5th point selection; (g) 6th point selection.

Figure 14: (a) the shortest path of AC; (b) the shortest path of AD;

(c) the shortest path of AE; (d) the shortest path of AF;

(e) the shortest path of BC; (f) the shortest path of BD;

(g) the shortest path of BE; (h) the shortest path of BF.

Figure 15: Final result tree.

Detailed ways

Firstly, the core idea of the "right-angle Steiner tree method considering obstacles" involved in this patent application is specifically analyzed.

After reading and processing the information of circuit obstacles and wire nets, the core part of this method is the process of constructing a Steiner tree. The overall flow chart is shown in Figure 1. The idea of this method is different from the previous methods. The method is divided into three steps to construct the final result tree: the first step is to find the FST (fulsome Steiner tree) of all endpoints, and delete the FST that intersects with obstacles; Construct the sub-Steiner tree in the subgraph composed of the FST below; the third step uses the detour method to connect all the sub-Steiner trees into a complete Steiner tree. The three steps of the method are described below.

The first step: find the FST (fulsome Steiner tree) of all endpoints, and delete the FST that intersects with the obstacle, which is equivalent to steps (2) and (3) in the previous invention idea. The flow chart of this step is shown in Figure 2 Show.

We use the method of constructing FST in the GeoSteiner method to generate FST, which has been published in 1998 [D.M.Warme, P.Winter, and M.Zachariasen, "Exact Algorithms for Plane Steiner TreeProblems: A Computational Study", Technical Report DIKU-TR -98/11, Department of Computer Science, University of Copenhagen, April 1998]. The FST set obtained after the construction is completed is shown in Figure 3-a. It can be seen that there are several line segments intersecting with the obstacle edge.

For each constructed FST, we judge whether its edge intersects with the obstacle edge. If it intersects, it is considered that the FST intersects with the obstacle and is deleted; otherwise, it is kept. Then according to the connectivity, a number of connected sub-graphs are formed from the remaining FST, and an instance division obtained after the first step of processing is shown in Figure 3-b.

Step 2: The main task of this part is to interconnect the results processed in the previous step, that is, several sub-graphs, each of which can be connected by a complete Steiner tree or by several Steiner trees. In addition, two considerations should be taken into account: on the one hand, the length of the bus used in each sub-graph should be the shortest, and on the other hand, we should try our best to ensure the connectivity of the original sub-graph.

In this part, two methods are proposed, which are named ant colony method and greedy FST method respectively. Both of them have their own advantages, and they can achieve good results by choosing applications for different situations.

The following first introduces how to use the ant colony method to interconnect sub-graphs:

The ant colony method is a heuristic method suitable for a variety of NP-hard problems. It takes into account the advantages of the greedy method and the random optimization method. The degree will not be as high as simulated annealing (SA).

Specific to our method, we regard each subgraph as a connection graph, place an ant on each endpoint, and form a collection of ants. In each round of iteration, first select an ant, let it move to another adjacent end point through the adjacent edge on the strongly connected graph according to a certain method. Every time it moves, the selected ants will leave pheromone (trail) on the edge they walk, and the pheromone on the path will gradually volatilize over time. Each ant maintains a tabulist at the same time, and uses it to record the endpoints that have been visited, so as to avoid repeated visits and form a loop. When an ant encounters another ant, the former is removed from the ant set, and the endpoint in its taboo list is added to the latter's taboo list. This process of selecting ants, selecting paths, and updating pheromones continues until all endpoints are covered by an RSMT. Record the currently constructed RSMT, and compare it with the previously constructed results, and keep the one with the smaller downline length. This counts as one iteration. Perform multiple iterations until the bus length no longer becomes smaller, or reaches the maximum number of iterations (after experimentation, we set this value to 100).

Ants choose the next target according to statistical laws. This probability depends on two aspects, on the one hand, the pheromone concentration left by the ant on the path in previous iterations, and on the other hand, the visibility corresponding to the connected vertices. Assuming that the current ant m is at vertex i, the visibility of point j in the connected vertices can be expressed by the following formula:

${\mathrm{<span\; class="notranslate">\; \&eta;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&gamma;</span>}<span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; \&psi;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Among them, γ is a constant, Ψ _j ^m is the shortest distance from vertex j to all other ants’ visited points, which represents the speed at which it is connected to other points, c(i, j) is the distance from vertex i to The length of vertex j.

The update of pheromone concentration on edge (i, j) can be characterized by the following formula:

τ _i,j = (1-ρ)·τ _i,j +ρ·Δτ _i,j (2)

Among them, ρ is a constant, called the evaporation rate, which characterizes the volatilization speed of existing pheromones on the path. And for each selected side, the amount of pheromone added on it is

Wherein c(S _t ) is the bus length of the currently reserved RSMT. E _t is its edge set, and Z is a constant representing the total amount of pheromone on the whole tree.

So far, the probability that the current ant m selects the side (i, j) is

The set N is composed of all the vertices connected to the current ant through the edges on the connection graph, and not the vertices it has visited.

The ant colony method is given below:

Initialize the pheromone on each side as p0;

Set the current number of iterations to 0;

while iterations<maximum value of set iterations

Place an ant on each endpoint in the endpoint set and put them into their respective tabu lists.

while the number of ants > 1

Choose an ant m;

Through formula (1) and formula (4), calculate the probability of selecting each connected vertex;

According to the probability, select the side (i, j) to pass through;

Add vertex j to the taboo list of ant m;

if the current ant m encounters another ant m'

Then add all the elements in the taboo list of ant m to the taboo list of m';

Remove m from the set of ants;

Use formula (2) and formula (3) to update the pheromone content on the edge.

Increment the number of iterations by one;

The greedy FST method is introduced below, aiming at the shortest bus length, selecting a local optimal solution in the FST set compatible with all current RSMTs, and constructing the RSMT set.

When each FST is initialized, its eagerness must be calculated, and the eagerness is defined as

η(t)=c(t) ^λ /t(t) ^ω (5)

where c(t) is the bus length of the FST named t, and t(t) is the number of endpoints of t. λ and ω are constants.

Obviously, if the desirability of an FST is relatively small, it means that it covers more points with less line length, so that the goal of the shortest bus length is locally optimized.

For the convenience of the following description, the definition of compatibility/incompatibility of two trees is given here: two trees are incompatible means that two trees contain two or more identical endpoints, or have one or more edges overlapping; A tree compatible means that two trees have exactly one identical endpoint and no overlapping edges.

In the method, such a triplet (D, Q, Y) is maintained, where Y is the set of RSMT currently obtained, D is the candidate set of FST, and Q is the endpoint not covered by Y. When initializing, Y is set to empty, D is the remaining FST set obtained after the first step of the method, and Q is the endpoint set of the input instance.

The method first selects the one with the minimum value of η in D, and adds it to the current minimum Steiner tree t, which is an element of the set Y. Then select the n times smaller one from the set D and fill it in t. And so on, but every time a new FST is added, all its incompatibles are removed from the candidate FST set D to avoid conflicts, and the set Q is updated. Therefore, if there is still an FST compatible with the current t in the set D, select the one with the smallest η and add it as above; otherwise, check whether the set D is empty, if not, add t to the set Y , and then reconstruct the RSMT from the set D; if the set D is empty, record the set Q composed of the remaining isolated points as the set of degenerated RSMT, and add it to the set Y.

The greedy FST method is given below:

D←Fi; Q←T; Y←NULL;

Select f from the set D with the least desire;

Y←t←f;

D←D-f;

Remove the FST in the set D that is not compatible with Y;

Remove the endpoint covered by f in Q;

while D is not empty

while in D there exists a FST compatible with the set t

Select f with the smallest η;

t←t+f;

Remove FSTs from the set D that are incompatible with f;

Remove the endpoints covered by f from Q;

Select f from the collection D with the smallest n;

t←f;

Y←Y+t;

Remove FSTs from the set D that are incompatible with f;

Remove the endpoints covered by f from Q;

Put all the remaining isolated points into the set Y;

The performance of the ant colony method is better than the greedy FST method, and the time complexity of the greedy FST method is lower than the former. In order to maximize strengths and avoid weaknesses, different methods need to be adopted for different instances. By analyzing the experimental results, we design that the greedy FST method is used for subgraphs with more than 20 endpoints; otherwise, the ant colony method is used. Experimental results show that this is an effective measure to improve the overall performance of the method.

The ant colony method and the greedy FST method are used to interconnect the sub-graphs, and the Steiner tree is used to connect the endpoints in each sub-graph. Figure 4 shows the situation of generating subtrees from the results of Figure 3-b according to this idea.

The third step: After the first and second steps of the method, some separated subtrees are obtained. The main task of this part is to interconnect them to become a complete Steiner tree. The method is to turn the interconnection of trees into a minimum path problem. That is, find the minimum path of each pair of points in each pair of trees, record the smallest one as the distance between the corresponding two trees, and then interconnect the trees in a greedy way.

I use the literature [Zheng SQ, Lim JS, Iyengar SS. "Finding obstacle-avoiding shortest paths using implicit connection graphs. "IEEE Transactions on Computer Aided Design, 1996, 15(1): 103-110.] to find the shortest path .

First, the definition of the return value of the directed edge u→v is given: given a directed edge u→v and a target point t, let L be a straight line passing through the point t and perpendicular to the directed edge u→v, then :

When u and v are on the same side of L, and the distance from u to L is farther than v, then the return value of u→v=0;

When u and v are on the same side of L, and the distance from u to L is closer to v, then the return value of u→v=the length of line segment u→v;

When the line segment u→v and L intersect at w, then the return value of u→v=the length of the line segment w→v.

From the above, the return value of a point can be defined as follows: during the pathfinding process from the source point to the current target point, the return value of a certain point is the sum of the return values of all paths from the source point to the point.

In the initialization phase, only escape graphs constructed based on obstacles are generated. Here, the escape graph is a connection graph formed by extending the horizontal and vertical edges of the obstacle to both ends until the obstacle is encountered, and the expanded line segments intersect.

Then, two Steiner trees are selected, a pair of points on them are added to the escape graph, and the shortest path is obtained by the reentry value method, and then two points are deleted from the escape graph. Find the shortest path of all the end-point pairs of the two selected Steiner trees in this way, and keep the smallest one. In the same way, perform the above operations on every two Steiner trees, and save the results in a set arranged in ascending order of path length, select a minimum path from it each time, and insert it into the current graph without generating a cycle until into a complete Steiner tree. The return value method used in it is as follows: maintain two sets, the visited set V and the candidate set A. Initially, there is only element source s in set A. Whenever an element is filled into set V, its unvisited neighbors are filled into set A. And when the set A is not empty and has not yet reached the target point, the element with the smallest return value must be taken from the set A and added to the set V, and deleted from the set A at the same time. The flow of the method is shown in Figure 5.

The literature [Zheng SQ, Lim JS, Iyengar SS. "Finding obstacle-avoiding shortest paths using implicit connection graphs. "IEEE Transactions on Computer Aided Design, 1996, 15(1): 103-110.] has proved that the minimum The path is the Manhattan distance plus 2 times the retracement value. In this paper, the method of finding the shortest path under obstacles is used to find the distance between the source point and the target point. The method in this step is based on the reentry value method proposed in the literature. Figure 6 shows the complete Steiner tree generated after the third step is completed.

In the implementation, the values of the parameters in formulas (1)-(5) are stipulated as follows:

α=1, β=1, γ=1, ρ=0.5, Z=10000, MAX_LOOP=100, λ=1, ω=4.

Below in conjunction with the example of the circuit net of a MCNC, illustrate the whole process of this method, as follows:

In order to realize, or specifically implement the present invention, we give the following description about the implementation of the invention.

The computer system for implementing the present invention: the software designed in the present invention for wiring service shall be implemented on a specific computer system, and the computer system is specifically described as follows.

A Sun V880 workstation;

Unix operating system;

C++ programming language;

Vi editor, gcc compiler, gdb debugging tool, etc.

Step (1): Preliminary work. Read in net information, obstacle information and process them. The following is the file describing the net: net 17(20,1000)(300,400)(600,1000)(500,1100)(650,1110)(700,1200);

——Description: The general form of the net description file is: net net_id{(pin_x, pin_y)};

Among them, net_id represents the net number, and (pin_x, pin_y) represents the coordinates of the pins to be connected to the net.

The obstacle information description file for Line 17 is as follows:

obs(100,1300)(400,1300)(400,800)(1000,800)(1000,600)(100,600);

——Explanation: The general form of the obstacle description file is: obs{(x, y)};

Wherein (x, y) represents the vertices on the obstacle polygon, and the order of the point columns starts from the lower left corner and is arranged in a counterclockwise direction.

FIG. 7 is a schematic diagram of the input net17 and obstacles, in which the coordinates of the endpoints of the net to be connected and the coordinates of the endpoints of the obstacles are given.

Step (2): construct the FST collection F according to the endpoint point of line network, we adopt the method that introduces among the GeoSteiner (see the narration in the first step of the specific implementation mode, the program of constructing FST can be found in the development kit of GeoSteiner3.1, It can be downloaded and used for free at http://www.diku.dk/geosteiner/) to construct FST. There are 5 FSTs generated according to the endpoints of net17, and we number them 1, 2, 3, 4, 5, 6, 7, and 8, as shown in Figure 8.

Step (3): Delete all FSTs that intersect with obstacles. In this way, FSTs No. 1, 2, 4, and 8 will be deleted, and FSTs No. 3, 5, 6, and 7 will be retained. In this way, according to the connectivity, FST Nos. 3, 5, 6, and 7 divide the four endpoints into two groups——A and B are a group (T1), and C, D, E, and F are a group (T2), as shown in the figure 9. The endpoints in the T1 and T2 groups are connected to each other by FST, but there is no connection between T1 and T2. Thus, the FST connected to T1 constitutes the subgraph H1, and the FST connected to T2 constitutes the subgraph H2.

Step (4): Construct subtree. The connection method in the second step mentioned above in the specific implementation manner will be described below by taking the connection in the sub-graphs H1 and H2 as an example. In order to illustrate the two subtree construction methods described in 4.1 and 4.2, we use the ant colony method (step 4.1) and the greedy FST method (step 4.2) to construct subtrees for subgraphs H1 and H2 respectively. First, the specific process of constructing subtrees for the H1 subgraph using the ant colony method is introduced, and the steps are as follows:

Since the FST belonging to the H1 subgraph is No. 6 FST, we construct the connection graph C1 of the H1 subgraph according to the No. 6 FST, and stipulate that ants can only move along the edge of C1, as shown in Figure 10(1). Next, initialize the pheromone value on the side of C1:

τ(AU)=τ(UB)=1.0.

where τ(AU) and τ(UB) denote the pheromone values on the edge AU and edge UB, respectively.

Let’s start the first iteration of the ant colony method: first place an ant at each of the two endpoints (A, B) of H1, and record these two ants as ant1 (initially located at point A) and ant2 (initially located at point B). ), set the taboo tables of ant1 and ant2 as {A} and {B} respectively. Now construct a Steiner tree through the movement of ants:

The first selection is at ant1 (a surviving ant is randomly selected each time), and the visibility when ant1 selects the AU side is calculated according to formula (1), where m=1, i=A, j=U, c(i, j )=|AU|=280 (length of side AU), γ is a constant, we set it as 1, Ψ _j ^m is the shortest distance from vertex j to all visited points of other ants, at this time, the so-called other ants It is ant2, the point visited by ant2 is the point in its taboo table, that is, {B}, so Ψ _j ^m is the shortest distance from vertex U to point B |BU|=600, substituting into formula (1) to get:

${\mathrm{<span\; class="notranslate">\; \&eta;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&eta;</span>}}_{\mathrm{<span\; class="notranslate">\; u</span>}}^{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 280</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; 600</span>}}<span\; class="notranslate">\; \&ap;</span>\mathrm{<span\; class="notranslate">\; 0.00114</span>}$

According to formula (4), calculate the probability that ant1 selects the edge AU, where τ _{i, j} is the pheromone value on the (i, j) edge of C1, here is the pheromone value on the edge AU, that is, τ(AU)= 1.0. α and β are constants, we set α=1, β=1. The set N is composed of all the vertices connected to the current ant through the edges on the strongly connected graph, and not the vertices it has visited, so N={B}.

${\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; AU</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; \&tau;</span>}}_{\mathrm{<span\; class="notranslate">\; AU</span>}}{<span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; \&eta;</span>}}_{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="B"\; filenames="C20041006911800301.png"\; state="\{\{state\}\}">B</figure-callout></span>}}^{\mathrm{<span\; class="notranslate">\; 1</span>}}}{{\mathrm{<span\; class="notranslate">\; \&tau;</span>}}_{\mathrm{<span\; class="notranslate">\; AU</span>}}{<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; \&eta;</span>}}_{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="1"\; label="B"\; filenames="C20041006911800301.png"\; state="\{\{state\}\}">B</figure-callout></span>}}^{\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1.0</span>}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; 0.00114</span>}}{\mathrm{<span\; class="notranslate">\; 1.0</span>}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; 0.00114</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}$

Since the probability of moving along the AU side is 1, ant1 moves to U along the AU side, and ant1 adds U point to its own tabulist, so now the tabulist of ant1={A, U}.

There are still two ants alive, so continue to choose ants. This time, we choose ant2 (same as above, also randomly selected). In the same process as above, we calculate that the probability of ant2 moving along the BU side is 1, so ant2 moves along the BU side. Move to U along the BU side; since the U point has been included in the tabulist of ant1, ant2 dies, and merges the tabulist of ant2 into the tabulist of ant1, that is, the tabulist of ant1={A, B, U}.

This shows that a complete solution S _t has been constructed, and this solution is represented by the point in the tabulist of the surviving ant. Calculate the weight of this solution, which is the bus length of this Steiner tree:

c(S _t )=|AU|+|UB|=280+600=880

Calculate the increment of pheromone according to the above weight and formula (3):

${\mathrm{<span\; class="notranslate">\; \&Delta;\&tau;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; Z</span>}}{\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1000</span>}}{\mathrm{<span\; class="notranslate">\; 880</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1.136</span>}$

Then update the values of pheromones on the two sides of AU and UB according to formula (2). ρ is a constant, called the evaporation rate, which characterizes the volatilization speed of existing pheromones on the path, and we set it to 0.5:

τ(AU)=(1-ρ)×τ(AU)+ρ×Δτ _{i, j}

＝(1-0.5)×1.0+0.5×1.136＝1.068

τ(BU)=(1-ρ)×τ(BU)+ρ×Δτ _{i, j}

＝(1-0.5)×1.0+0.5×1.136＝1.068

Next, start a new round of iterations, construct a set of solutions, and compare them with the existing optimal solutions above. If it is better than the current optimal solution, use this solution to replace the current optimal solution, otherwise proceed to the next cycle. , until the number of loops is greater than 100. A subtree S1 as shown in FIG. 11 can be obtained.

The following introduces the method of constructing a subtree for the subgraph H2 using the greedy FST method.

For sub-graph H2, the candidate FSTs are No. 3, No. 5 and No. 7 FSTs, see (3), (5), and (7) in Fig. 8. Below, we mark these 3 FSTs with F3, F5 and F7. First initialize 3 sets: D←{F3, F5, F7}; Q←{C, D, E, F}; Y←NULL. Then according to (5) formula in the specific embodiment calculates the degree of thirst of each FST in D, we get constant λ=1, ω=4; c (t) is the bus length of FST, so:

c(F3)=|500-650|+|1100-1110|+|1000-1100|=260.

c(F5)=|500-600|+|1100-1000|=200.

c(F7)=|650-700|+|1110-1200|=140.

t(t) is the number of endpoints covered by FST, obviously:

t(F3)=3, t(F5)=2, t(F7)=2.

So the degrees of desire are:

η(F3)=c(F3) ^λ /t(F3) ^ω =260/3 ⁴ =3.21.

η(F5)=c(F5) ^λ /t(F5) ^ω =200/2 ⁴ =12.5.

η(F7)=c(F7) ^λ /t(F7) ^ω =140/2 ⁴ =8.75.

Take the FST with the least desirability in D, which is obviously F3, and add F3 to the current partial solution set Y; then remove F3 from D, then D={F5, F7}, remove all incompatible with F3 from D It is easy to see that F5 and F3 have two identical endpoints (C, D). According to the definition of incompatibility, F5 and F3 are incompatible, so F5 should be removed from the set D; similarly, F7 and F3 can be judged compatible and should remain in set D. So now the elements of the 3 sets and the current subtree t become as follows:

D={F7}; Q={F}; Y={F3}. t=F3.

Since the set D is not NULL, the FST-F7 compatible with t is selected from D and put into the set Y. Since F7 is the only element in D, it is directly selected without calculating the compatibility of F7. Now D is empty, and then remove the endpoint F covered by F7 in Q, then Q is also empty, so the cycle ends. And now there is no isolated point, so the set Y maintains the status quo, that is, Y={F3, F7}.

Now a subtree S2 as shown in Figure 11 can be obtained from the FST in the set Y.

Step (5), connect the subgraphs. For the two subtrees obtained above, find the shortest distance two by two, that is, for each pair of subtrees, find the shortest path between all point pairs, and then take the shortest one.

In the following, the specific implementation process of the minimum reentry value method is given by taking finding the shortest path between B and C as an example. In the following description, in order to distinguish endpoints from general vertices, we record endpoint B as t1 and endpoint C as t3.

Before finding the shortest path between t1 and t3, the following tasks should be done first: First, use Zheng’s literature [Zheng S Q, LimJ S, Iyengar S S.Finding obstacle-avoiding shortest paths using implicit connection graphs[J].IEEE Transaction on Computer -Aided Design of Integrated Circuits and Systems.1996, 15(1): 103-110.] The method proposed is to construct an escape graph for obstacles, as shown in Figure 12(a), adding the source point t1 and target point t3 to the above The constructed escape graph is shown in Figure 12(b) and (c). The coordinates of the newly added points are marked in the figure.

In the process of pathfinding, two sets are set, candidate point set C and visited point set V. In the initial state, V is set to be empty, and there is only source point t1 in C. Then repeat the following operations: take a minimum return value from the set C and add it to the set V, that is, ensure that only the currently known minimum return value is visited each time, and add its unvisited adjacent nodes into set C.

As mentioned above, first initialize the visited set V to be empty, the candidate set C to be t1, and set the current point to be t1; then add the three points v2, v3, and v6 adjacent to t1 to the candidate set C, and calculate their Turnback value; Next, select the point v6 with the smallest turnback value in the candidate set C, add it to the visited set V, and set the current point to v6; the above process is shown in "initialization" and "first point selection" in Table 1 . This continues until the target point t3 is added to the set V.

When calculating the shortest path from t1 to t3 according to the minimum return value method, the calculation results of each step are shown in Table 1. The "value" in the "point (value)" in Table 1 indicates the return value of this point, for example, v7(200) indicates that the return value of point v7 is 200.

Table 1 Calculating the minimum return value method of the shortest path from t1 to t3 Collection V visited Candidate set C Correspondence diagram initialization Φ t1 Figure 13(a) first point selection t1(0) v6(0), v3(200), v2(400) Figure 13(b) second point selection v6(0) v7(200), v3(200), v5(400), v2(400) Figure 13(c) third point selection v7(200) v10(200), v3(200), v5(400), v2(400) Figure 13(d) The fourth selection v10(200) v9(200), v12(200), v3(200), v5(400), v2(400) Figure 13(e) fifth point selection v9(200) t3(200), v12(200), v3(200), v5(400), v2(400), v8(500) Figure 13(f) The sixth point selection t3(200), stop Figure 13(g)

Note: the rebate value in brackets

The calculation process of several typical reentry values in Table 1 is given here:

In the first point selection process, the return value of v6 needs to be calculated. According to the definition of the return value, in the pathfinding process from the source point t1 to the current target point v6, the return value of v6 is from the source point t1 to v6 The sum of the return values of all paths; the path from t1 to v6 only contains a line segment t1→v6, which is on the same side of the vertical line passing through the final target point t3, and t1 is farther than v6, so it is defined according to the return value of the line segment In the first case, the return value of the line segment is 0, so the return value of v6 is 0.

In the fifth point selection, it is necessary to calculate the return value of v8. Since the return value of v9 is known to be 200, it is easy to deduce according to the definition of the return value. The return value of v8 is equal to the return value of v9 and the return value of the line segment v9→v8 Sum. The line segment v9→v8 is on the same side of the vertical line passing through the final target point t3, and v8 is farther than v9, which belongs to the second case of the definition of the return value, so the return value should be the length of the line segment, which is 300. So the rebate value of v8 is 300+return value of v9, which is equal to 500.

In the second point selection process, for the line segment v6→v7, the return value is accumulated to 0 when reaching v6, and v6 and v7 are respectively located on both sides of the vertical line passing through the target point t, which is the first definition of the return value above. Three cases, so the length 200 of the line segment below the vertical line is the return value of the line segment v6→v7. So the rebate value of v7 is 200+return value of v6, which is equal to 200.

(A, C), (A, D), (A, E), (A, F), (B, C), (B, D), (B, E, (B, The shortest path of F) is shown in Fig. 14-a, b, c, d, e, f, g, h respectively. The length of the shortest path between ab is represented by SP(ab) below, then:

SP(AC)=2000, SP(AD)=1700, SP(AE)=1760, SP(AF)=1800.

SP(BC)=1700, SP(BD)=1700, SP(BE)=1840, SP(BF)=1800.

Select the shortest path BC to connect the two subtrees, and get the final connection result shown in Figure 15.

Claims (1)

1. the right angle Steiner tree method of VLSI (very large scale integrated circuit) obstacle avoidance is characterized in that it contains following steps successively:

(1) following preset data is read in initialization, computing machine from the outside:

The information of gauze: gauze is numbered, and needs to connect the physical location of pin in the gauze, represents with two-dimentional Cartesian coordinate, is end points;

Complaint message: the polygonal point range that forms obstacle;

(2) construct the set of complete Steiner tree according to the end points of gauze with the kit of GeoSteiner3.1, represent, be called for short F with FST;

(3) end points is divided: all and the FST that obstacle intersects among the set F that deletion step (2) obtains, obtain new FST set, and use F ' expression, wherein, continuous FST is divided into the subclass Ti of n separation to end points, i=1 ..., n;

(4) structure subtree: each the subclass Ti to step (3) obtains, according to the FST set constructor Steiner tree that forms Ti, represent that with Si this step will be adopted following two kinds of methods respectively according to end points quantity:

(4.1) for end points quantity less than 20 subclass Ti, adopt method construct subtree based on the ant group, its steps in sequence is as follows:

(4.1.1) set: the plain value of the initial information on the limit of subclass Ti, represent that with τ τ is the pheromones value;

(4.1.2) 1 ant is placed at each the end points place in each Ti, and is numbered, and represents with antName; Simultaneously, each ant is safeguarded a taboo table, the point that record had been visited; Set the maximal value of iterations;

(4.1.3) optional ant m calculates the probability of selecting each summit adjacent with m by following formula, and i represents the summit at ant m place, and j represents the adjacent vertex of summit i, and (i, j) expression connects the limit of summit i and summit j, p _{I, j}Expression ant m selects the probability on the summit that summit j will arrive as the next one:

Wherein, set N is a vertex set, and it is to be linked to each other with summit, current ant m place by the limit on the Ti by all, and is not that the summit that it was visited is formed;

η _j ^m: current ant m when the i of summit, and the visibility of a certain summit j in the summit that ant m links to each other:

${\mathrm{\&eta;}}_j^m=\frac{1}{c(i,j)+\mathrm{\&gamma;}\&CenterDot;{\mathrm{\&psi;}}_j^m}$

ψ _j ^m: the bee-line from summit j to the summit that current every other ant had been visited, be known quantity,

C (i, j): from the summit i length of j to the limit,

τ _Ij: the limit (i, j) updating value of the pheromone concentration on:

τ _i，j＝(1-ρ)·τ _i，j+ρ·Δτ _i，j

Δ τ _Ij: when whenever selecting on one side, the amount of the pheromones that is increased on it:

Wherein, c (S ₁) be total line length of the current minimum right angle Steiner tree that keeps, E ₁It is its limit set;

Above-mentioned α, β, γ, ρ, Z are all constant, preestablish, and its scope is as follows:

α∈[1，5]，β∈[1，5]，γ∈[1，4]，ρ∈[0，1]，Z∈[1，∝]，

Wherein, α, β, γ, Z are integers, and ρ is a real number;

Above-mentioned tabulist is the taboo table, and k  tabulist (m) expression is the visibility of the some k in the taboo table of m not;

(4.1.4) Probability p that obtains according to step (4.1.3) _Ij, the limit that ant m selection will be passed through (i, j);

(4.1.5) summit j is added in the taboo table of ant m;

(4.1.6) if preceding ant m runs into another ant m ', just ant m is concentrated from ant and remove, and the end points in the taboo table of m is added in the taboo table of another ant m ';

(4.1.7) upgrade limit (i, j) content of the pheromones on;

(4.1.8) iterations adds 1, and repeating step (4.1.2)-(4.1.8) iterates to till the maximal value of iterations of setting always;

(4.2) for end points quantity greater than 20 subclass Ti, adopt greedy search strategy structure subtree based on FST, contain the following step successively:

(4.2.1) deletion and the crossing FST of obstacle, remaining FST is called candidate FST, calculates the degree of craving for of all candidate FST again] (t):

η(t)＝c(t) ^λ/t(t) ^ω

Wherein, t represents that needs calculate the FST of degree of craving for, total line length of c (t) expression t, and t (t) is the number of endpoint of FST, and λ and ω are constants, preestablish, and its scope is as follows:

λ ∈ [1,4], ω ∈ [1,4], wherein, λ, ω are integers;

(4.2.2) select the FST of candidate collection degree of craving for minimum, i.e. f, and f joined current separating among the set Y;

(4.2.3) all and the incompatible FST of f among the deletion candidate FST here, are set for two and incompatiblely are meant that two trees comprise two or more same endpoints, perhaps have one or more than one limits overlapping;

(4.2.4) all end points that covered by f in the set of deletion end points;

If (4.2.5) candidate FST set is not empty, then repeat the step of (4.2.2)-(4.2.4), select new FST to join in current the separating, be empty up to candidate FST set;

If (4.2.6) also have surplus element in the end points set, then they joined in current the separating;

(5) utilize the minimum value of turning back method, it is the detour method, calculate the shortest path between per two subtrees, thereby Si, i=1, ..., n connects into a complete Steiner tree, and the method for calculating the shortest path between two subtrees is: for all end points that belong to this two stalks tree, ask shortest path in twos, get that wherein the shortest paths as the shortest path between two subtrees; Calculate two end points, promptly put s to a some t, between the method for shortest path following steps are arranged:

(5.1.1) according to obstacle and end points s, t structure escape figure, here, escape figure is expanded to two ends by the horizontal sides of obstacle and vertical edge, up to running into obstacle, and a kind of connection layout that the line segment intersection after expanding like this forms;

(5.1.2) initialization candidate point set be some s}, the accessing points set is for empty, it is s that current point is set;

(5.1.3) all and current on escape figure adjacent and point that do not visit join in the candidate point set, calculate the value of turning back that these are newly added some points according to following rule:

The definition of directed edge u → v value of turning back: a given directed edge u → v and a final goal point t, establish L and be

By a t and with the perpendicular straight line of directed edge u → v, then:

Work as u, v is at the homonymy of L, and u is distal to v to the distance of L, then the value of turning back of u → v=0;

Work as u, v is at the homonymy of L, and u is bordering on v to the distance of L, then the length of the value of turning back of u → v=line segment u → v;

When line segment u → v and L meet at w, the length of the value of turning back of u → v=line segment w → v then;

So the value of turning back of point can define like this: the pathfinding process from source point to impact point, certain any value of turning back is the value of the turning back sum in all paths from source point to this point;

(5.1.4) select the minimum some q of the value of turning back to join in the accessing points set in candidate collection, it is q that current point is set;

If (5.1.5) final goal point t is not in candidate point set, repeating step (5.1.1)-(5.1.4) then;

If (5.1.6) final goal point t is in candidate point set, then t is joined in the accessing points set, the shortest path that finds like this is exactly the path that the point range in the accessing points set is formed according to the sequencing that is added into.

Images