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

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C024 492 Finals Page 492 9-10-2008 #7 Handbook of Algorithms for Physical Design Automation next subsection discusses a batched variant of the I1S approach, which offers runtime improvements in practice. 24.3.1 BATCHED 1-STEINER VARIANT Although a single 1-Steiner point may be found in O(n2 ) time, the required computational geometry techniques are complicated and not easy to implement. To address these issues, a batched variant of I1S was developed [19,54], which amortizes the computational expense of finding 1-Steiner points by adding as many independent 1-Steiner points as possible in every round. The batched 1-Steiner (B1S) variant computes MST(P, {x}) for each candidate Steiner point x ∈ H(P) (i.e., the Hanan grid candidate points). Two candidate Steiner points x and y are independent if MST(P, {x}) + MST(P, {y}) ≤ MST(P, {x, y}) that is, introducing each of the two 1-Steiner points does not reduce the potential gain in MST cost relative of the other 1-Steiner point. Given pointset P and a set of Steiner points S, each round of B1S greedily adds into S a maximal set of independent 1-Steiner points. Termination occurs when a round fails to add any new Steiner points (Figure 24.5). The total time required for each round is O(n2 log n). In three dimensions, I1S exploits a generalization of Hanan’s theorem to higher dimensions [41], namely that there always exists an optimal Steiner tree whose Steiner points are selected from the O(n3 ) intersections of all axis-orthogonal planes passing through points of P. The three-dimensional analog of Hwang’s result suggests that the Steiner ratio, i.e., the maximum cost(MST) ratio for three cost(SMT) dimensions is at most 53 ; however, this is only a conjecture and generalizing Hwang’s theorem to dimensions three and higher is still an open problem. An example consisting of six points located in the middle of the faces of a rectilinear cube establishes that 53 is a lower bound for the Steiner ratio in three dimensions. The I1S and B1S algorithms are highly parallelizable because each processor can independently compute the MST savings of different candidate Steiner points. The iterated Steiner approach is therefore very amenable to parallel implementation on grid computers [19,58]. As with I1S, the time complexity and practical runtime of B1S can be further improved using incremental/dynamic MST update techniques [62]. Moreover, by exploiting tighter bounds on the maximum MST degree in the rectilinear metric,∗ further runtime improvements can be obtained [19,58,63]. Batched 1-Steiner (B1S) heuristic Input: Set P of n points Output: Rectilinear Steiner tree spanning P While T = {x∈H (P)|MST(P,{x})> 0} = ∅ Do S=∅ For x∈ {T in order of non-increasing MST} Do If MST(P ∪ S,{x}) ≥ MST(P,{x}) Then S = S ∪ {x} P = P ∪S Remove from P Steiner points with degree ≤2 in MST(P) Output MST(P) FIGURE 24.5 The B1S algorithm. (From Kahng, A. B. and Robins, G., On Optimal Interconnections for VLSI, Kluwer Academic Publishers, Boston, MA, 1995 and Kahng, A. B. and Robins, G., IEEE Trans. Computer-Aided Design, 11, 893, 1992.) ∗ In Refs. [58,63] it was proven that the maximum rectilinear MST degree in two dimensions does not have to exceed 4, and that the maximum rectilinear MST degree in three dimensions does not have to exceed 14, settling these long-standing open questions. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C024 Minimum Steiner Tree Construction Finals Page 493 9-10-2008 #8 493 24.3.2 EMPIRICAL PERFORMANCE OF ITERATED 1-STEINER In benchmark tests, I1S and B1S compare very favorably with optimal Steiner tree algorithms, such as those of Salowe and Warme [64,65] on random uniformly distributed pointsets (i.e., the standard testbed for Steiner tree heuristics [2]). Both I1S and B1S exhibit very similar average performance in terms of solution quality, approaching 11 percent average improvement over MST cost, which is on average less than half a percent from optimal. Moreover, I1S and B1S produce optimal solutions on 90 percent of all random eight-point instances (and on more than half of all random 15-point instances). For n = 30 points, I1S and B1S are on average only about 0.3 percent away from optimal, and yield optimal solutions in about one quarter of the cases [19,58]. I1S and B1S also perform similarly well in three dimensions and in other Lk norms [19,58]. Empirical experiments also indicate that the number of rounds required by B1S grows very slowly (i.e., apparently logarithmically) with the number of points [19,58]. For example, on sets of 300 points the average number of B1S rounds is only 2.5, and was never observed to be more than 5 on any instance. As expected, over 95 percent of the total tree-cost improvement occurs in the first B1S round, and over 99 percent of the total improvement occurs in the first two rounds [19,58]. The average number of Steiner points generated by B1S grows linearly with the number of points (and is typically less than half the number of input points) [19,58]. An example of the output of B1S on a random set of 300 points is shown in Figure 24.6. Experimental data also indicates that only a small fraction of the Hanan candidates yield positive MST savings in a given B1S round, and that such positive-gain candidates are more likely to produce positive MST savings in subsequent rounds [19,54]. Therefore, rather than examining the FIGURE 24.6 Example of the output of B1S on a random set of 300 points (hollow dots). The Steiner points produced by B1S are denoted by solid dots. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C024 494 Finals Page 494 9-10-2008 #9 Handbook of Algorithms for Physical Design Automation MST savings of all Hanan candidates in a given round, subsequent rounds may consider only the candidates that produced positive savings in the previous round. In practice, this strategy significantly contributes to reduction in the time spent during each round, without affecting the solution quality. 24.3.3 GENERALIZATION OF I1S TO STEINER ARBORESCENCES The I1S algorithmic template also generalizes to produce Steiner arborescences, i.e., shortest path trees with minimum wirelength, which are known to yield high-performance critical net routings [15]. The iterated dominance (IDOM) graph arborescence heuristic of Ref. [66] recapitulates the I1S strategy, by greedily iterating over a given spanning arborescence construction. To construct a Steiner arborescence, the IDOM heuristic repeatedly finds Steiner candidates that reduce the overall spanning arborescence cost by the greatest amount, and includes them into the growing set of Steiner nodes. The reason that a spanning arborescence criterion is used to drive the Steiner arborescence construction is that the former is easy to compute [66], while the latter is NP-complete [67]. Arborescence constructions are described in greater detail in Chapter 25. 24.4 STEINER TREES IN GRAPHS A more general version of the Steiner problem arises when interpoint distances can be arbitrary, rather than induced by an underlying metric or a particular geometry. This topological, or graphbased version of the Steiner problem, occurs in practice when we wish to route a signal net in the presence of obstacles, congestion, or variable-cost routing resources, such as in field-programmable gate arrays [66]. More formally, given an arbitrary weighted graph with a distinguished vertex subset, the graph Steiner tree problem seeks a minimum-cost subtree spanning the distinguished vertices. Graph Steiner minimal tree (GSMT) problem: Given a weighted graph G = (V , E), and a distinguished set of nodes N ⊆ V , find a minimum-cost spanning tree T = (V , E ) with N ⊆ V ⊆ V and E ⊆ E. In particular, any node in V − N can serve as a potential Steiner point. As usual, each graph edge eij ∈ E has a real-valued weight wij , and the cost of a tree (or any subgraph) is the sum of the weights of its edges. The GSMT problem is NP-complete, even in the Euclidean or rectilinear metrics [43], because the geometric SMT problems are special cases of the general graph SMT problem. The method of Kou, Markowsky, and Berman (KMB) [53] was the first provably-good heuristic to solve the GSMT problem in polynomial time with approximation ratio of twice the optimal. 24.4.1 GRAPH GENERALIZATION OF ITERATED 1-STEINER The I1S approach generalizes to solve the Steiner problem in arbitrary weighted graphs, by combining the geometric I1S heuristic with the KMB [53] graph Steiner algorithm [19,66]. The resulting hybrid method inherits the good average-case performance of the I1S method, while also enjoying the errorbounded performance of the KMB algorithm. We refer to this hybrid method as the graph iterated 1-Steiner (GI1S) algorithm. The GI1S method is essentially an adaptation of I1S to graphs, where the MST in the inner loop is replaced with the KMB construction. That is, instead of using an MST subroutine to determine the savings of a candidate Steiner point/node, we use the KMB (or any other) approximation algorithm for this purpose. Thus, given a graph G = (V , E), a set N ⊆ V , and a set S of potential Steiner points, we define the following: KMB(N, S) = cost[KMB(N)] − cost[KMB(N ∪ S)] Thus, the GI1S template (Figure 24.7) repeatedly finds Steiner node candidates that reduce the overall KMB cost and includes them into the growing set of Steiner nodes S. The cost of the KMB tree over N ∪ S will decrease with each added Steiner node, and the construction terminates when there is no x ∈ V with KMB(N ∪ S, {x}) > 0. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C024 Minimum Steiner Tree Construction Finals Page 495 9-10-2008 #10 495 Graph iterated 1-Steiner (GI1S) heuristic Input: Weighted graph G = (V,E) and a set N ⊆ V Output: Low-cost tree T = (V ,E ) spanning N (i.e., N ⊆ V ⊆ V and E ⊆ E) S=∅ While T = {x ∈ V −N | KMB(N ∪ S,{x})> 0} = ∅ Do Find x ∈ T with maximum KMB(N ∪ S,{x}) S = S ∪ {x} Return KMB(N ∪ S) FIGURE 24.7 GI1S algorithm. (From Kahng, A. B. and Robins, G., On Optimal Interconnections for VLSI, Kluwer Academic Publishers, Boston, MA, 1995 and Alexander, M. J. and Robins, G., IEEE Trans. ComputerAided Design, 15, 1505, 1996.) The approximation ratio for GI1S is 2 · 1 − L1 ≤ 2 times optimal, where L is the number of leaves in the resulting tree. This follows from the KMB bound and from the fact that the cost of the GI1S construction cannot exceed that of the KMB construction [19,66]. If |N| ≤ 3 (e.g., a VLSI signal net with three or fewer terminals—a very common occurrence in VLSI layouts), GI1S is guaranteed to find an optimal solution. Although the worst-case performance ratio of GI1S is the same as that of KMB, in practice GI1S significantly outperforms KMB in terms of solution quality [66]. Given a faster implementation of the KMB method [68], the GI1S algorithm can be implemented within time O(|N| · |G| + |N|4 log |N|), where |N| ≤ |V | is the number of nodes to be spanned and |G| = |V | + |E| is the size of the graph. Moreover, like with I1S, the GI1S approach can be batched, and incremental/dynamic MST computations [62] can be exploited, resulting in further runtime improvements. Note that the GI1S template above can be viewed as an iterated KMB (IKMB) construction, and that KMB inside the inner loop may be replaced with any other graph Steiner approximation heuristic, such as that of Zelikovsky (ZEL) [52], yielding an iterated Zelikovsky (IZEL) heuristic. IZEL has the same theoretical performance bound as ZEL, namely 116 , but provides improved solutions in practice. Experiments have shown that these heuristics of increasing average solution quality are KMB < ZEL < IKMB < IZEL [66]. In general, iterating a given Steiner approximation heuristic greedily is an effective general mechanism to improve empirical performance without sacrificing the theoretical performance bounds. 24.4.2 LOSS-CONTRACTING APPROACH For arbitrary weighted graphs, the best Steiner approximation ratio achievable within polynomial time was steadily improved from 2 down to 1.5493 in a series of papers [52,53,55,69–73]. On the negative side, it is known that unless P = NP, the Steiner tree problem in general graphs cannot be approximated within a factor of 1 + for sufficiently small > 0 [74]. More recently, an improved nonapproximability lower bound of 96 for the graph Steiner problem was proved in Ref. [75]. 95 The graph Steiner tree heuristic with the best-known performance ratio, approaching 1 + ln2 3 ≈ 1.5493, was given by Robins and Zelikovsky [55,56]. This approach, called the loss-contracting algorithm (LCA), proceeds by adding full components to a growing solution, based on their relative cost savings. A full component is a Steiner tree over a terminal subset in which all of the terminals are leaves (Figure 24.8a). Any Steiner tree can be decomposed into full components by splitting all the nonleaf terminals (we assume that any full component has its own copy of each Steiner point, so that full components chosen by the algorithm do not share Steiner points). A Steiner tree that does not contain any Steiner points (i.e., where each full component consists of a single edge) is called a terminal-spanning tree. The LCA algorithm computes relative cost savings with respect to a shrinking terminal-spanning tree. All previous graph Steiner heuristics (except Ref. [70]) with provably good approximation ratios repeatedly choose appropriate full components and then contract them to form the overall solution. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C024 496 Finals Page 496 9-10-2008 #11 Handbook of Algorithms for Physical Design Automation a a c b d c b d (a) (b) (c) FIGURE 24.8 LCA idea: (a) full component K, where filled circles denote terminals and hollow circles denote Steiner points; (b) connected components of Loss(K) to be collapsed, with dashed edges belong to Loss(K); and (c) the corresponding terminal-spanning tree with the contracted Loss(K). However, this strategy does not allow the discarding of an already-accepted full component, even if it turns out later that a better full component conflicts with a previously accepted component (two components conflict if they share at least two terminals). The intuition behind the LCA method is to contract as little as possible so that a chosen full component may still participate in the overall solution, but not many other full components would be rejected. The LCA approach iteratively modifies a terminal-spanning tree T , which is initially MST(GS ), by incorporating into T loss-contracted full components greedily chosen from G. Each such component has positive gain, and therefore contains at least three terminals and has nonzero loss (see Refs. [55,56] for more details). The loss-contracting approach also solves the Steiner tree problem in quasi-bipartite graphs (i.e., where no two nonterminals are adjacent), achieving an approximation ratio of ≈ 1.28 times optimal within time O(mn2 ), where m and n are the numbers of terminals and nonterminals in the graph, respectively. This improves a previous primal-dual algorithm for Steiner trees in quasi-bipartite graphs [76] whose bound exceeds 1.5 times optimal. Similar techniques were also used to show that the graph version of the I1S heuristic described above [19,49] achieves an approximation ratio of 1.5 in quasi-bipartite graphs [55,56]. Along similar lines, the approximation ratio achievable for the Steiner tree problem in complete graphs with edge weights 1 and 2 was recently improved from the best previously known bound of 43 times optimal [74] to less than 1.28 times optimal [55,56]. 24.5 GROUP STEINER TREES Most papers on VLSI routing assume either implicitly or explicitly that each terminal consists of a single port. However, in actual layouts (e.g., in a gridded routing regime), a terminal to which a wire is to be routed can consist of a large collection of distinct, electrically equivalent ports [77–79]. Even though a wire may connect to any one of these ports, this degree of freedom is often not fully exploited in routing or in wiring estimation. This section addresses the general problem of minimumcost Steiner tree construction in the presence of multiport terminals, where rather than spanning a set of nodes, the objective is to connect groups of nodes. This is also known as the group Steiner problem (Figure 24.9), formulated as follows. Group Steiner problem [2,80]: Given a weighted graph G = (V , E) and a family N = {N1 , . . . , Nk } of k disjoint groups of nodes Ni ⊆ V , find a minimum-cost spanning tree in G containing at least one node from each group Ni . As in the classical Steiner problem, we are allowed to include optional Steiner nodes to reduce the cost of the tree interconnecting the groups of N. The problem of interconnecting a net with multiport terminals is a direct generalization of the NP-complete Steiner problem (i.e., in the classical Steiner problem each terminal contains exactly one port), and is therefore itself NP-complete. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C024 Finals Page 497 9-10-2008 #12 497 Minimum Steiner Tree Construction N2 N2 N3 N3 N1 N1 N4 (a) N4 (b) FIGURE 24.9 (a) Solution to the same group Steiner problem instance under the weak-connectivity assumption and (b) a feasible solution for the strong-connectivity version of the group Steiner problem. Ovals represent multiport terminals (i.e., groups), hollow dots represent ports within a terminal, and solid dots represent Steiner nodes. One version of the group Steiner problem, known as the strong-connectivity version, allows multiple connections to attach to different nodes in the same group (i.e., all the nodes of a group are implicitly connected to each other, which allows the solution to the group Steiner problem to be a forest—see Figure 24.9b). The version of the group Steiner problem described below involves weak connectivity: the solution must be strictly a tree, and intragroup edges must be represented explicitly in the solution (see Figure 24.9a). 24.5.1 APPLICATIONS OF GROUP STEINER TREES The group Steiner problem models several practical scenarios in VLSI layout design [78]: • Rotating and flipping a module can induce multiple locations for the given port, even in single-port-per-terminal instances. For a general module, there are up to eight possible orientations [80] (Figure 24.10a), and a given terminal can induce a group of up to eight nodes in the group Steiner problem (Figure 24.10b). The weak-connectivity model applies here, because the use of virtual ports is mutually exclusive. Rotate Flip (a) (b) FIGURE 24.10 (a) Module is rotated and flipped to induce a group of eight terminal positions, as shown in (b). Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C024 498 Finals Page 498 9-10-2008 #13 Handbook of Algorithms for Physical Design Automation • Complicated terminal geometry can easily have many ports located on multiple fabrication layers in grid-based maze routing regimes. These ports form a group in a strong-connectivity version of the group Steiner problem, because the ports are electrically equivalent, and a routing tree may connect to multiple ports of a given terminal. • Pin assignment problem [81] seeks to optimally determine pin locations on module boundaries. This can be modeled by the weak-connectivity version of the group Steiner problem, where exactly one pin is assigned to each module [78]. • Multiple ports on a block boundary may be connected inside the block and thus be electrically equivalent. These sets of ports form groups in the weak-connectivity group Steiner problem. • Instances of the group Steiner problem can also occur in hierarchical design methodologies, where some global nets are partially prerouted. Here, each connected component of a partially routed net can be modeled as a multiport terminal in a weak-connectivity version of the group Steiner problem. Despitethesenumerousapplications,surprisinglyfewroutingpapersaddressorexploitthefreedom to connect to any of multiple port locations. The first provably good approximation algorithms for the weak-group Steiner problem produced solutions k −1 times worse than optimal, where k is the number of groups [82]. In contrast, the strong-connectivity version, though also NP-hard, is somewhat more tractable than the weak-connectivity version: by converting an instance of the strong-connectivity version into an instance of the graph Steiner problem, then setting to zero the weight of every intragroup edge, we can efficiently solve the strong-group Steiner problem to within a factor of 2 times optimal or better, using any of the existing graph Steiner tree algorithms such as Refs. [52,53,56,83]. The following section√describes a group Steiner heuristic with an improved sublinear approximation ratio of 2·(2+ln k2 )· k times optimal, where k is the number of groups [77,78]. This algorithm is general and applies to arbitrarily weighted graphs. On the negative side, it is also known that the group Steiner problem is NP-hard to approximate to a sublogarithmic performance bound [77–79,84]. 24.5.2 DEPTH-BOUNDED GROUP STEINER TREE APPROACH The group Steiner algorithm relies on depth-bounded∗ trees. The motivation for using depth-bounded trees is twofold: (1) optimal depth-2-bounded trees can be used to approximate optimal group Steiner √ trees to within a factor of 2 · k, and (2) optimal depth-2-bounded trees in turn can be approximated efficiently, as discussed below. The overall Depth-Bounded Star (DBS) group Steiner algorithm [78,79] composes these two approximations, and therefore enjoys a performance bound that is the product of the two corresponding bounds. A given graph G may in general violate the triangle inequality, i.e., there may be edges (u, v) in G whose cost is greater than the cost of the minimum u–v path in G. An optimal group Steiner tree contains no such edges, because replacing such an edge with the corresponding shortest path will decrease the total tree cost, a contradiction to minimality. Therefore, without loss of generality, we replace G by its metric closure, defined as a complete graph where the cost of each edge (u, v) is equal to the cost of the minimum u–v path in G. Let a d-star be a rooted tree of depth of at most d (Figure 24.11a and b). It can be shown that for any arbitrary rooted tree T , there exists a low-cost 2-star spanning the leaves of T . This will imply that an optimal group Steiner tree can be approximated by a low-cost group Steiner 2-star (defined as a 2-star that spans all of the groups), which is exactly how the DBS group Steiner algorithm operates (Figures 24.12 and 24.13). The overall strategy in deriving a performance bound for the DBS group Steiner algorithm is based on bounding the total cost of 2-stars. Analyzing the edge reuse with respect to an appropriately ∗ The depth of a rooted tree is defined as the maximum number of edges in any root-to-leaf path. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C024 Finals Page 499 9-10-2008 #14 499 Minimum Steiner Tree Construction Root r (a) e Root r (b) e Root r e (c) FIGURE 24.11 DBS group Steiner algorithm: (a) tree T rooted at r may have an arbitrary depth; (b) 1-star and (c) 2-star are represented by dashed lines, which connect the root r to all leaves. To derive the performance bound of the DBS algorithm we sum the edge reuse; e.g., here the edge e is reused three times by edges of the 1-star in (b) and twice by edges of the 2-star in (c). √ selected set of intermediate nodes yields an upper bound of 2 · k times optimal on the cost of 2-stars, where k is the number of groups (similarly, the cost of an optimal Steiner 1-star is at most k times optimal) [77,78]. However, while an optimal Steiner 2-star is a reasonable approximation 2 of an optimal group Steiner tree, it is known that the problem of even approximating an optimal Steiner d-star is as difficult as approximating a minimum set cover. In particular, unless NP ⊆ DTIME[nlog log n ], a depth-2 group Steiner tree cannot be approximated to a factor of better than [1 − o(1)]. ln k times optimal, where k is the number of groups [84]. Nevertheless, it is possible to approximate a Steiner 2-star within a factor of 2 + ln k2 ≈ 1.307 + ln k times optimal [77–79]. Therefore, the overall performance bound for the DBS group Steiner heuristic will be the product of these two factors, namely the approximation bound of 2-stars with respect to optimal, times the bound with which 2-stars can themselves be approximated. The DBS group Steiner heuristic (Figures 24.12 and 24.13) √ therefore solves the group Steiner minimal tree problem with performance ratio 2 · (2 + ln k2 ) · k, where k is the number of groups. 24.5.3 TIME COMPLEXITY OF THE DBS GROUP STEINER ALGORITHM The time complexity of computing minimum-norm partial stars (a subroutine in the DBS algorithm) is O(|V |·k ·log k), where k is the number of groups. Approximating rooted 2-stars requires O(|V |·k 2 · log k) time. The total runtime of the overall DBS group Steiner heuristic (Figures 24.12 and 24.13) is therefore O(τ + |V |2 · k 2 · log k), where k is the number of groups, and τ is the time complexity of computing all-pairs graph shortest paths. Depth-bounded star (DBS) group Steiner algorithm Input: Weighted graph G = (V ,E), a family N of k disjoint groups N 1 ,. . .,N k ⊆V Output: A low-cost tree Approx spanning at least one vertex from each group N i For each node r ∈ V do Find a low-Cost 2-star Approx 2 (r) rooted at r intersecting each group N i , i = 1,. . .,k Output the least-cost 2-star Approx, i.e., cost(Approx) = minr ∈ V cost(Approx 2 (r)) FIGURE 24.12 DBS approximation algorithm for the group Steiner problem on arbitrary weighted graphs produces a low-cost Steiner 2-star. (From Bateman, C. D., Helvig, C. S., Robins, G., and Zelikovasky, A., Proceedings of the International Symposium on Physical Design, pp. 96–102, Napa Valley, CA, 1997 and Helvig, C. S., Robins, G. and Zelikovsky, A., Networks, 37, 8, 2001.) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C024 500 Finals Page 500 9-10-2008 #15 Handbook of Algorithms for Physical Design Automation r (a) (f) r r (e) (b) r (d) r (c) r FIGURE 24.13 Given an instance of the group Steiner problem, for each possible root r, the DBS heuristic: (a) finds the optimal 1-star, (b) finds the minimum-norm partial star (shaded region), (c) stores this star in the solution and removes its groups from future consideration, (d) finds the next minimum-norm partial star (shaded region), (e) repeats step (c) for the new partial star, and finally (f) finds the last minimum-norm partial star and outputs the union of all stored partial stars. A practical enhancement to the runtime of the DBS algorithm entails computing a group MST instead of a group SMT (i.e., computing a MST for a set of nodes containing exactly one port from each group). It can be shown that the optimal group MST is at most twice as long as the optimal group SMT. Thus, in approximating the group SMT by a group MST, only a factor of 2 √ is lost, which does not asymptotically increase the overall solution quality bound of 2 · (2 + ln 2k ) · k times optimal, yet yields substantial savings in runtime. 24.5.4 DEGENERATE GROUP STEINER INSTANCES While solving the group Steiner problem, optimizing degenerate groups (i.e., groups of size 1) as a special case can yield substantial improvements in solution quality as well as in runtime. The degenerate groups by themselves induce an instance of the classic Steiner problem, and such an Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C024 Finals Page 501 9-10-2008 #16 501 Minimum Steiner Tree Construction M1 M2 FIGURE 24.14 Group degeneracy can be exploited in solving the group Steiner problem. The set of degenerate groups (M1 ) is spanned with a classical approximate Steiner tree (left). Then, all the nondegenerate groups (M2 ) are spanned, together with an arbitrary degenerate group, using a group Steiner tree algorithm such as DBS (right). The combination of these two resulting trees spans the original instance of the group Steiner quite effectively, with an overall performance ratio equal to the sum of the two individual bounds. instance can be approximated efficiently with a constant performance ratio. Thus, to solve the SMT problem for degenerate groups, we may choose a provably good heuristic from among the numerous existing ones [19,52–56,58,85]. For example, in time O(|V |3) we may find a Steiner tree that is at most 11 times optimal [83]. All that remains now is connecting the SMT over the degenerate groups with 6 a tree spanning the other, nondegenerate groups, without degrading the overall performance ratio. To achieve this goal, we partition the set of all groups N = M1 ∪M2 into two subsets: the degenerate groups containing one terminal (M1 ) and the nondegenerate groups containing two or more terminals (M2 ). The combined DBS group Steiner heuristic is modified to work as follows: first, it computes the usual Steiner tree Approx1 for the terminals M1 using the algorithm from say Ref. [83]. Next, using the group Steiner heuristic (Figure 24.12), it finds the group Steiner tree Approx2 for the family of groups that includes all of M2 as well as a single arbitrary degenerate group from M1 . Finally, it outputs a minimum spanning tree over the union Approx1 ∪ Approx2 (Figure 24.14). If the number of degenerate groups is large, then the combined group Steiner heuristic will enjoy considerable runtime savings as compared to the basic DBS group Steiner heuristic (of Figures 24.12 and 24.13). Moreover, the heuristic also enjoys an improved overall performance bound of at most |M2 | + 1 11 . |M2 | + 1 + 2 · 2 + ln 6 2 where M2 is the set of degenerate groups of size 2 or more. In particular, if the number of nondegenerate groups is bounded by a constant independently of the total number of nodes in the graph (i.e., |M2 | = O(1)), then the above hybrid DBS algorithm will solve such instances of the group Steiner problem within a constant factor of optimal. 24.5.5 BOUNDED-RADIUS GROUP STEINER TREES The objective of delay minimization can induce wiring geometries that are substantially different from those dictated by an optimal-area objective, particularly in deep submicron regimes. This has motivated a number of bounded-radius∗ routing constructions [19,86,87]. The basic group Steiner tree approach can be easily extended to a bounded-radius construction, thereby yielding routing trees with source-to-sink pathlengths bounded by a user-specified parameter. ∗ The radius of a graph is defined as the maximum pathlength of any shortest source–sink path. Note that 2-stars implicitly have a radius bound of 2 · OPT, although an MST postprocessing step does not preserve this bound.

Handbook of algorithms for physical design automation part 52

Nội dung