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

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 632 Finals Page 632 9-10-2008 #7 Handbook of Algorithms for Physical Design Automation 32.4 SIMPLEX ALGORITHM WITH COLUMN GENERATION The first algorithm to solve the fractional global routing problem (Equation 32.2) by Hu and Shing in 1985 [15] used the simplex algorithm by Dantzig in 1951 [16] with column generation. This method finds an optimal solution even though it does not explicitly enumerate all the possible Steiner trees, nor has variables for all Steiner trees in memory. The method is limited in the size of the problem instances, and hence Hu and Shing propose a decomposition and cut-and-paste approach. In this section, we show how the simplex algorithm with column generation is applied to the fractional global routing problem. The simplex method goes from vertex to vertex along edges of the polyhedron underlying the linear program until an optimal vertex is reached. For a complete description of the simplex method, we refer the reader to Refs. [12,13,17]. Interesting is that this method requires a subroutine that computes minimal Steiner trees for nets with respect to a nonnegative length function on the edges, a subroutine that is also required by the approximation schemes is presented later. The linear program of the fractional global routing problem (Equation 32.2) can be rewritten with matrices as follows in a standard form for linear programs: ⎧ ⎨ M min λ : N ⎩ −c 0 ⎫ ⎛ ⎞ x ⎬ 0 I ⎝ ⎠ λ = , x, λ, v ≥ 0 1 0 ⎭ v (32.4) ⎛ ⎞ x −c I ⎝λ⎠ = 0 corresponds to the capacity v constraints on the edges, the first inequality in Equation 32.2. Each row corresponds to an edge and each column of the matrix M corresponds to a Steiner tree T for a net i and is the incidence vector for the edges of the corresponding Steiner tree. The vector v contains slack variables for the equality constrains. ⎛ ⎞ x The second constraint N 0 0 ⎝λ⎠ = 1 of the linear program ensures that the weights xi,T v for each net i and all Steiner trees T for the net sum up to 1, the second inequality in Equation 32.2. The matrix N has one row for each net and each row is the incidence vector for all the Steiner trees of the corresponding net. The dual of this linear program is as follows: In this linear program, the first constraint M max{1z : zN ≤ yM, yc ≤ 1, y ≥ 0} (32.5) The simplex method requires an initial vertex of the polyhedron as a starting point and basis of M −c I : for each net i, pick one Steiner tree T arbitrarily, set xi,T , = 1, and the matrix A = N 0 0 M −c the corresponding column of is part of the basis. We becomes part of the basis. Next, N i,T 0 can assume that this column is always part of the basis, because λ does not become 0. Finally, for all I are part edges that do not have the maximum relative congestion, the corresponding columns 0 e I of the basis. In case several edges have the maximum relative congestion, additional columns 0 e 1 −c M the matrix are chosen until the basis has |E| + k columns. We denote by 0 B 0 N B 1 2 Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 Finals Page 633 9-10-2008 #8 633 Optimization Techniques in Routing that has all the columns for the basis. This matrix has the full rank and can be inverted. The simplex algorithm computes a dual solution as follows: (−y, z) = M N B1 −c 0 I 0 −1 ⎛0⎞ ⎝ 1⎠ B2 0 −c is part of 0 the basis. Checking y ≥ 0 is straight forward. The inequality zN ≤ yM is checked by computing a minimal Steiner tree for each net i with respect to the length function ye , e ∈ E and comparing this length with zi . We will later see that the approximation algorithms require the same subroutine. If (y, c) is a feasible dual solution, the vertex for the primal linear program is an optimal solution. Otherwise a column corresponding to a violated constraint becomes part of the basis, another column leaves the basis, and if the vertex was not degenerate, a new vertex is computed. The simplex algorithm terminates in the worst case, after exponentially many steps; however, in practice, it is reasonably fast for most applications. We conclude this section by mentioning another linear programming approach for the global routing problem by Vannelli from 1989 [18]. In a first step, Vannelli reduces the complexity and size of the linear program by restricting the set of Steiner trees to only the minimal or near-minimal Steiner trees using also the result by Hanan, that a shortest rectilinear Steiner tree can be found in the grid induced by the terminals [19]. This restriction of the solution space may of course result in a suboptimal solution of the fractional global routing problem. Then he uses the Karmarkar algorithm [20], an interior point algorithm, which moves through the interior of the feasible region and reaches the optimal solution asymptotically. The runtime of the Karmarkar algorithm is polynomial, but it has the disadvantage compared to the simplex algorithm that it requires the complete linear program as input. The algorithm checks if this is a feasible dual solution: We have yc = 1 because 32.5 MULTICOMMODITY FLOW AND FRACTIONAL PACKING PROBLEMS In this section, we give an overview about multicommodity flow and fractional packing problems. These problems are similar to the fractional global routing problem. In fact, the fractional packing problem is a generalization of the fractional global routing problem. There have been many advances in the field of approximation algorithms for multicommodity flow and fractional packing problems and we will apply these to the fractional global routing problem in the next section. For this section, let G = (V , E) be a directed graph with an edge utilization (or capacity) function c : E → R+ . For a vertex v ∈ V we denote by δ + (v) all outgoing edges of v and by δ − (v) all incoming edges of v. Let s (the source) and t (the sink) be twospecified vertices. An s–t flow is a function f : E → R+ , which fulfills the flow conservation rule e∈δ− (v) f (e) = e∈δ+ (v) f (e) for all v ∈ V \{s, t} and the capacity constraints f (e) ≤ c(e) for all e ∈ E. The value of an s–t flow f is defined as value(f ) := e∈δ− (s) f (e) − e∈δ+ (s) f (e). It is possible to decompose an s–t flow into at most m = |E| flows along s–t paths: Given an s–t flow f of nonzero value, we find an s–t path P with f (e) > 0 for all e ∈ P. If we set x := min{f (e)|e ∈ P}, the function f : E → R+ with f (e) = f (e) − x if e ∈ P and f (e) = f (e) otherwise is again an s–t flow, but it has at least one edge e with f (e) > 0 less. Repeating this procedure until the value of the flow is 0 (flow along cycles may remain), we find x1 , . . . , xt and P1 , . . . , Pt such that i:e ∈ Pi xi ≤ f (e) for all e ∈ E. For the multicommodity flow problem, several commodities are given. Each commodity i has a source si , a sink ti , and a demand di . Let k be the number of commodities. The task of the maximum-concurrent multicommodityflow problem is to find an si –ti flow fi for each commodk ity i subject to the capacity constraints i=1 fi (e) ≤ c(e) for all e ∈ E such that the total throughput µ is maximized. The value of each flow fi is at least µ di . Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 634 Finals Page 634 9-10-2008 #9 Handbook of Algorithms for Physical Design Automation Other version of the multicommodity flow problem are the maximum multicommodity flow problem for which no demands are given and just the sum of the flows is maximized and the minimum-cost multicommodity flow problem for which a cost function for the edges is given in addition to the capacitances and the task is to minimize the total cost of all the flows. It is possible to formulate the maximum concurrent flow problem as a linear program in which the variables are the flow values for the edges fi (e). The size of this linear program is polynomial in the size of the input, hence we can find an optimal solution in polynomial time using the ellipsoid method [21]. However, for large problem instances, it is computationally impossible to solve the linear program optimally. Let Pi be the set of all si − ti paths. The following linear programming formulation makes use of the decomposition of flows into paths. max µ subject to xi,P ≤ c(e) for e∈E i,P:e∈P∈Pi xi,P = µdi for i = 1, . . . , k xi,P ≥ 0 for i = 1, . . . , k; P ∈ Pi (32.6) P∈Pi This linear program has exponentially many variables. Nevertheless, it is possible to compute an -approximate solution in polynomial time using this formulation implicitly as most of the variables xi,P can be 0. There has been a series of papers about fully polynomial-time approximation schemes (FPTAS) for multicommodity flow problems in the last decade. An approximation scheme is a family of algorithms that compute a solution within a factor (1 − ) of the optimal for any constant . If the running time can be bounded by a polynomial depending on the input size and 1/, then the scheme is called fully polynomial time. All approximation algorithms maintain a flow and then iteratively improve it by computing single commodity flows or single commodity flows restricted to paths with respect to a cost function depending on the congestion. The fractional packing problem is a generalization of the multicommodity flow problem. Given a convex set P ⊆ Rn , a matrix A ∈ R+m×n , and a vector b ∈ Rm , the task is to find an x ∈ P with Ax ≤ b. The approximation scheme, as for example by Plotkin et al. [4], requires a subroutine, which finds for a vector c ∈ R+n , a vector x ∈ P that minimizes cT x. The fractional global routing problem is a special case of the fractional packing problem: The convex set P is given by the constraints T ∈Ti xi,T = 1 for i = 1, . . . , k and xi,T ≥ 0 for i = 1, . . . , k, T ∈ Ti and the constraints Ax ≤ b represent the constraints i,T :e∈T ∈Ti xi,T ≤ λc(e) for e ∈ E. The subroutine needs to find a Steiner tree for each net minimizing a cost function and this cost function is the sum of some nonnegative cost of the edges of the Steiner tree. 32.6 FULLY POLYNOMIAL-TIME APPROXIMATION SCHEME FOR FRACTIONAL GLOBAL ROUTING In this section, we present and describe a fully polynomial-time approximation scheme for the fractional global routing problem. Carden et al. in 1996 [22] were the first to apply a multicommodity flow approximation algorithm to global routing. They use the approximation algorithm by Shahrokhi and Matula [3]. The approximation scheme presented here, first published in Ref. [9], is based on the approximation scheme by Garg and Könemann [6], but also use ideas from Fleischer [7]. The Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 Finals Page 635 9-10-2008 #10 635 Optimization Techniques in Routing approximation scheme iteratively finds Steiner trees with respect to dual lengths ye , then adjusts the dual lengths just for the Steiner tree found. 32.6.1 APPROXIMATION SCHEME MINIMIZING THE RELATIVE CONGESTION The approximation scheme that solves the fractional global routing problem for any given approximation ratio 1 + 0 is shown in Figure 32.3. The variables are initialized in lines 1 and 2. The algorithm is called with the parameters and M. The proof of the theorem in this section will show which value to choose for these parameters to get the desired approximation ratio. The algorithm runs through several phases. A phase starts in line 4 and ends in line 11. For each net i, a minimal Steiner tree T ∈ Ti with respect to lengths ye , e ∈ E is computed (line 7). For this Steiner tree, the variable xi,T is increased by 1 (line 8). To achieve that for each net i, the variables xi,T , T ∈ Ti , sum up to 1, all variables xi,T are divided by the total number of phases at the end of the algorithm. Finally, the dual variables ye are increased for all edges used by the Steiner tree T (line 9). The variables are increased more if the net uses a greater fraction of the capacity of the edge. Theorem 2 If there exists a solution for the fractional global routing problem with maximum relative congestion at most 1, the algorithm finds a (1 + 0 )-approximation in O 1 ln m λ 2 ∗ 0 1 3 m 1 1 with := (1+ ∈) . and M := 1− phases, if := min 1, 1 − 1 + 0 Moreover, the variables ye , e ∈ E, provide at some time during the algorithm a (1 + 0 ) − approximation for the dual linear program. The total number of phases of the algorithm depends on λ∗ , but usually in the application of global routing λ∗ is not arbitrarily small, for example, we can assume λ∗ ≥ 12 . 1 4 To prove this theorem, we follow the proof by Garg and Könemann [6], but also use parts from the proof by Fleischer [7] because we have a modified update rule for ye . Proof Let t be the total number of phases executed by the algorithm. We will prove that if the algorithm had stopped one phase before the last one, namely after t − 1 phases, the solution would have had the desired approximation ratio. (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) 1 Set y e : = c(e) for all e ∈ E. : = 0 for i = 1,...,k; T ∈ T i. Set x i,T While c(e)y < M e e∈E begin For i := 1 to k begin Find a minimal Steiner tree T ∈ T i for net i with respect to length y e , e ∈ E. Set x i,T : = x i,T + 1. 1 Set y e : = y e e c(e) for all e ∈ T. end end FIGURE 32.3 Approximation scheme for fractional global routing. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 636 Finals Page 636 9-10-2008 #11 Handbook of Algorithms for Physical Design Automation Let ye(p,i) be the value of variable ye , after net i has been considered in phase p and ye has been 1 increased in line 9, ye(0,0) = c(e) and let ye(p) := ye(p,k) be the value at the end of phase p. So we compute the minimal Steiner tree in phase p and iteration i with ye(p,i−1) as edge lengths. At the beginning, we have c(e)ye(0) = e∈E c(e) e∈E 1 =m c(e) (32.7) When the dual variables ye are increased in line 9 after a Steiner tree T has been found, the expression c(e)ye increases, and we have e∈E c(e)ye(p,i) = e/ ∈T e∈T e∈E ≤ c(e)ye(p,i−1) + c(e)ye(p,i−1) + e/ ∈T c(e)ye(p,i−1) e c(e)ye(p,i−1) e∈T 1 c(e) 2 1 1 1+ + 2 c(e) c(e) For the last inequality, we used ex ≤ 1 + x + x 2 for 0 ≤ x ≤ 1. We can assume c(e) ≥ 1 and because 1 ≤ 1 we have x = c(e) ≤ 1. Hence, 1 c(e)ye(p,i−1) 1 + (1 + ) c(e) e/ ∈T e∈T = c(e)ye(p,i−1) + (1 + ) ye(p,i−1) c(e)ye(p,i) ≤ e∈E c(e)ye(p,i−1) + e∈E e∈T Because ye increases only during the algorithm, for the Steiner tree T found in line 7, we have ye(p,i−1) ≤ min ye(p) T ∈Ti e∈T e∈T which means that at the end of phase p, we get c(e)ye(p) ≤ e∈E c(e)ye(p−1) + ∈ e∈E k i=1 min T ∈Ti ye(p) e∈T where := (1 + ). By linear programming duality (Theorem 1), the expression k λ(p) lb min ye(p) T ∈T i e∈T i=1 := c(e)ye(p) e∈E ∗ is a lower bound on the maximum relative congestion, that is, λ(p) lb ≤ λ . With this, inequality (Equation 32.8) can be rewritten as c(e)ye(p) ≤ c(e)ye(p−1) + λ(p) c(e)ye(p) lb e∈E e∈E e∈E which can be transformed to e∈E c(e)ye(p) ≤ 1 (p) lb e∈E 1−λ c(e)ye(p−1) (32.8) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 Finals Page 637 9-10-2008 #12 637 Optimization Techniques in Routing If we set λlb := maxp=1,...,t λ(p) lb , we get with Equation 32.7 c(e)ye(p) ≤ e∈E m (1 − λlb )p λlb m 1 + = (1 − λlb ) 1 − λlb λlb m 1+ ≤ (1 − ) 1 − ≤ p−1 p−1 (32.9) λlb (p−1) m 1− e (1 − ) For the last inequality, 1 + x ≤ ex for x ≥ 0 is used. An upper bound on the relative congestion of an edge e can now be derived: Suppose edge e is used s times by some tree during the first t − 1 phases, and let the jth increment in the relative congestion 1 of edge e be aj := c(e) for the appropriate i. After rescaling the variables xi,T , the relative congestion s 1 M of edge e is λ(e) = j=1 aj /(t − 1). Because ye(0) = c(e) and ye(t−1) < c(e) (because the condition in line 4 still holds before the last phase is executed) and because 1 aj e c(e) j=1 s ye(t−1) = we get M 1 aj e ≤ c(e) j=1 c(e) s It follows that e and hence s j=1 s j=1 λ(e) = aj ≤ M aj t−1 ≤ ln M (t − 1) (32.10) Because e ∈ E c(e)ye(t) ≥ M, solving inequality (Equation 32.9) with p = t for λlb gives a lower bound on the optimum solution value: λlb ≥ 1 − M ln (1 − ) (t − 1) m from which together with Equation 32.10, we get an upper bound on the approximation ratio ρ: maxe∈E λ(e) ≤ λlb 1− (t−1) ln M ∈(t−1) ln M m (1 − ) = ln M M (1 − ) ln m (1 − ) 1 m If M is now chosen to be M := ( 1− ) , we get 1 ln M M = 1 − ln m (1 − ) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 638 Finals Page 638 9-10-2008 #13 Handbook of Algorithms for Physical Design Automation such that ρ≤ (1 + ) (1 + ) = = 2 2 (1 − ) [1 − (1 + )] [1 − (1 + )]2 If ≤ 1, 1 + ≤ 2, we get ρ≤ If is chosen such that (1 + ) 1 ≤ 2 (1 − 4) (1 − 4)3 1 (1−4)3 because 1+ ≤ 1 1− ≤ 1 1−4 ≤ 1 + 0 , so we choose = min 1, 14 1 − 1 1+0 41 we get ρ ≤ 1 + 0 . After all, we have = O(0 ) and also = O(0 ). Because maxe∈E λ(e) ≥ λ∗ , we get from Equation 32.10 that λ∗ ≤ ln M (t − 1) which means that the maximum number of phases is bounded by t ≤1+ ln M 1 m = 1 + ∗ ln ∗ λ λ 1 − The last expression can be bounded by O( 21λ∗ ln m). 0 It is important that the actual implementation does not have one single variable xi,T for every possible Steiner tree, because there are exponentially many. A variable is only needed for a Steiner tree that was at some point during the algorithm the minimal Steiner tree and found by the algorithm in line 7 and for which the variable xi,T is greater than 0. To simplify the presentation of the algorithm and the proof we have omitted one idea that gives additional runtime improvements. The algorithm in Figure 32.3 computes a Steiner tree for all the nets in every phase. However, this is not necessary. The length (with respect to ye ) of a newly computed Steiner tree is stored and then in the following phases a new Steiner tree is computed for the net only if the length of the Steiner tree has increased by more than a certain factor (depending on ). It can be shown that still any approximation ratio can be achieved [9]. This idea was used by Fleischer [7] to reduce the theoretical runtime of the maximum multicommodity flow problem. Another practical speedup can be achieved with the Newton method as used in Refs. [5,9]: After p phases, the last Steiner tree computed has a weight of 1p in the current solution where all previously computed Steiner trees have a total weight of p−1 . After each Steiner tree is computed, the Newton p method is used to compute a new weight for the new Steiner tree with respect to the other Steiner trees minimizing an expression similar to ψ = e∈E eαλ(e) . Another advantage of this approximation algorithm (compared to some rip-up and reroute algorithms) is that not only the maximum relative congestion is minimized, but also that the congestion of the edges is distributed and that the algorithm works toward a solution that is optimal in a well-defined sense—the vector of the relative congestion of the edges sorted in nonincreasing order is minimal by lexicographic order [9]. Reducing the congestion beyond the maximum relative congestion on some edges can speed up the local router and also improves the signal integrity. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 Finals Page 639 9-10-2008 #14 639 Optimization Techniques in Routing 32.6.2 APPROXIMATION SCHEME MINIMIZING THE TOTAL WEIGHTED NETLENGTH The approximation scheme described in Section 32.6.1 can be modified such that the total weighted netlength is considered and minimized subject to the condition that the maximum relative congestion of the edges is at most 1. We follow the approach by Garg and Könemann [6] for the minimum-cost multicommodity flow problem. In addition to the capacity for each edge e = {u, v}, the L1 -length l(e) is given, that is, for an edge in x- or y-direction as the distance between the midpoints of the tiles corresponding to u and v. For each net i, a weight gi ∈ R+ is given. We would like to minimize the total weighted netlength, k l(e) xi,T . which is given by the expression gi i=1 T ∈Ti e∈T Let L be a target for the total weighted netlength. Then the constraint k i=1 gi T ∈Ti l(e) xi,T ≤ λL (32.11) e∈T is added to the linear program (Equation 32.2) of the fractional global routing problem. This constraint is very similar to the capacity constraints for the edges, the first constraint in (Equation 32.2), and the algorithm can be modified to treat this new constraint in the same way as the capacity constraints. To minimize the total weighted netlength, we want L to be as small as possible such that λ, the maximum relative congestion, is at most 1. This is achieved by binary search over L. In practice, the netlength in the final solution is only slightly higher compared to the minimum netlength if each Steiner tree is as short as possible ignoring capacities. This gives a good estimate for L. For the dual of the linear program, an additional dual variable yL for the constraint in Equation 32.11 is needed. The dual linear program is given by max k zi i=1 subject to c(e)ye + LyL = 1 e∈E [ye + gi l(e)yL ] ≥ zi for i = 1, . . . , k; T ∈ Ti for e∈E e∈T ye ≥ 0 yL ≥ 0 Figure 32.4 shows the modified approximation scheme. During the algorithm, minimal Steiner trees are computed with respect to the length ye + gi l(e)yL for net i and edge e ∈ E (line 7). The length of an edge e is the sum of the congestion cost ye and the wirelength cost gi l(e)yL of the edge. With the assumption that gi e∈T l(e) ≤ L for each Steiner tree T found in line 7 (which usually holds for the global routing problem), the proof in Section 32.6.1 can be extended to show that a (1+0 )–approximation for the fractional global with the constraint in Equation 32.11 routing problem 1 is found by the algorithm in Figure 32.4 in O 2 λ∗ ln m phases. If for some Steiner tree T we have 0 Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 640 Finals Page 640 9-10-2008 #15 Handbook of Algorithms for Physical Design Automation 1 Set y e : = c(e) for all e ∈ E and y L : = L1 . : = 0 for i = 1,...,k; Set x i,T T ∈ T i. While c(e)y + Ly < M e L e∈E begin For i := 1 to k begin Find a minimal Steiner tree T ∈ T i for net i with respect to lengths (y e + g i l(e)y L ), e ∈ E. (8) Set x i,T : = x i,T + 1. 1 (9) Set y e : = y e e c(e) for all e ∈ T. (1) (2) (3) (4) (5) (6) (7) Set Y L : = y L e (10) end (11) end gi e∈T l(e) L FIGURE 32.4 Approximation scheme for fractional global routing optimizing the total weighted netlength. gi e∈T l(e) > L, variable xi,T in line 9 is increased only by L/[gi e∈T l(e)], and another Steiner tree has to be found for the same net until the total increment of T ∈Ti xi,T is 1 (for details see Ref. [6]). 32.7 RANDOMIZED ROUNDING So far we have focused on solving the linear relaxation of the global routing problem. To come from a fractional solution of the global routing problem to an integer solution it is necessary to choose one Steiner tree for each net. This is done by randomized rounding, a technique developed by Raghavan and Thompson [1,2], which we present in this section. The technique of randomized rounding can be summarized as follows: RULE 32.1 Independently for each net i choose randomly one Steiner tree out of the set Ti . The probability to choose Steiner tree T is xi,T . The expected value for the relative congestion of an edge or of the maximum relative congestion after randomized rounding is equal to the relative congestion of the fractional solution. Randomized rounding may increase the relative congestion of some edges. However, it is possible to prove that there is a positive probability that the relative congestion does not increase by more than by a certain factor, and this factor decreases with increasing capacity of the edges. We will present these results with the proofs. In the following, we denote the probability of an event by P[·] and the expectation of a random variable X by E[X]. The following lemma was proved in this version by Raghavan and Spencer [23], and gives a variation of Chernoff’s bound [24]. The lemma bounds the tail of the distribution of the sum of independent random variable in [0,1]. To simplify the notation, we use b() := (1 + ) ln(1 + ) − . For small values of , b() is approximately 12 2 . Lemma 1 Let X1 , . . . , Xt be independent random variables in [0, 1]. Let X := t µ > p=1 E[Xp ] and > 0. Then P[X ≥ (1 + )µ] ≤ t t p=1 Xp , 1 e b()µ Proof We first consider the case µ = p=1 E[Xp ]. Using (1) the Markov inequality, (2) the independence of the random variables X1 , . . . , Xt , (3) (1 + )x ≤ 1 + x for 0 ≤ x ≤ 1, and (4) 1 + x ≤ ex , we compute Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C032 Finals Page 641 9-10-2008 #16 641 Optimization Techniques in Routing P[X ≥ (1 + )µ] = P[(1 + )X ≥ (1 + )(1+)µ] t X = P (1 + ) p=1 p ≥ (1 + )(1+)µ t t p=1 (1 + )Xp (2) tp=1 (1 + )E[Xp ] p=1 (1 + )Xp (1) ≥ 1 ≤ E = =P (1 + )(1+)µ (1 + )(1+)µ (1 + )(1+)µ (3) ≤ tp=1 (1 + E[Xp ]) (4) tp=1 eE[Xp ] ≤ (1 + )(1+)µ (1 + )(1+)µ t E[X ] e p=1 p eµ 1 = = = b()µ (1+)µ (1 + ) (1 + )(1+)µ e The lemma also holds if µ > E[X]. We add additional independent random variables in [0,1] to X until µ = E[X]. This only increases P[X ≥ (1 + )µ]. For an edge e ∈ E, we denote the relative congestion after randomized rounding with respect to Rule 32.1 by λ̂(e). The probability that the relative congestion of one edge increases by at least a factor of (1 + ) can be bounded as follows: Lemma 2 P[λ̂(e) ≥ (1 + )λ] ≤ 1 eb()c(e)λ Proof We apply Lemma 1: for i = 1, . . . , k, let the random variable Xi be 1 if for net i a Steiner tree is chosen that uses edge e, and zero k otherwise. The variables X1 , . . . , Xk are independent random variables in [0,1] and with X := i=1 Xp , we have E[X] = c(e)λ. Then, we have P[λ̂(e) ≥ 1 (1 + )λ] = P[X ≥ (1 + )c(e)λ] ≤ eb()c(e)λ . Finally, the probability of the overall failure, that is, the probability that any one edge has a relative congestion of at least (1 + )λ can now be bounded. Let λ̂ := maxe∈E λ̂(e) be the maximum relative congestion after randomized rounding and C := mine∈E c(e). Theorem 3 P[λ̂ ≥ (1 + )λ] ≤ e∈E 1 e b()c(e)λ ≤ m e b()Cλ m If is chosen so large that the expression eb()Cλ is smaller than 1, then the probability of success, λ̂ < (1 + )λ, is positive. Repeating the randomized rounding experiment increases the probability that one of the experiments is successful. It is possible to derandomize this random experiment. Assuming that for some nets a Steiner tree has already been chosen and that for each remaining net a Steiner tree is chosen according to Rule 32.1, the probability of failure is computed. This is a pessimistic estimator. It is then possible to choose one Steiner tree for the next net such that the probability of failure does not increase. Because the total probability was smaller than 1 at the beginning, in the end this probability is also smaller than 1, and because the Steiner trees for all nets are chosen, the final solution has to be a success. 32.8 EXTENSIONS The approach of solving a fractional global routing problem and then applying randomized rounding has been used successfully in practice and has been extended to consider additional tasks and objectives. Albrecht et al. [25] consider the problem of finding global routes that need to buffered. In addition, the sizes of the buffers and the widths of the wires are optimized. Some areas on the

Handbook of algorithms for physical design automation part 66

Nội dung