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

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C031 622 Finals Page 622 29-9-2008 #9 Handbook of Algorithms for Physical Design Automation overall solution. This schema represents an iterative optimization technique; i.e., a pivot is made by tightening some violated constraint and then solving the resulting problem. 1. Route nets 2. Identify areas where the design constraints are violated 3. Identify nets/connections r to a. Remove r b. Reroute r This schema was proposed in the earliest papers on rip-up and reroute. An early, sophisticated discussion is in Ting and Tien (1983). They define a loop as a closed, nonintersecting sequence of boundaries in the grid graph. The loop constraint states that the number of times that connections cross a loop must be no greater than the maximum number of crossings allowed on the loop. For each connection, define its crossing count to be the number of times the connection intersects the loop. The crossing count of a net is the sum of the crossing counts of its connections. A net is said to violate the loop constraint if there exists a Steiner tree that can decrease the crossing count. As a specific example, suppose a net contains two pins that are outside the loop, but the routed connection for these two pins crosses the loop (Figure 31.4). This connection violates the loop constraint because there must be a Steiner tree that lies entirely outside the loop. Ting and Tien consider several loops simultaneously. Given a set of loops and a set of violating nets, they form a bipartite graph. One set of vertices are the violating nets, the other set are the loops, and there is an edge between a net and a loop if the net violates the corresponding loop constraint. Using this bipartite graph, Ting and Tien attempt to find an intelligent subset of nets to rip-up and reroute. They select a minimal set of nets such that, if removed, no loop constraint will be violated. (By minimal, this means that if any net was removed from the set, some loop constraint would be violated.) The smallest such set is called a set cover, which is also an NP-complete problem, so a suitable approximation is used. After the set of nets to reroute is obtained, Ting and Tien (1983) use a greedy strategy to obtain a net ordering, and then reroute the connections in that order. They note that their sequence may not remove all congestion, even if an uncongested solution can be found by another sequence. Such an issue is endemic to the iterative rip-up-and-reroute schema. 31.3.2.1 Issues The strength of iterative improvement is its consistent progress. Design constraint violations are found and resolved if possible. If the routing problem is feasible and the initial solution is of reasonable quality, the number of violations will be a small fraction of the design. If the probability of a successful rip-up and reroute is sufficiently high, the iterative improvement methodology will converge rapidly (see Dees and Smith [1981] for a probabilistic justification). A B L A B C (a) L C (b) FIGURE 31.4 (a) Loop L has four crossings, but it can only support two. (b) Net B is rerouted to avoid loop L. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C031 Finals Page 623 29-9-2008 #10 623 Rip-Up and Reroute L A B C FIGURE 31.5 Region R is the area outside of L. Routing in R prevents B from being successfully rerouted. The weakness of iterative improvement depends on the exact method used. Here are some issues that can arise. 31.3.2.1.1 Insufficient Rip-Up Ting and Tien take a direct approach; they remove violating routes. However, it is also possible that nets that are not in violation may need to be ripped up as well. (Figure 31.5) A net that is nearby a violation may control a resource that is needed to remove the violation. For instance, suppose that wire a avoids closed region R, but it must pass through R in an optimal solution. There is no incentive to reroute wire a when considering R because it does not cross R. Another example is if wire a is placed in the middle of a two-track gap (Figure 31.6). Near the gap, wires b and c cross. If the rip-up-and-reroute region is at the spot where b and c cross, and wire a is not in the region, wire a would not be considered. If, however, wire a is moved to make room for wire b, then the violation would be removed. 31.3.2.1.2 Net Ordering Ting and Tien noted that their net ordering strategy may not produce a global minimum. This is always the case with iterative optimization techniques. Many authors have noted this issue; the net ordering problem is dealt with using heuristics, Lagrangian weights, and randomization (Dees and Karger 1982). a (a) b c a b c (b) FIGURE 31.6 (a) Wires b and c cross. Assume the rip-up region is the cross-hatched area. Wire a is not moved. (b) If the rip-up region is enlarged to contain wire a, then the rip-up and reroute is successful. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C031 624 Finals Page 624 29-9-2008 #11 Handbook of Algorithms for Physical Design Automation 31.3.2.1.3 Lack of Progress Suppose that the rip-up and reroute of a region does not reduce the total cost. Such an issue is called a lack of progress. A lack of progress always occurs if a design constraint cannot be removed, but it may occur because of insufficient rip-up, for instance. 31.3.2.1.4 Oscillation Oscillation is a phenomenon where a sequence of rip-up-and-reroute operations results in a return to the original configuration. For instance, a reroute may move wire a out of a region, and then a successive reroute may place the route back in its original configuration. Oscillation may occur if a lack or progress is permitted. If oscillations do occur, there is the possibility of an infinite loop in the routing strategy. A special type of oscillation occurs when no change takes place during the rip-up and reroute of a connection. 31.4 RIP-UP-AND-REROUTE STRATEGIES The two schemas presented have strengths and weaknesses. For some routing problems, the strengths may suffice. However, the most successful routers use combinations of these schemas that form a strategy. A good example of the strategic development of a router is the router Mighty, developed by Shin and Sangiovanni-Vincentelli (1987), which mixes progressive rerouting and iterative improvement in a sophisticated way. The first pass of Mighty routes all the connections, but it does not commit them. The information is used to order the connections for the second pass. Specifically, connections are placed on a priority queue that is ordered by length. In the second pass, connections are either implemented if no network constraint is violated, or they are rerouted. Connections are rerouted so that they avoid conflicts, and the resulting connection is tested for quality. Connections that pass the quality test are placed on the priority queue. Connections that fail the quality test cause a sequence of modifications to the implemented connections. These modifications are either localized moves such as shifting the location of the wire (weak modifications) or more drastic moves that involve the rip-up of the conflicting connections (strong modifications). In the strong modification stage, connections are routed so that they are allowed to conflict with existing objects. During this stage, conflicts are taxed, and a minimum-weight path is used to identify the connections to remove. Mighty demonstrates the power of strategy. It deals with the schema issues in the following way. With respect to progressive reroute, the initialization problem is resolved by routing all connections independently of each other. They use a strategy for net ordering where certain simple connections are done first. There are two routing phases; in one phase, violations are not allowed, so Lagrangian weights are not an issue. In the second phase, violations are allowed, and Lagrangian weights are needed, though it is expected that the first phase will succeed most of the time. With respect to iterative improvement, there are two types of rip-up techniques. When using weak modifications, a history is stored to avoid oscillation. Lack of progress is dealt with using a sequence of more powerful (and extensive) rip-up-and-reroute operations. 31.5 HISTORY Rip-up and reroute was mentioned in early papers on printed circuit boards (PCBs) in the late 1960s. The earliest reference appears to be Dunne (1967). A slightly later work in a more visible publication is by Lass (1969). In that paper, Lass described a rip-up-and-reroute technique where the changes were localized to a small window. Further work on PCBs was given by Rubin (1974). For IC design, IBM played a particularly important role in developing area routers (Darringer et al. 2000) and in the use of rip-up and reroute to solve these problems. The central concepts were established by the mid-1980s. The schemas described here were also established in the earlyto-mid 1980s. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C031 Rip-Up and Reroute Finals Page 625 29-9-2008 #12 625 A good short survey of rip-up-and-reroute techniques for global routing appears in Hu and Sapatenekar (2001). One interesting rip-up-and-reroute algorithm that does not use path search as its main component appears in Meixner and Lauther (1990). Rip-up-and-reroute concepts appear in some recent work as well, such as Hu and Sapatnekar (2002), Liu and Sechen (1999), and Tseng and Sechen (1997). We note that much of the commercial work on rip-up and reroute is folklore. Key developers of proprietary routing software have not published all of their discoveries. 31.6 ENGINEERING PRACTICALITY Rip-up-and-reroute strategies are used in many commercial routers and are mentioned in recent technical papers. There are many reasons why rip-up and reroute is so common. First of all, rip-up-and-reroute algorithms always satisfy the network constraints. After the reroute step, one can perform an analysis such as a timing analysis or a process antenna check. Because the network constraints are satisfied, only a single routing representation is needed; intermediate results are lost. Rip-up-and-reroute algorithms typically allow individual control over a net. For instance, if a net is involved in a timing violation because it has too much cross capacitance, only that net and nearby affected nets need to be rerouted. Many of the rip-up-and-reroute schemas are easy to implement. If one implements the basic components of the routing algorithm, then the rip-up step consists of deleting routes and remarking the routing grid. For example, only an A∗ routing engine is needed in progressive rerouting. This represents a significant simplification from the standpoint of software engineering—there is only one place that would need to be updated or fixed when an enhancement is needed. Rip-up-and-reroute algorithms typically represent only one physical realization of a connection at a time. The routing representation is a significant memory consumer, so care must be taken to ensure that the memory footprint is small. In rip-up and reroute, the memory footprint is as efficient as possible because alternate solutions are not represented. Through the use of strategies, a variety of rip-up-and-reroute techniques can be used to solve difficult problems. In this sense, some different techniques dovetail in the same way as optimizing compiler techniques dovetail: each additional strategic tool improves router quality without affecting the quality of the other tools. Finally, rip-up-and-reroute algorithms have been used successfully in many practical applications. From the commercial risk–reward standpoint, there is little risk to implement an improved rip-up-and-reroute algorithm, and there is little reward if the underlying routing algorithm worked as well as the competition but took longer to develop. REFERENCES R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, New Jersey, 1993. C. Albrecht. Global routing by new approximation algorithms for multicommodity flow. IEEE Transactions on CAD, 20(5), 2001, 622–632. J. Darringer et al. EDA in IBM: Past, present, and future. IEEE Transactions on CAD, 19(12), 2000, 1476–1497. W. A. Dees, Jr. and P. G. Karger. Automated rip-up and reroute techniques. 19th Design Automation Conference, Annual ACM IEEE Design Automation Conference, IEEE Press, Piscataway, NJ, 1982, pp. 432–439. W. A. Dees, Jr. and R. J. Smith, II. Performance of interconnection rip-up and reroute strategies. Proceedings of the 18th Design Automation Conference, Nashville, TN, Annual ACM ICEEE Design Automation Conference, IEEE Press, Piscataway, NJ, 1981, pp. 382–390. G. V. Dunne. The design of printed circuit layouts by computer. Proceedings of Australian Computer Conference 3, 1967, pp. 419–423. R. T. Hadsell and P. H. Madden. Improved global routing through congestion estimation. DAC, Anaheim, CA. ACM, NY, 2003, pp. 28–31. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C031 626 Finals Page 626 29-9-2008 #13 Handbook of Algorithms for Physical Design Automation P. E. Hart, N. J. Nilsson, and B. Rafael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4, 1968, 100–107. J. Hu and S. S. Sapatenekar. A survey on multi-net global routing for integrated circuits. Integeration: The VLSI Journal, 31(1), 2001, 1–49. J. Hu and S. S. Sapatnekar. A timing-constrained simultaneous global routing algorithm. IEEE Transactions on CAD, 21(9), 2002, 1025–1036. F. K. Hwang, D. S. Richards, and P. Winter. The Steiner Tree Problem. Annals of Discrete Mathematics, 53, Amsterdam, The Netherlands, 1992. S. E. Lass. Automated printed circuit routing with a stepping aperture. CACM, 12(5), 1969, 262–265. H. Lin, T. Roughgarden, E. Tardos, and A. Walkover. Braess’s paradox, Fibonacci numbers, and exponential inapproximability, ICALP, Lisbon, Portugal, 2005, pp. 497–512. R. Linsker. An iterative-improvement penalty-function-driven wire routing system. IBM Journal of Research and Development, 28(5), 1984, 613–624. L. E. Liu and C. Sechen. Multilayer chip-level global routing using an efficient graph-based Steiner tree heuristic. IEEE Transactions on CAD, 18(10), 1999, 1442–1451. G. Meixner and U. Lauther. A new global router based on a flow model and linear assignment. Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, Santa Clara, CA, 1990, pp. 44–47. R. Nair. A simple yet effective technique for global wiring. IEEE Transactions on CAD, 6(2), 1987, 165–172. T. Roughgarden and E. Tardos. How bad is selfish routing? Journal of the ACM, 49(2), 2002, 236–259. F. Rubin. An iterative technique for printed wire routing. 11th Design Automation Workshop, Annual ACM IEEE Design Automation Conference, IEEE Press, Piscataway, NJ, 1974, pp. 308–313. H. Shin and A. Sangiovanni-Vincentelli. A detailed router based on incremental routing modifications: Mighty. IEEE Transactions on CAD, 6(6), 1987, 942–955. B. S. Ting and B. N. Tien. Routing techniques for gate array. IEEE Transactions on CAD, 2(4), 1983, 301–312. H. -P. Tseng and C. Sechen. Multi-layer over-the-cell routing with obstacles. IEEE Custom Integrated Circuits Conference, Santa Clara, CA, 1997, pp. 565–568. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 Finals Page 627 9-10-2008 #2 Techniques 32 Optimization in Routing Christoph Albrecht CONTENTS 32.1 32.2 32.3 32.4 32.5 32.6 Introduction.. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Global Routing Problem Formulation .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Fractional Global Routing and Linear Programming Duality .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Simplex Algorithm with Column Generation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Multicommodity Flow and Fractional Packing Problems .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Fully Polynomial-Time Approximation Scheme for Fractional Global Routing . . . . . . . . . . 32.6.1 Approximation Scheme Minimizing the Relative Congestion .. . . . . .. . . . . . . . . . . . . . 32.6.2 Approximation Scheme Minimizing the Total Weighted Netlength . . . . . . . . . . . . . . 32.7 Randomized Rounding .. . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 32.8 Extensions . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 32.9 Conclusion .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 627 628 629 632 633 634 635 639 640 641 642 642 32.1 INTRODUCTION Today’s routing instances are of enormous complexity. Millions of nets need to be routed on chip images that have tens of thousands routing channels in x- and y-direction and up to eight routing planes. Because of this complexity, routing is usually split up into two subtasks: global routing, which gives the approximate area for the Steiner tree of each net, and detailed routing, which performs a path search in this area and determines the actual tracks and vias for the nets. Global routing also provides a fast method to determine if a routing instance is feasible or not, or feasible only with long detours that may not be acceptable. If the global routing does not have a solution, it is necessary to change the placement. This chapter focuses on the global routing problem. Many global routers are based on an initial route of all nets followed by a rip-up and reroute procedure, which tries to reduce the congestion of the edges by rerouting segments of nets on overloaded edges as described in Chapter 31. For difficult instances, these algorithms may run forever and not come up with a solution, even though a solution exists. In this chapter, we discuss routing techniques that are based on the linear relaxation of an integer programming formulation of the global routing problem. If the linear program does not have a solution, by linear programming duality the dual linear program provides a proof, and this is a certificate that also the given global routing instance does not have a solution. The linear relaxation of the global routing problem allows multiple Steiner trees (or routes) for a single net, each Steiner tree having a nonnegative weight. The weights of the Steiner trees for each net sum up to 1. In the end, we would like to have an integer solution that has only on single Steiner tree for each net. This is achieved by randomized rounding as introduced by Raghavan and Thompson in 1987 [1,2]. 627 Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 628 Finals Page 628 9-10-2008 #3 Handbook of Algorithms for Physical Design Automation Solving the linear programming relaxation was (and still is) the computationally most expensive part in this approach and this was the reason why the approach was used only very limitedly in practice. This changed with new developments of approximation algorithms for the multicommodity flow problem and the fractional packing problem [3–8]. These problems are related to the linear relaxation of the global routing problem, the fractional global routing problem. We present an approximation scheme for the linear relaxation of the global routing problem, which is based on the approximation algorithms by Garg and Könemann [6] and Fleischer [7]. In the year 2000, it was possible to route the latest IBM application specific integrated circuit (ASIC) and microprocessor designs with up to 1,000,000 nets with this approximation scheme [9]. Subsequently, the algorithm was also used in commercial electronic design automation (EDA) tools for the X-architecture as discussed in Chapter 40. This chapter is organized as follows. In the next section, Section 32.2, we formulate the global routing problem. Then in Section 32.3, we discuss the linear relaxation and the dual linear program. In Section 32.4, we present early work on linear programming for global routing, in particular the simplex method with column generation. In Section 32.5, we describe the multicommodity flow problem and the fractional packing problem and show the relationship to the fractional global routing problem. In Section 32.6, we present a fully polynomial approximation scheme for the fractional global routing problem based on the multicommodity flow approximation schemes and prove the approximation ratio. In Section 32.7, we present randomized rounding as introduced by Raghavan and Thompson [1,2], which is used to achieve the final integer solution. In the last section, we discuss extensions of the approach. 32.2 GLOBAL ROUTING PROBLEM FORMULATION In global routing, an undirected grid graph G = (V , E) is constructed. A two-dimensional grid is placed over the chip. For each tile, there is a vertex v ∈ V and two vertices corresponding to adjacent tiles are connected by an edge. It is possible that the grid graph G consists of different layers such that via-capacities as well as capacities for different layers can be considered. Figure 32.1 shows a global routing graph with two layers, one for wiring in x-direction, the other for wiring in y-direction, and via edges in between. The number of edges in G is denoted by m, that is m = |E|. For global routing, only nets with pins in different tiles are considered. Let k be the total number of these nets and for each net i, i = 1, . . . , k, let Ni ⊆ V be the set of vertices for which there exists a pin of the net in the corresponding tile. The vertices of Ni are called the terminals of net i. For a given net i, let Ti be the set of all possible Steiner trees. This set might be restricted such that it contains only a subset of all possible Steiner trees—for example, for timing critical nets, the set may contain only the Steiner trees with minimum L1 -length. For the algorithms presented in this chapter, we assume that given any nonnegative lengths for the edges, a subroutine can be queried to compute a Steiner tree T ∈ Ti of minimum length with respect to these edge lengths. In practice, a heuristic that does not necessarily return the optimum Steiner tree is often good enough. FIGURE 32.1 Global routing graph with two layers and via edges. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 Finals Page 629 9-10-2008 #4 629 Optimization Techniques in Routing For each edge e = {u, v}, a capacity c(e) is computed according to the number of free channels between the two tiles corresponding to u and v, taking into account the entanglement of the nets that have all pins either in u or in v. Global routing asks for a Steiner tree Ti for each net i. Given these Steiner trees, the relative congestion of an edge e is defined as λ(e) := |{i|e ∈ Ti }|/c(e), and the maximum relative congestion is λ := maxe∈E λ(e). Several versions of the global routing problem have been studied. As a first approach, we will consider the task to find for each net i a Steiner tree Ti such that the maximum relative congestion is minimized. Later, in Section 32.6.2, we consider another version of the global routing problem: Find Steiner trees such that the maximum relative congestion is at most 1 and the total weighted netlength is minimized. With the notation above, the global routing problem for minimizing the maximum relative congestion can be formulated as a mixed integer linear program: min λ subject to i,T :e ∈ T ∈Ti xi,T ≤ λ c(e) for xi,T = 1 for e ∈ E i = 1, . . . , k (32.1) T ∈Ti xi,T ∈ {0, 1} for i = 1, . . . , k; T ∈ Ti In this mixed integer linear program, the variable xi,T is 1, if and only if for net i the Steiner tree T is part of the solution. The global routing problem is NP-complete as was shown by Kramer and van Leeuwen [10]. It is even NP-complete for the special case that all nets have only two terminals and the capacities are c(e) = 1 for all edges (edge-disjoint path problem), see Ref. [11]. The problem presented here is simplified compared to previous problem formulations. For example, it is possible to consider different wire widths for the nets and if the global routing graph models different layers, these wire widths may depend not only on the net but also on the edge. It is straight forward to adjust the algorithms presented here to incorporate additional factors that represent the wire width [9]. 32.3 FRACTIONAL GLOBAL ROUTING AND LINEAR PROGRAMMING DUALITY In this section, we consider the linear relaxation of the global routing problem introduced in the previous section. We then analyze and discuss the dual linear program. The linear programming relaxation of the mixed integer linear program (Equation 32.1) is the following: min λ subject to i,T :e ∈ T ∈Ti xi,T ≤ λc(e) for e ∈ E xi,T = 1 for i = 1, . . . , k xi,T ≥ 0 i = 1, . . . , k; T ∈ Ti T ∈Ti for (32.2) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 630 Finals Page 630 9-10-2008 #5 Handbook of Algorithms for Physical Design Automation We call the problem of solving this linear program the fractional global routing problem and denote the value of the optimum solution by λ∗ . For any feasible solution of this linear program, the relative congestion of an edge e is given by λ(e) := i,T :e∈T ∈Ti xi,T /c(e). We will sometimes write a solution (xi,T )i=1,...,k;T ∈Ti for the fractional global routing problem simply as a vector x. The dual linear program of the linear program (Equation 32.2) is given by max k zi i=1 subject to e∈E c(e)ye = 1 ye ≥ zi for i = 1, . . . , k; T ∈ Ti ye ≥ 0 for e∈E (32.3) e∈T By linear programming duality (a comprehensive overview about linear programming can be found in the books by Chvátal [12] and Schrijver [13]), any feasible solution of the dual linear program provides a lower bound on the optimum solution for the primal linear program, and for the optimum solutions equality holds. According to the second inequality in Equation 32.3, the value of zi has to be smallerthan the k minimum length of all Steiner trees T ∈ Ti with respect to the length ye for edge e. As i=1 zi is maximized, zi can be substituted by this minimum value, and by rescaling all lengths ye , e ∈ E by 1/ e ∈ E c(e)ye such that the first inequality in Equation 32.3 holds, we get the following theorem: Theorem 1 Given any nonnegative values ye for the edges e ∈ E, the expression k min ye i=1 T ∈Ti e∈T c(e)ye e∈E provides a lower bound on the optimum value of the fractional global routing problem. Moreover, there exist nonnegative values ye , e ∈ E, such that the expression above is equal to the optimum value of the fractional global routing problem. We briefly prove the weak duality, that the expression in Theorem 1 provides a lower bound on the minimum relative congestion. Let λ, xi,T for i = 1, . . . , k; T ∈ Ti be a feasible solution of Equation 32.2 and ye , e ∈ E, zi , i = 1, . . . , k of Equation 32.3. Then, we get λ e∈E c(e)ye ≥ e∈E ⎛ ⎝ i,T :e∈T ∈Ti ⎞ xi,T ⎠ ye = k i=1 T ∈Ti xi,T e∈T ye ≥ k i=1 min T ∈Ti e∈T ye ≥ k zi i=1 These inequalities show that for any optimal solution of Equations 32.2 and 32.3 the following holds: First, an edge e can have a positive length ye > 0 only if it has the maximum relative congestion, that is, λc(e) = i,T :e ∈ T ∈Ti xi,T . Second, every Steiner tree with positive xi,T has to be minimal with respect to the dual lengths ye , that is, e ∈ T ye = minT ∈Ti e ∈ T ye . Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 Finals Page 631 9-10-2008 #6 631 Optimization Techniques in Routing 2 2 2 1 2 2 2 2 2 2 Blockage Pins of Net 1 Pins of Net 2 (a) (b) 0 2 5 0 0 3 10 1 2 3 10 (c) 2 1 1 1 2 1 1 0 0 (d) FIGURE 32.2 Example for fractional global routing with the dual solution: (a) the chip with some blockages and the pins for two nets, (b) the global routing graph with the capacitances c(e), e ∈ E, (c) a fractional solution for the global routing problem minimizing the maximum relative congestion, and (d) an optimal dual solution ye , e ∈ E (without scaling). Figure 32.2 shows an example for the fractional global routing problem with an optimal fractional global routing for the primal problem in Figure 32.2c in which the fractional numbers specify the values for the variables xi,T , and an optimal solution for the dual problem in Figure 32.2d. We can verify Theorem 1: The maximum relative congestion is 25 and five edges have a congestion equal to the maximum relative congestion. For the dual solution, the value of the expression e ∈ E c(e)ye , which can be considered (speaking of flows) as the total volume availk able, is 10, and the value of the expression i=1 minT ∈Ti e ∈ T ye , the total volume needed, is 4. Hence, the value of the lower bound in Theorem 1 is 25 and the primal and dual solutions are optimal. In this example, the length of one edge in the dual solution has to be twice as high as the length of all other edges that have a positive length. In most cases, the dual solution just consists of a solution in which the edges with positive length form a cut and all edges in the cut have the same positive length. It is possible to extend this example such that in any optimal dual solution the length of one edge is required to be an arbitrary multiple of any other length [14].

Handbook of algorithms for physical design automation part 65

Nội dung