CN1529268A - Right Angle Steiner Tree Method under Obstacles in General Routing of Standard Units - Google Patents

Abstract

The right-angle Steiner tree method under obstacles during standard unit overall wiring belongs to the technical field of computer-aided design of integrated circuits, and is characterized in that: it first considers all obstacles as non-existent, and obtains the Steiner tree method under the obstacle-free set of endpoints of the network to be connected. The tree is the pre-Steiner tree; then, make the tree edge inside the obstacle in the pre-Steiner tree bypass the obstacle to generate a Steiner tree with obstacles; in the process of generating a Steiner tree with obstacles, according to the topological structure of the graph, carry out Appropriate preprocessing and postprocessing to optimize the line length optimization problem with consideration of time efficiency. It solves the problem of constructing right-angle Steiner tree which optimizes line length and time efficiency when there are many terminal points in the network to be connected.

Description

Right Angle Steiner Tree Method under Obstacles in General Routing of Standard Units

technical field

The right-angle Steiner tree method under obstacles in the overall wiring of standard cells belongs to the technical field of computer aided design of integrated circuits (ICAD), especially relates to the field of overall wiring design of standard cells (SC).

Background technique

In integrated circuit (IC) design, physical design is the main link in the IC design process, and it is also the most time-consuming step. A computer-aided design technique related to physical design is called layout design . In layout design, overall routing is an extremely important link, and its results have a great impact on the success of the final detailed routing and the performance of the chip.

The design scale of integrated circuits is currently developing from very large-scale (VLSI) and 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 Steiner minimal tree, RSMT) is an important issue in the VLSI/ULSI/GSI/SOC layout design, especially in the wiring research. In the actual wiring process, because the macro module, IP module and pre-wiring will all become obstacles , the RSMT method that considers 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 general wiring, it is one of the key issues in general 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 ([CYLee, 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 line network wiring under obstacles. the shortest path of . 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 15 ^th 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 0(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 ([DwHightower, A solution to the Line Routing Problem on the Continuous Plane, Proc.Of the 6 ^th Design Automation Workshop, 1969, 1-24.]), Mikami and Tabuchi in 1968 ([Mikami K. and Tabuchi K., A Computer Program for Optimal Routing of Printed Circuit Connectors, IFIPS Proc., 1968, H47, 1475-1478]) proposed line search methods, respectively. Its computational time and space complexity are both 0(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.

正好反向，则e₂即为极边)。G_G在复杂度上有一定的优势。在这些文献中提出了利用G_G来构造两端线网的最小Steiner树，另外也提出G_G可以用来构造多端线网，但是他们还没有具体实现。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 connection graph of 0(tlogt) 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, "Using the generalized connection graph of Θ(t) to find the shortest path when there are obstacles", Journal of Software, 2003, 14(2):pp.166-174.] introduces the generalized connected graph G _G , whose average complexity is Θ(t), where t is the number of polar edges of obstacles (three adjacent edges e ₁ (x ₁ , x ₂ ), e ₂ (x ₂ , x ₃ ), e ₃ (x ₃ , x ₄ ), if and

exactly reversed, then e ₂ is the polar edge). G _G has certain advantages in complexity. In these documents, it is proposed to use G _G to construct the minimum Steiner tree of the two-terminal network, and it is also proposed that G _G 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 a multi-end line network, and its complexity is 0(mn), where m and n are the number of obstacles and the number of end points of the line network respectively. 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 0(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. Except that the method involved in this patent application is different from this method, we can obtain better line length results under the same time complexity. Please refer to the following "Experimental data of the effect of the method of the present invention" for details. A comparison of the experimental data given in and their explanation.

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 document, 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.] Introduction A strongly connected graph G _C , whose complexity is 0(e ² ), 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 optimal steiner tree routing in the presence of rectilinear obstacles, 5615128, Mar.25, 1997], and [Ranko Scepanovic, Cupertino; Cheng-Liang Ding, SanJose. Toward optimal steiner tree routing in the presence of rectilinear obstacles, 5880970, Mar. 9, 1999] also use a similar strongly connected graph "escape graph" to obtain the Steienr tree of the multi-point line network with obstacles through the maze method or the method of Steinerizing the minimum spanning tree (spanning 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.

Document [Ganley J L, Cohoon JPRouting a multi-terminal critical net: Steinertree construction in the presence of obstacles [A]. In: Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS). London, UK, 1994.113-116.] Proposed The point of view is: since the 3-point and 4-point situations are relatively simple, they can be divided into 3-point groups or 4-point groups according to certain requirements in the multi-point situation. For the Steiner tree problem with obstacles, the time complexity of greedy 3-Steinerization (G3S) is 0(k ² n), and the time complexity of greedy 4-Steinerization (G ⁴ S) is 0(k ³ n ² ) . Where n is the number of optional Steiner points, and k is the number of iterations performed, which is less efficient. batched 3-Steinerization (B3S) selects three-point groups in batches, and the time complexity is 0(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.

In addition, literature [Huang Lin, Zhao Wenqing, Tang Pushan. An algorithm for the construction of Steiner trees 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.

The "novelty search" has been carried out, and the search report is shown in Attachment 1.

Contents of the invention

The object of the present invention is to propose a right-angle Steiner tree method under obstacles in the overall wiring of standard cells.

The general train of thought of the present invention is: at first regard all obstacles as non-existent, obtain the Steiner tree (we are called pre-Steiner tree) under barrier-free and connect each end point; Then pre-Steiner tree is transformed, Make the tree edge inside the obstacle in the pre-Steiner tree bypass the obstacle, and generate a Steiner tree under the obstacle. In the process of generating the obstacle Steiner tree, appropriate preprocessing and postprocessing can also be carried out according to the topological structure of the graph to obtain better construction results.

The present invention is characterized in that: it at first regards all obstacles as non-existent, and obtains the Steiner tree of the endpoint set of the network to be connected under no obstacle, that is, the pre-Steiner tree; then makes the tree in the obstacle interior in the pre-Steiner tree The edge bypasses obstacles to generate a Steiner tree with obstacles; in the process of generating a Steiner tree with obstacles, appropriate preprocessing and postprocessing are performed according to the topology of the graph; specifically, it contains the following steps in sequence:

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

The number of rows N _nr and the number of columns N _nc of the general wiring unit GRC,

The coordinates V _{nr, nc} (x, y) of all vertices in the general wiring diagram GRG, that is, the central point of the GRC, wherein, nr, nc represent rows and columns respectively, and x, y are the coordinates of the chip plane,

The capacity C _k of each edge e _k in GRG,

The total number of nets in the circuit Nsum, the netlist NetlistIndex of each net,

The total number of obstacles in the circuit Osum, and the position ObstacleIndex of each side of each obstacle;

(2). Read out the following data to generate GRG:

Read the number of rows N _nr and the number of columns N _nc necessary to divide the GRC on the wiring chip, and then read the coordinate values of the vertices necessary to generate the above-mentioned GRG on the wiring chip, and at the same time, give the above-mentioned vertices and each adjacent connection The edge e _k numbers of the two vertices;

(3). According to the read-in program, number each line net above;

(4). Generate an obstacle list according to the total number Osum of obstacles in the above-mentioned read-in circuit and the position ObstacleIndex of each side of each obstacle;

(5). Construct a pre-Steiner tree, that is, obtain a pre-Steiner tree by solving the endpoint set of the connection network without considering obstacles;

(6). Calculate and store the intersection points of each side of the pre-Steiner tree and the obstacle side, and delete the tree side inside the obstacle in the pre-Steiner tree;

(7). Preprocessing: According to the obstacle and the situation of the pre-Steiner tree, comprehensively consider the line length and time efficiency to decide whether to transform the pre-Steiner tree and how to transform it;

(8). According to the intersecting situation of the preprocessing tree obtained in step (7) and the obstacle, the tree edge is transformed, that is, the intersection of the tree edge and the obstacle of each group is reconnected around the obstacle, and the Steiner tree under the obstacle is obtained;

(9). Post-processing: starting from the optimized line length, the Steiner tree under the above obstacles is transformed.

The post-processing of the step (9) mainly includes de-ring processing and de-"empty U" processing, so as to further reduce the total length of the tree.

Method of the present invention has following characteristics:

Firstly, the method of the present invention can handle the line net with multiple endpoints (including the ability to handle two endpoints); it can handle the situation of complex obstacles (including the ability to handle simple obstacles of rectangle or L shape). 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 general wiring process, with specific implementation descriptions.

Secondly, compared with the existing multi-end line network Steiner tree construction method considering obstacles, the method of the present invention has better performance in terms of time complexity and line length. The time complexity of the method of the invention is only 0(mn), m and n are the number of obstacles and the number of end points of the line network respectively; meanwhile, the line length result obtained by the method is also very ideal. The method of the present invention is superior to the existing methods in comprehensive effect, please refer to the description of the experimental data given in the following "Experimental data of the effect of the method of the present invention" for details.

Description of drawings

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

Figure 2: Flowchart for transforming a pre-Steiner tree into a Steiner tree with obstacles.

Figure 3: Schematic diagrams of several situations of intersections between tree edges and obstacle edges.

(a) The intersection of a tree edge passing through an obstacle;

(b) The intersection situation when there is a Steiner point inside the obstacle;

(c) The intersection situation when the entire edge is inside the obstacle.

Figure 4: Schematic diagram of two boundary cases where tree edges intersect obstacle edges.

(a) Only one end of the tree edge is in contact with the obstacle;

(b) There are four possible situations where a part of the tree edge coincides with the obstacle edge.

Figure 5: Schematic representation of the "grouping" of intersection points.

Figure 6: Schematic diagram of an example of preprocessing.

(a) Two intersection points p1, p2 of a part of the pre-Steiner tree and the obstacle;

(b) A shortest path between point S1 and point S2.

Figure 7: Schematic diagram of an example of preprocessing II.

(a) Two intersection points p1, p2 of a part of the pre-Steiner tree and the obstacle;

(b) Remove the part of the pre-Steiner tree located inside the obstacle;

(c) When there is no preprocessing, the final generated result.

Figure 8: Preprocessing method description.

Figure 9: Schematic diagram of an example of preprocessing III.

(a) Two intersection points p1, p2 of a part of the pre-Steiner tree and the obstacle;

(b) preprocessing process;

(c) When there is preprocessing, the final result generated.

Figure 10: Schematic diagram of the Steiner tree construction process of net18.

(a) Enter the endpoints and barriers of the net to be connected;

(b) Pre-Steiner tree, and its intersection with obstacles;

(c) The result after removing the part of the pre-Steriner tree located inside the obstacle;

(d) The result after preprocessing;

(e) The result of changing the edge of the tree so that it bypasses the obstacle;

(f) The result after post-processing is the final output.

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 GRG, obstacles in the circuit, and wire network, the core part of this method is the process of constructing the Steiner tree. The overall flow chart is shown in Figure 1. The idea of this method is different from the previous methods. The method constructs the final result tree in two steps: the first step, ignoring all obstacles, and generating an initial barrier-free Steiner tree for the end points of the line network, that is, the pre-Steiner tree; Step, consider the obstacle, transform the pre-Steiner tree, get the Steiner tree considering the obstacle. The two steps of the method are described below.

Step 1: Construct a pre-Steiner tree, that is, obtain a Steiner tree by solving the endpoint set without considering obstacles, which is equivalent to step (5) in the above general process:

Since the pre-Steiner tree generated in this step is only a first draft of the final result, the principle of choosing the method of constructing a barrier-free Steiner tree is to focus on whether the method has a good time on the basis of ensuring that the result has a certain degree of optimization. efficiency. For example, a method with high efficiency and good results is obviously more suitable than a method that takes a lot of time to find a better result.

According to this principle, we choose the Steiner tree method under barriers as follows: when the number of endpoints is small, we choose the "DW method", which has been published in an international journal in 1972, see: [Dreyfus S E, and Wagner R A, "The Steiner problemin graphs", Networks, 1972, 1:195]. This method is an exact method, and the obtained result is the minimum Steiner tree, and the calculation time is shorter when the number of endpoints is small. But when the number of endpoints is large, the calculation time of the above precise method rises sharply, so some more efficient heuristic methods should be selected, such as "1-Steiner method", see [A.B.Kahng, and G.Robins, "A new class of iterative Steiner tree heuristics with good performance", IEEE Transactions on Computer Aided Design.11(7):893-902, July 1992.]; or "GTCA method", see [A.B.Kahng, Ion I.Mandoiu, Alexander Z. Zelikovsky, "Highly Scalable Algorithms for Rectilinear and Octilinear Steiner Trees", Proc Asia-Pacific DesignAutomation Conference (ASP-DAC), 2003].

Step 2: Considering the influence of obstacles, make corresponding transformations on the part of the tree edges intersecting with obstacles in the pre-Steiner tree, and obtain the Steiner tree with obstacles. This part corresponds to steps (6) to (9) in the above-mentioned overall process, and the flow chart of this step is shown in Figure 2. Among them, Proc1 to Proc4 correspond to steps (6) to (9) in turn.

Proc1 and Proc3 are the main work of this step method, while Proc2 and Proc4 are determined according to the degree of optimization of the resulting Steiner tree. The preprocessing in Proc2 can help reduce the path length for different situations, and the postprocessing in Proc4 can do some work to eliminate rings and further reduce the path length. Their specific methods will be introduced later.

1. Proc1 and Proc3 are the main body of the second step method. First calculate the intersection points of each side of the pre-Steiner tree and the obstacle side, and process and store these intersection points as needed (ie: Proc1); then according to the situation of the intersection point, transform the edge to obtain the Steiner tree under the obstacle (ie :Proc3).

(1) When dealing with the intersection of tree edges and obstacle edges in Proc1, the following situations need to be considered, as shown in Figure 3.

●A tree edge passes through the obstacle and produces two intersection points with the obstacle edge.

• There are Steiner points inside the obstacle, and the set of edges intersects more than two edges with the obstacle.

●If there is an entire edge inside the obstacle, this edge must be connected to two Steiner points, then the intersection of this group of edges and the obstacle is the intersection of the Steiner edge and the obstacle edge that are connected together by the inner edge of the obstacle set.

In addition, there are some edge cases to consider. In the program, obstacles are described by obstacle edges, and it is stipulated that the closed area formed by obstacle edges is a non-wiring area, and the outer part of the enclosed area formed by obstacle edges, including obstacle edges, is a routeable area. There are two boundary conditions, as shown in Figure 4:

● Only one end of the tree edge is in contact with the obstacle, and at this time it is treated as such that the edge does not intersect with the obstacle.

● A part of the tree edge coincides with the obstacle edge, and there are four possible situations for the convex polygon, which must be dealt with separately in the program.

(2) In addition, according to the requirements of Proc3, a concept of "grouping" the intersection points should be proposed. The principle of grouping the intersection points of a pre-Steiner tree and the obstacle side is: all the partial intersection points formed by connecting the pre-Steiner tree to the inside of the obstacle belong to the same group. Only the intersections belonging to the same group need to be reconnected after removal of the obstacle inner tree edges in Proc3. In the example of Fig. 5, {p ₁ , p ₂ , p ₃ , p ₄ } is a set of intersection points, and {p ₅ , p ₆ } is another set of intersection points.

The operation of changing the path in Proc3 is: first remove the edge or part of the edge inside the obstacle, and then reconnect around the obstacle. There are many ways to reconnect: the simplest method is to find a minimum path to connect all intersections (not grouped) on an obstacle along the obstacle edge, since this method also connects all intersections of different groups together, so Some unnecessary connections may be generated, increasing the path length. A slightly more complicated method can be processed by grouping the intersection points, and reconnecting the shortest path around the obstacle for each group of intersection points. This method does not take into account the influence caused by the overlapping of different groups of paths around obstacles, so this effect can be further considered for more detailed processing to make the paths around obstacles shorter.

2. Proc2 and Proc4, you can choose to use this step according to the degree of optimization of the results.

If only Proc1 and Proc3 are performed in the second step, the results obtained in some cases may not be very good. Different preprocessing for different situations can help reduce the length of the path. The following example illustrates one of the more important issues:

Figure 6(a) is the case where a part of a pre-Steiner tree intersects with an obstacle, and the edge needs to be changed. Obviously we can see that the shortest path length between S1 and S2 is the Manhattan distance, as shown in Figure 6(b).

However, if we directly find the intersection point and reconnect without preprocessing (that is, only execute Proc1 and Proc3 directly), as shown in Figure 7, we can only get the result of (c) in Figure 7. When the situation is very bad, The final result will be much worse than the minimum Steiner tree with obstacles.

So, to improve the results, some preprocessing needs to be done. The preprocessing flow is shown in Figure 8.

Figure 9 shows the preprocessing process and results of the above example. p1 is not adjusted, p2 is adjusted to p2', the result obtained after preprocessing is shown in Figure 9(c), it can be seen that the path length between two points at this time is the shortest distance between two points.

The post-processing is mainly to remove the ring and remove the "empty U", so as to further reduce the total length of the tree. A U-shaped circuit composed of three consecutive segments is called a "U", and an "empty U" means that there is still room for upward movement in the middle section of the U-shaped circuit. We adopt "TPT conversion technology". The method of removing rings is to search sequentially from the root of the tree to find the rings, and remove the largest edge in the rings.

The whole process of this method is illustrated below with an example of MCNC (Microelectronics Center of North Carolina) standard circuit network, 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 to serve the general wiring shall be implemented on a specific computer system, and the computer system is specifically described as follows.

A Sun V880 workstation;

Unix operating system;

Standard C programming language;

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

Steps (1)-(4): Preparatory work. Construct GRG grid; read in line network information; read in obstacle information and process these information. Among them, other tasks except "reading in the obstacle information and processing the information" are the same as the general preparation work of the general wiring of the standard unit, and the detailed description can be found in the literature [Applied national invention patents: Hong Xianlong, Jing Tong, Bao Haiyun, Cai Yici , Xu Jingyu. Invention name: A standard cell overall wiring method based on key network technology to optimize time delay. Application date: 2002/01/15. Application number: 02100354.8. It was published on 2002/07/24. ] and [applied national invention patents: Hong Xianlong, Jing Tong, Xu Jingyu, Zhang Ling, Hu Yu. Invention name: A standard cell overall wiring method for delay optimization considering coupling effects. Application date: 2002/12/17. Application number: 02156622.4. It was published on 2003/05/07. ] in the introduction. Here we only focus on the work of "reading in obstacle information and processing it".

Input network information: using the netlist representation of the 18th line network in the MCNC standard circuit example (endpoint information to be connected), then there are:

(net 18(vertexList 83 2 38 2 80 2 93 1))

——Explanation: 83, 38, 80, and 93 among them give the endpoint numbers to be connected in the GRG grid, and the coordinates of these endpoints in the xy plane are: (1246, 1312), (972, 656), (428 , 1312), (972, 1488). Vertex No. 83 is a leak point, Vertex No. 38 is a leak point, Vertex No. 80 is a leak point, and Vertex No. 93 is a source point. Their general formula can be expressed as:

(net number (VertexList vertex number source point/leakage point ...)),

Among them: the number 1 indicates the source point, and the number 2 indicates the leakage point.

The input obstacle information for line 18 is: obstacle 1(ybound(800 1000)xbound(400 1000)h_edge(400 800,1000800;400 1000,1000 1000)v_edge(400 800,400 1000;1000 800,1000 1000))obstacle 2(ybound(1200 1400)xbound(600 1000)h_edge(700 1200, 950 1200; 600 1250, 700 1250; 950 1250, 1000 1250; 600 1350, 700 1350; 1400)v_edge(600 1250, 600 1350; 700 1200, 700 1250; 700 1350, 700 1400; 950 1200, 950 1250; 950 1350, 950 1400; 1000 1250, 1000 1350))

——Explanation: The input obstacle information gives the obstacle ID number and description of each obstacle, including the maximum and minimum values of the obstacle in the x and y directions, and all horizontal and vertical sides of the obstacle.

Fig. 10(a) is a schematic diagram of the input net18 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.

After the information is read in, it is processed and stored in the corresponding data structure.

Step (5): Construct a pre-Steiner tree according to the endpoints of the network to be connected.

For example, the pre-Steiner tree obtained by net18 is:

Net ID 18

(972,1488)----->(972,1312)

(972,1312)----->(1246,1312)

(428,1312)----->(972,1312)

(972,656)----->(972,1312)

——Description: "(972, 1488)----->(972, 1312)" describes a tree edge of the pre-Steiner tree, and the coordinates of its two endpoints on the xy plane are (972, 1488) and (972, 1312). The rest are similar. This pre-Steiner tree has a total of 4 tree edges.

Figure 10(b) is a schematic diagram of the pre-Steiner tree of net18, in which the coordinates of each end point of the tree and the coordinates of the intersection of the tree and the obstacle are given.

Step (6): Calculate the intersection of the pre-Steiner tree and the obstacle. And delete tree edges that are inside the barrier.

After calculation, the intersection points of net18's pre-Steiner tree with obstacle 1 and obstacle 2 are:

Net ID 18

obstacle 1

intersections: (972, 800): 1, (972, 1000): 1

obstacle 2

intersections: (600, 1312): 2, (972, 1250): 2, (972, 1350): 2, (1000, 1312): 2

- Explanation: Obstacles obstacle1 and obstacle2 intersect the pre-Steiner tree of net18. Each intersection point is expressed as (x, y): link_No, where (x, y) represents the coordinate value of the intersection point on the xy plane, and link_No represents the group number of the intersection point (the intersection point of the same group needs to be changed in the step of changing the tree edge later) For details, please refer to the analysis on the concept of "grouping" in item 1(2) of the previous "Detailed Implementation" section).

Correspondingly, the part of the pre-Steiner tree that is in the barrier between the intersection points is deleted, and only the part that is outside the barrier is retained, as follows:

Net ID 18

Part of the tree out of the obstacles:

(972,1488)----->(972,1350)

(972,1250)----->(972,1000)

(972,656)----->(972,800)

(1000, 1312)----->(1246, 1312)

(428,1312)----->(600,1312)

The schematic diagram of the change is shown in Figure 10(c), in which the coordinates of the endpoints of each tree edge are given.

Step (7): Preprocessing process. Make changes to some tree edges in the pre-Steiner tree parts outside the barrier, depending on how the pre-Steiner tree intersects the barrier.

After calculation, the following original tree edges are replaced by new tree edges:

                                                                       

(972,1250)----->(972,1000) (1000,1250)----->(1000,1000)

Therefore, the part of the pre-Steiner tree that is outside the barrier obtained after preprocessing is:

Net ID 18

Part of the tree out of the obstacles:

(972,1488)----->(972,1350)

(1000, 1250)----->(1000, 1000)

(972,656)----->(972,800)

(1000, 1312)----->(1246, 1312)

(428,1312)----->(600,1312)

The pre-Steiner tree outside the obstacle after the preprocessing process is shown in Figure 10(d), in which the coordinates of the endpoints of each tree edge are given.

Step (8): Change the path. The work done in this step is the reconnection of the intersection around the obstacle.

The new tree edge obtained by reconnecting the intersection points is:

Net ID 18

Part of the tree reconnecting the intersections:

(600, 1312)----->(600, 1350)

(600, 1350)----->(700, 1350)

(700, 1350)----->(700, 1400)

(700, 1400)----->(950, 1400)

(950, 1400)----->(950, 1350)

(950,1350)----->(972,1350)

(972, 1350)----->(1000, 1350)

(1000, 1350)----->(1000, 1312)

(1000, 1312)----->(1000, 1250)

(1000, 1000)----->(1000, 800)

(1000,800)----->(972,800)

In this way, the transformed Steiner tree consists of two parts: the part of the pre-Steiner tree outside the obstacle that is retained (and possibly transformed by step (7)) and the new by the tree. The modified Steiner tree is shown below, this Steiner tree connects all endpoints and avoids obstacles.

Net ID 18

(600, 1312)----->(600, 1350) <1>

(600, 1350)----->(700, 1350) <2>

(700, 1350)----->(700, 1400) <3>

(700, 1400)----->(950, 1400) <4>

(950, 1400)------>(950, 1350) <5>

(950, 1350)----->(972, 1350) <6>

(972, 1350)----->(1000, 1350) <7>

(1000, 1350)----->(1000, 1312) <8>

(1000, 1312)----->(1000, 800) <9>

(1000,800)----->(972,800) <10>

(972, 1488)----->(972, 1350) <11>

(972,656)----->(972,800) <12>

(1000, 1312)----->(1246, 1312) <13>

(428, 1312)----->(600, 1312) <14>

——Explanation: "(600, 1312)----->(600, 1350)" describes a tree edge of the Steiner tree, and "<1>" is the serial number of this edge. The rest are similar. Figure 10(e) is the transformed Steiner tree, in which the serial numbers of each side are marked.

Step (9): post-processing. Cycles in the tree as well as "empty U's" are handled.

The result of the processing is: the original tree edge is replaced by the new tree edge as shown below.

                                                                                                         

(950, 1400)----->(950, 1350) Form "empty U" (950, 1400)----->(972, 1400)

(950,1350)----->(972,1350) (972,1400)----->(972,1350)

(972,1488)----->(972,1350) (972,1488)----->(972,1400)

After post-processing, the resulting Steiner tree of net18 with obstacles is shown below. Here it is the final result of adopting the method of the present invention.

Net ID 18

(600, 1312)----->(600, 1350) <1>

(600, 1350)----->(700, 1350) <2>

(700, 1350)----->(700, 1400) <3>

(700, 1400)----->(972, 1400) <4>

(972, 1400)----->(972, 1350) <5>

(972, 1350)----->(1000, 1350) <6>

(1000, 1350)----->(1000, 1312) <7>

(1000, 1312)----->(1000, 800) <8>

(1000,800)----->(972,800) <9>

(972, 1488)----->(972, 1350) <10>

(972,656)----->(972,800) <11>

(1000, 1312)----->(1246, 1312) <12>

(428, 1312)----->(600, 1312) <13>

——Description: "(600, 1312)----->(600, 1350)" describes a tree edge of the final result Steiner tree of net18 under obstacles, and the coordinates of its two endpoints on the xy plane They are (600, 1312) and (600, 1350) respectively, and "<1>" is the serial number of this edge. The rest are similar. The resulting Steiner tree under the obstacle of net18 has 13 tree edges.

Figure 10(f) shows a schematic diagram of the Steiner tree of the final result of net18, and the serial numbers of each side are marked in the figure.

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;

  Standard C programming language;

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

The wire net in the MCNC circuit is used as a test example, and the test result data of 9 wire nets are listed as follows:

  Net ID                                                

Number of endpoints [1] [2] [3] [4]

C2net22 2 442 754 754 0%

C2net33 2 1332 1332 1332 0%

C2net2 3 3572 3828 3828 0%

C2net17 3 1160 1188 1188 0%

C2net504 4 856 1256 1256 0%

C2net59 3 2028 3208 3268 1.87%

C2net609 4 2054 2894 3004 3.80%

C2net67 5 1880 2064 2156 4.46%

C2net177 6 2660 2660 2790 4.89%

[1] RSMT: RSMT length without barriers

[2] RSMTO: RSMT length with obstacles

[3] Ours: The length of RSMT with obstacles generated by the method of the present invention

[4]Redundancy＝(Ours-RSMTO)/RSMTO*100%

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 1.67%. At the same time, the solution execution time for all examples is: ≤1 second.

For the above-mentioned 9 wire nets, the test results of the method of the present invention and the "TPT" [5] method of Chen Desheng etc. (please refer to the introduction in "Background Technology") are listed as follows:

Net ID TPT Ours Comparison

Number of endpoints [5] [3] [6]

C2net22 2 902 754 19.00%

C2net33 2 1332 1332 0%

C2net2 3 3906 3828 2.03%

C2net17 3 1368 1188 15.15%

C2net504 4 1580 1256 25.80%

C2net59 3 3254 3268 -0.43%

C2net609 4 3004 3004 0%

C2net67 5 2418 2156 12.15%

C2net177 6 3008 2790 7.81%

[5] The "TPT" method solves the generated RSMT length under obstacles.

[6] Comparison＝(TPT-Ours)/Ours*100%

From the comparison of the above test results, it can be seen that the time complexity of the two methods is equivalent, but the line length result obtained by the method of the present invention is obviously better than that of the "TPT" method.

Claims (2)

1. the right angle Steiner tree method under the obstacle during standard block loose routing, it is characterized in that: it at first is considered as all obstacles not exist, try to achieve the end point set for the treatment of connecting diagram the Steiner tree under accessible promptly pre--Steiner tree; Make then in pre--Steiner tree at the tree limit of obstacle inside cut-through, generate the Steiner that has obstacle under and set; Have in the process of obstacle Steiner tree in generation,, carry out suitable pre-service and post-processed according to the topological structure of figure; Particularly, it contains following steps successively:

(1). the following data that set in advance are read in initialization, computing machine from the outside:

The line number N of global routing cell GRC _Nr, columns N _Nc,

All summits are the coordinate V of GRC central point among the loose routing figure GRG _{Nr, nc}(x, y), wherein, nr, nc represent row and column respectively, and x, y are the coordinates on chip plane,

Every limit e among the GRG _kCapacity C _k,

The total Nsum of gauze in the circuit, the net table NetlistIndex of every gauze,

The total Osum of obstacle in the circuit, each obstacle is respectively formed the position ObstacleIndex on limit;

(2). read following data to generate GRG:

Read out on the wiring chip and divide the necessary line number N of GRC _NrWith columns N _Nc, read out in the coordinate figure that generates necessary each summit of above-mentioned GRG on the wiring chip again, simultaneously, give above-mentioned summit and connect the limit e on adjacent two summits whenever _kNumbering;

(3). press read-in programme, be above-mentioned every gauze numbering;

(4). tabulate according to the position ObstacleIndex dyspoiesis that total Osum and each obstacle of obstacle in the above-mentioned circuit that reads in are respectively formed the limit;

(5). structure is pre--Steiner tree, promptly under the situation of not considering obstacle the end point set of connecting diagram found the solution and obtains pre--Steiner tree;

(6). calculate intersection point and storage that pre--Steiner sets each limit and obstacle limit, delete the tree limit that is in obstacle inside in pre--Steiner tree;

(7). pre-service: according to the situation of obstacle and pre--Steiner tree, take all factors into consideration the decision of line length and time efficiency in advance-whether the Steiner tree carry out conversion and how to carry out conversion;

(8). according to pre-service tree and the crossing situation of obstacle that step (7) obtains, conversion is carried out on the tree limit promptly respectively the tree limit of each group and the intersection point obstacle of obstacle are reconnected, obtain the Steiner tree under the obstacle;

(9). post-processed:, have the Steiner tree under the obstacle to carry out conversion to above-mentioned from optimizing line length.

2. the right angle Steiner tree method during standard block loose routing according to claim 1 under the obstacle is characterized in that: described step (9) post-processed mainly is that decyclization is handled and gone " empty U " to handle, with the total length that further reduces to set.

Images