Handbook of algorithms for physical design automation part 50.pdf (Sổ tay thuật toán)

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 472 Finals Page 472 23-9-2008 #5 Handbook of Algorithms for Physical Design Automation (a) (b) FIGURE 23.4 (a) Three-dimensional grid model for a three-layer circuit and (b) its corresponding grid graph, where solid lines represent intralayer connections and dashed lines represent interlayer connections. in G between vertices that correspond to neighboring ties. Here, each terminal is assumed to lie at the center of the grid cell that contains the terminal. In this model, edge capacities are set based on the number of routing tracks available passing through the tile boundaries, as will be discussed with more detail in Section 23.3. If a two-dimensional grid model is used (as in Figure 23.3), the routing tracks on every layer are lumped together to compute edge capacities. On the other hand, a three-dimensional grid graph can capture the characteristics of different layers more accurately. For example, there can be routing blockages on specific layers, and different layers can have different wire width and spacing requirements based on the technology being used. Although the three-dimensional grid model can capture the capacity differences in different layers, it requires layer assignment to be performed during global routing. Figure 23.4 illustrates a three-dimensional grid graph, where each layer has either horizontal or vertical preferred orientation. Observe here that there are only horizontal edges on a horizontal layer, and only vertical edges on a vertical layer. The global routing algorithms using tile-based graph model include Refs. [18–25]. 23.3 CAPACITY COMPUTATION As discussed earlier, a graph model G is used for global routing to capture the adjacencies and the capacities of the routing regions. Let u and v represent two vertices in G, corresponding to two adjacent routing regions. The capacity of the edge e ∈ G between u and v is set so as to reflect the available routing resources between the corresponding routing regions. A common capacity metric for edge e is the number of available routing tracks between the routing regions corresponding to u and v. In other words, capacity of e reflects the number of nets that can be routed between u and v. It is also possible to extend this simple track-based capacity metric to consider specific locations of blockages, pins, and preroutes. Furthermore, for the three-dimensional graph model described in Section 23.2.2, the routing resources consumed by the utilized vias can be modeled as well. For example, in Refs. [26,27], three types of edge capacities are defined: wiring capacity, through capacity, and interlayer capacity. The wiring capacity is computed by dividing the routing tile into slices based on the available routing resources, as shown in Figure 23.5. Then, the width (Wi ) and the depth (Di ) of each slice i is computed. Based on these, the wiring capacity is simply defined as i (Wi × Di )/D, where D is the depth of the tile. Similarly, the through capacity is based on the number of nets that can pass straight through the tile. It is computed as the sum of (Wi × Di ) values for each slice i that spans the entire tile (i.e., Di = D). Finally, interlayer capacitance corresponds to Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 Finals Page 473 23-9-2008 #6 473 Global Routing Formulation and Maze Routing D D1 W1 W2 D2 D3 W3 W4 W5 D4 D5 FIGURE 23.5 Capacity estimation model. Here, Wi and Di represent the width and depth of slice i in the given tile. (From Cong, J., Fang, J., and Khoo, K. -Y., IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 20, 633, 2001; Cong, J., Fang, J., Xie, M., and Zhang, J., IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 24, 382, 2005.) the number of vias that can be created within the tile, and is computed as the sum of empty spaces in the tile. In practice, high-precision capacity estimation can be complex, especially in the presence of arbitrary preroutes, varying wire pitches, and complex design rules. Furthermore, it can also be necessary to model the effect of interlayer connections (i.e., vias) on the horizontal/vertical wire capacities during global routing. In general, considering different factors during capacity estimation can lead to better correlation between global routing and detailed routing in the expense of increased algorithmic complexity. 23.4 ROUTING METRICS The key objective of global routing is to maximize routability in the consequent detailed routing step, while satisfying various routability constraints. In this section, we give an overview of the commonly used global routing metrics. 23.4.1 CONGESTION As described in Section 23.3, each global routing tile has a specific capacity. If the total resource usage of the nets assigned to a tile is more than its capacity, then the tile is defined to be congested. Clearly, the detailed router will not be able to route all the nets assigned to a congested tile because of lack of routing resources. However, in practice, detailed routers typically can tolerate some degree of congestion by spreading the wires to nearby not congested tiles, if any. A good congestion metric needs to consider not only the edge capacities, but also through capacities, as described in Section 23.3. Furthermore, an even spread of congestion throughout the routing region usually leads to better detailed routing solutions. Typically, global routers assign higher costs for congested-routing resources to discourage nets using these resources. For an even spreading of congestion throughout the routing region, some Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 474 Finals Page 474 23-9-2008 #7 Handbook of Algorithms for Physical Design Automation Cost Cost 1 Demand Capacity 1 (a) Demand Capacity (b) FIGURE 23.6 (a) Congestion cost function that penalizes congested resources only and (b) congestion cost function that promotes an even spreading of congestion. routers use cost functions that are linear functions of resource usage [20,28,29]. These cost functions are reported [20] to give better results than step functions, which only penalize congested resources. Figure 23.6 illustrates sample cost functions corresponding to these two types. 23.4.2 BEND COUNT As described in Section 23.2, each interconnect layer is used for either horizontal or vertical connections. If a routing path makes a change in its direction (e.g., from horizontal to vertical), this necessitates a layer change, as illustrated in Figure 23.7. So, each bend in a routing path indicates the need for the usage of a via, which connects adjacent interconnect layers. Typically, vias are undesirable because of their negative effects on signal integrity, delay, routing area, and manufacturing yields. Hence, a good global router needs to minimize the number of bends in the routing paths. 23.4.3 WIRELENGTH Another important metric for global routing is wirelength minimization. Increased wirelengths typically imply larger power consumption and larger delays. Although routing nets with the minimum wirelengths are desirable, a global router may need to introduce detours to avoid blockages or congested regions. Inherently, congestion minimization metrics can conflict with the wirelength and bend-count minimization metrics, as illustrated in Figure 23.8. So, the trade-off between these metrics should be carefully tuned based on the requirements of the global router. (a) (b) FIGURE 23.7 (a) Bend in a routing path is illustrated in the two-dimensional grid model and (b) the via corresponding to the bend is illustrated in the three-dimensional grid model. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 Finals Page 475 23-9-2008 #8 475 Global Routing Formulation and Maze Routing (a) (b) Low-congestion area High-congestion area FIGURE 23.8 Two possible configurations for a routing segment: (a) minimum wirelength, increased congestion and (b) increased wirelength, minimum congestion. 23.4.4 TIMING Timing optimization can be another important metric for high-speed designs. Typically, the critical nets are identified, and certain timing bounds are imposed on critical connections. These connections are then prioritized so that they can use faster resources, and scarce resources in the congested areas. Furthermore, some restrictions can be imposed on the maximum detours introduced while routing the critical connections. 23.4.5 COUPLING Because of the scaling down of device geometry and increasing clock frequencies, detrimental effects of coupling capacitances are becoming more significant. Coupling capacitance between two wires is proportional to the amount of parallel overlap between them, and inversely proportional to the distance between them. Avoiding coupling during global routing can be important for coupling management in general. Figure 23.9 [22] illustrates two configurations of a set of connections with and without coupling. Zhou and Wong [30] propose a Lagrangian relaxation-based methodology to minimize coupling during global routing. 23.5 SINGLE NET ROUTING In this section, we focus on the problem of global routing of a single net. Given a global routing grid with possible blockages, the objective is to find the best routing solution for one net. In Section 23.5.1, (a) (b) FIGURE 23.9 (a) Layout with coupling owing to long parallel wires and (b) layout with no coupling. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 476 Finals Page 476 23-9-2008 #9 Handbook of Algorithms for Physical Design Automation we start with a description of the classical maze routing algorithm [31], which is one of the earliest algorithms on automated wire-routing problem. Because this algorithm can be too expensive for large designs, several enhancements have been proposed in the literature, as discussed in Section 23.5.2. Inherently, maze routing algorithms are based on searching a path as a sequence of grid points. Another class of routing algorithms represent the paths as a sequence of line segments for the purpose of efficient execution. These line-search algorithms are described in Section 23.5.3. Another class of algorithms simplify the routing solution space to certain patterns such as I-, L-, and Z-shaped routes for the purpose of further speedup, as discussed in Section 23.5.4. For simplicity of the presentation, these algorithms are described in the context of nets with two terminals. In Section 23.5.5, we outline typical approaches to handle nets with multiple terminals. 23.5.1 LEE’S MAZE ROUTING ALGORITHM Lee’s algorithm [31] is one of the earliest routing algorithms proposed for automated wire routing. It is basically an extension of Moore’s shortest path algorithm [32] to a uniform grid structure. The basic algorithm operates on a single two-terminal net n, and a uniform grid G, which can have some of its cells specified as blockages. It is guaranteed to find a path between the terminals of the nets, and this path is guaranteed to be the shortest possible. The algorithm consists of two main phases. In the first phase, a wavefront is expanded from one of the terminals, as illustrated in Figure 23.10a. As the first step, the immediate neighboring cells of the terminal are marked with label 1. Then, at every step i(i > 1), the unmarked neighbors of the cells that were marked with label L at step i − 1 are marked with label L + 1. This process continues until the wavefront reaches the target terminal. Once the target terminal is found, the shortest path is constructed by backtracking in the second phase of the algorithm, as shown in Figure 23.10b. The backtracking operation starts with the target cell, and continues iteratively until the source cell 9 8 7 6 7 8 9 10 11 12 13 14 8 7 6 5 6 7 8 9 10 11 12 13 14 7 6 5 4 5 6 7 8 9 10 11 12 13 14 9 8 7 6 7 8 9 10 11 12 13 14 8 7 6 5 6 7 8 9 10 11 12 13 14 7 6 5 4 5 6 7 8 9 10 11 12 13 14 6 5 4 3 4 5 6 7 8 9 10 11 12 13 6 5 4 3 4 5 6 7 8 5 4 3 2 3 4 5 6 7 8 9 10 11 12 5 4 3 2 3 4 5 6 7 8 9 10 11 12 4 3 2 1 2 3 4 5 6 7 8 9 10 11 4 3 2 1 2 3 4 5 6 7 8 9 10 11 3 2 1 S 1 2 3 4 5 6 7 8 9 10 3 2 1 S 1 2 3 4 5 6 7 8 4 3 2 1 2 3 4 5 6 7 8 9 10 11 4 3 2 1 2 3 4 5 6 7 8 9 10 11 5 4 3 2 3 4 5 6 7 8 9 10 11 12 5 4 3 2 3 4 5 6 7 8 9 10 11 12 6 5 4 3 4 5 6 7 8 9 13 6 5 4 3 4 5 6 7 8 9 7 6 5 4 5 15 14 7 6 5 4 5 8 7 6 5 6 12 13 14 15 T 9 8 7 6 7 11 12 13 14 15 10 9 8 7 8 9 10 11 12 13 14 15 11 10 9 8 9 10 11 12 13 14 15 8 7 6 5 6 12 13 14 15 T 9 8 7 6 7 11 12 13 14 15 10 9 8 7 8 9 10 11 12 13 14 15 11 10 9 8 9 10 11 12 13 14 15 12 11 10 9 10 11 12 13 14 15 15 9 10 13 15 14 15 12 11 10 9 10 11 12 13 14 15 13 12 11 10 11 12 13 14 15 13 12 11 10 11 12 13 14 15 14 13 12 11 12 13 14 15 14 13 12 11 12 13 14 15 (a) 9 10 11 12 13 (b) FIGURE 23.10 Two phases of maze routing algorithm are illustrated: (a) wave expansion and (b) backtracking. The source and target terminals are marked as S and T , respectively. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 Finals Page 477 23-9-2008 #10 477 Global Routing Formulation and Maze Routing is reached. At one step, if the current cell c has label L, then backtracking continues with one of the neighbors of c that has label L − 1. If there are multiple neighbors with the same label, then a practical guideline for tie-breaking is to select the neighbor that will cause no change in the direction of the path (if any). This heuristic tends to choose the shortest paths with reduced bend counts. 23.5.2 MAZE-ROUTING ENHANCEMENTS The worst-case time complexity of the original maze routing algorithm is O(N × M), where N and M are the height and width of the grid, respectively. Several enhancements have been proposed in the literature to reduce the practical runtime and memory requirements of this algorithm. Furthermore, some generalizations of the problem formulation have been proposed to extend its application areas. Some straightforward speedup techniques have been proposed [33] to reduce the runtime of the original algorithm with only small modifications. One of them is the selection of the starting point of the wave propagation. If we start expanding the wavefront from the terminal that is closer to the circuit boundary, then the area of wave propagation will tend to be smaller. Another technique is to expand the wavefront from both terminals simultaneously until two wavefronts meet each other. This also reduces the number of grid points visited during wave propagation. Another heuristic is to define an artificial bounding box on the search region, and to allow wavefront expansion only within this bounding box. For the purpose of reducing the memory requirements of maze routing, Akers [34] proposed some coding schemes for cell labeling. In the original algorithm, k bits are necessary to represent a cell label, where k = lg(N × M), because the maximum label can be as large as N × M. However, it is possible to make the following observation. During backtracking, path computation is done by iteratively visiting the predecessor of each cell, starting from the target cell. Hence, it is only necessary to distinguish two types of neighbors for each cell C: the predecessors and the successors of C. As long as the predecessors of C can be distinguished from the successors of C, we do not need to store the labels of the cells. In the coding scheme proposed by Akers, the following sequence is used to label the cells during wavefront expansion phase: 1, 1, 2, 2, 1, 1, 2, 2, . . ., as illustrated in Figure 23.11a. Observe that the predecessor of each cell C is labeled different from the successor of cell C. During backtracking, the same sequence is used to construct the path from target to source, as illustrated in Figure 23.11b. In this coding scheme, only two bits need to be stored for each cell, representing four states: empty, blocked, 1, and 2. This can reduce the memory requirements of the algorithm significantly especially for large circuits. Some other heuristics involve manipulation of the direction of the wavefront propagation. Hadlock’s minimum detour algorithm [35] uses a variant of A∗ search algorithm [36] to reduce the size of the search space. It is straightforward to show that the length of path P between nodes A and B is equal to M(A, B) + 2d(P), where M(A, B) is the Manhattan distance between A and B, and d(P) is the detour number for path P (i.e., the number of cells directed away from target B). 1 1 1 1 2 1 1 1 1 1 1 2 1 2 2 2 2 2 1 2 1 1 1 1 1 1 S 1 1 (a) 1 T 1 1 1 1 S 2 2 1 1 1 1 1 T 1 1 1 2 2 1 (b) FIGURE 23.11 Coding scheme proposed by Akers is illustrated: (a) wavefront expansion and (b) backtracking. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 478 Finals Page 478 23-9-2008 #11 Handbook of Algorithms for Physical Design Automation Because the Manhattan distance between A and B is fixed for a given source–target pair, finding the path with the shortest path is equivalent to finding the path with the minimum detour number. Based on this observation, Hadlock’s minimum detour algorithm uses the detour numbers as the cell labels, and the cells with smaller detour numbers are expanded before the cells with higher detour numbers. Wavefront expansion phase of this algorithm is illustrated in Figure 23.12a with an example. The worst-case time complexity of this algorithm is the same as the original maze-routing algorithm; however, it is significantly faster in practice. Also, it is guaranteed to find the shortest path if one exists. Another algorithm that improves the runtime of the original maze-routing algorithm is Soukup’s fast maze algorithm [37]. In this algorithm, search is conducted iteratively in two different phases. In the first phase, wavefront expansion is done toward the target without changing direction until an obstacle is reached. Once an obstacle is reached, the second phase begins. In this phase, the same wavefront expansion methodology as the original maze-routing algorithm is used to search around the obstacle. Once a cell in the direction of the target is found, the first phase begins again for a directed search toward the target. Basically, this algorithm combines depth-first search (first phase) and breadth-first search (second phase) as an effective heuristic for wavefront propagation. Wavefront expansion phase of this algorithm is illustrated in Figure 23.12b with an example, where the edges expanded in the first phase are highlighted. This algorithm is guaranteed to find a path from source to target if one exists; however, the path found is not guaranteed to be the shortest one. Although the worst-case running time of this algorithm is still the same as the original algorithm, significant reduction of runtimes can be obtained in practice. The reason can be observed by comparing the sizes of the search spaces in Figures 23.10 and 23.12. Maze routing algorithms can also be generalized to multilayer problems in a straightforward way. The basic idea is to model the routing resources as a three-dimensional grid (as in Section 23.2.2), 2 (a) 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 1 S 0 0 0 0 0 0 0 1 2 2 1 0 0 0 0 0 0 0 0 1 2 2 1 0 0 0 0 0 0 0 0 1 2 2 1 0 0 0 0 0 0 0 2 1 0 0 2 1 0 0 2 2 2 2 T 2 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 S T (b) FIGURE 23.12 Wavefront expansion phases of (a) Hadlock’s minimum detour algorithm and (b) Soukup’s fast maze algorithm are illustrated from source S to target T . Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 Finals Page 479 23-9-2008 #12 479 Global Routing Formulation and Maze Routing 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 11 3 2 1 1 T 1 1 2 1 11 10 11 2 1 1 S 1 1 1 0 9 10 1 0 2 2 2 2 2 2 8 10 2 2 (a) 2 2 6 5 6 7 5 4 5 6 4 3 (b) 7 7 4 6 6 5 6 7 8 9 5 4 5 6 7 8 4 3 7 8 9 8 9 12 9 10 11 4 6 9 10 8 10 (c) FIGURE 23.13 (a) Routing grid with different weights assigned to each cell, (b) wave expansion from source S reaches target T the first time with cost 11, and (c) further expansion of the wavefront reduces the cost of the target cell T from 11 to 9. and to perform wave expansion in all three dimensions at each step. Note here that an edge in the third dimension corresponds to layer change, and can be assigned a higher cost to discourage via usage. As mentioned in Section 23.2.2, typically each layer is assigned one of the horizontal or vertical orientations for routing. For such designs, wave expansion on each layer can be limited to either horizontal or vertical orientations at each step. It is also possible to perform weighted path computations using maze routing algorithms. As discussed in Section 23.4, some paths can be more preferable than others because of various routing metrics, such as congestion minimization. For the purpose of incorporating different routing objectives into path computations, different edges in the routing graph can be assigned different costs. For instance, an edge passing through a congested region can be assigned a higher cost. In its original form, the maze routing algorithm does not guarantee to find the path with the minimum cost, because it is possible that a longer path can have smaller total cost. An example is illustrated in Figure 23.13. In Figure 23.13a, different weights are assigned to each grid cell based on a given metric. In Figure 23.13b, the wave expanded from the source reaches the target cell the first time. Note here that, if wave expansion is stopped as soon as the target is reached, then the path found will have a total cost of 11. However, if wave expansion is allowed to continue as in Figure 23.13c, then the path found will have a total cost of 9. In the original maze-routing algorithm, each cell is labeled at most once during wave expansion. In case of weighted routing edges, cells can be labeled multiple times, and the original worst time complexity of O(N × M) is not guaranteed anymore for an N × M grid. An efficient methodology to handle this issue is to prioritize cells during wave expansion based on their labels. Typically, a priority queue is used to expand the cells with the smallest labels at each step. This approach is actually a special case of Dijsktra’s shortest path algorithm [38], and its worst-case time complexity is O[N × M log(N × M)]. In practice, the well-known A∗ heuristic methodology [36] can further reduce the average runtime requirements of this algorithm. 23.5.3 LINE-SEARCH ALGORITHMS The main idea behind the line-search algorithms is to represent the routing search space as a set of line segments instead of grid points. This feature makes it possible to reduce memory and runtime requirements, compared to the maze routing algorithms, which typically need to allocate memory for each grid point. The first line-search algorithms were independently proposed by Mikami–Tabuchi [39] and Hightower [40] with small variations. An example illustrating Mikami–Tabuchi algorithm is given in Figure 23.14a. The algorithm starts with expanding one horizontal and one vertical line segment from each of the source and target points. After that, line expansion continues iteratively until one of the line segments originating from Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 480 Handbook of Algorithms for Physical Design Automation S S T T (a) Finals Page 480 23-9-2008 #13 (b) FIGURE 23.14 Illustration of the line-search algorithms proposed by (a) Mikami–Tabuchi and (b) Hightower. The dark circles represent the originating points of the line segments created. The path computed between source S and target T is highlighted. the source point intersects with one of the line segments originating from the target point. In each iteration, potential expansion points (represented as dark circles in Figure 23.14a) are identified on the most recently expanded line segments; then perpendicular line segments are created originating from these points. Once a line segment originating from the source intersects with a line segment originating from the target, the path is constructed by backtracking from the intersection point to the source and the target points. It is shown that this algorithm is guaranteed to find a path if one exists, and the path found is guaranteed to have the minimum possible number of bends. Observe that each grid point on a line segment created in Mikami–Tabuchi algorithm is a potential expansion point for new line segments. Hightower algorithm [40] differs from Mikami–Tabuchi algorithm in the way it chooses potential expansion points for the line segments. Instead of expanding a new line segment on each candidate point, Hightower algorithm identifies escape lines on the most recently created line segments based on the positions of the blockages. This algorithm is illustrated in Figure 23.14b. Observe that only the line segments that are extendable beyond the obstacle that blocked the previous line segment are considered as candidates in this algorithm. Compared to Mikami–Tabuchi algorithm, fewer line segments are generated. However, Hightower algorithm does not guarantee to find a path even if it exists, because the solution space is not explored completely. Typically, line-search algorithms are effective in minimizing the number of bends, and they do not guarantee shortest paths. The main assumption behind these algorithms is that routing can be accomplished with relatively few bends (hence few line segments) so that memory and runtime requirements are small. This is especially true for problems with low congestion and few number of blockages. However, if the routing problem is complicated, line-search algorithms run slower, and typically require more memory and runtime than maze routing algorithms. Furthermore, some class of line-search algorithms (e.g., Hightower algorithm [40]) do not guarantee to find a feasible path even if one exists. Because of their nature, line-search algorithms are more preferable early in the routing process when there are relatively fewer blockages in the design. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C023 Finals Page 481 23-9-2008 #14 481 Global Routing Formulation and Maze Routing FIGURE 23.15 Some routing patterns with 0, 1, and 2 bends are illustrated. 23.5.4 PATTERN ROUTING As discussed in Section 23.5.3, representing the routing solution space as a set of line segments can potentially reduce memory and runtime requirements. A more aggressive approach is to restrict the solution space to routes with predefined patterns, such as I-, L-, Z-, and U-shaped patterns. In general, routing patterns can be defined based on the number of bends on them. Figure 23.15 illustrates some patterns with 0, 1, and 2 bends. Because the objective of global routing is to generate rough routing solutions for the nets, pattern routing can be effectively used in global routing to reduce the runtime requirements. For example, in the experiments of Ref. [24], it is reported that on average about 2 percent of the nets are routed with maze routing, while the rest of the nets are routed with pattern routing. Yet, about 48 percent of the total runtime is spent on maze routing. In general, it is an effective heuristic to use pattern routing for the nets that have feasible few-bend solutions, and maze routing for the nets that require larger number of bends. 23.5.5 ROUTING NETS WITH MULTIPLE TERMINALS In the previous subsections, we mainly focused on routing algorithms for two terminal nets. However, it is possible to use these algorithms in the context of routing nets with multiple terminals. Note that the problem of finding the optimal route for a multiterminal net is an NP-complete problem. However, there are several heuristic-based algorithms that are used frequently in practice, as will be described in more detail in Chapter 24. A typical approach to route a multiterminal net N consists of two main steps: (1) generate a Steiner topology T for the terminals of net N and (2) perform point-to-point routing between the terminals and Steiner points of topology T . This two-step approach is illustrated in Figure 23.16 with an example. Another practical approach is to apply maze routing algorithm iteratively between terminal pairs of the net. Typically, wave expansion starts from the driver terminal Td until a receiver terminal Tr is reached. Then, the route between Td and Tr is implemented by backtracking, as in the original maze-routing algorithm. After that, the route between Td and Tr is regarded as the new source of A A S S C B (a) C B (b) FIGURE 23.16 (a) Steiner topology is generated for a net with three terminals: A, B, and C, where S is a Steiner point and (b) final routing solution is obtained by point-to-point routing between A–S, S–B, and S–C.

Handbook of algorithms for physical design automation part 50

Nội dung