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

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C025 512 Finals Page 512 29-9-2008 #5 Handbook of Algorithms for Physical Design Automation BRBC algorithm Input: Graph G = (V,E ) (with radius R, source s0 ∈ V ), ≥ 0 Output: Spanning tree T BRBC with r (T BRBC ) ≤ (1 + ) · R and cost(T BRBC ) ≤ (1 + 2 ) · cost(T M ) Q = TM L = depth-first tour of T M Sum = 0 For i = 1 to |L|−1 Sum = Sum + dist(Li ,Li + 1 ) If Sum ≥ · distG (s0 ,Li + 1 ) Then Q = Q ∪ {edges in minpathG (s0 , Li + 1 )} Sum = 0 Output T BRBC = shortest paths tree of Q FIGURE 25.2 BRBC spanning tree algorithm produces a tree TBRBC with radius at most (1 + ) · R and cost at most (1 + 2 ) · cost(TM ). (From Cong, J., Kahng, A. B., Robins, G., Sarrafzadeh, M., and Wong, C. K., IEEE Trans. Comput. Aided Des., 11, 739, 1992; Kahng, A. B. and Robins, G., On Optimal Interconnections for VLSI, Kluwer Academic Publishers, Boston, MA, 1995.) and √23 · (1 + 1 ) times optimal, respectively. For λ-geometries (which allow wiring angles of iπλ [54]), a cost bound of ( √23 cos πλ ) · (1 + 1 ) times optimal can be shown for BRBC [16]. Experimental benchmarks indicate that both the BPRIM and BRBC algorithms run quickly and indeed yield a smooth trade-off between tree cost and tree radius [16,43]. In fact, on typical nets, the cost-radius trade-off is on average significantly more favorable than suggested by the theoretical bounds. For example, for ten pins and = 1, BRBC offers an average of 21 percent savings in tree radius over optimal, at the expense of only 13 percent average rise in tree cost over optimal. Moreover, the interconnects produced by BPRIM and BRBC have significantly better delay characteristics than classical Steiner trees, as verified by accurate timing simulators (e.g., SPICE) [16,43]. An alternative approach to the wirelength-radius trade-offs is the AHHK algorithm [40], which integrates Prim’s minimum spanning tree algorithm [58] and Dijkstra’s shortest path tree algorithm [57]. Prim’s algorithm minimizes the total wirelength, while Dijkstra’s algorithm minimizes the tree radius (i.e., the source-to-sink pathlengths). Thus, these two classic algorithms address, albeit separately, two major concerns in performance-driven interconnect synthesis. On the other hand, these two algorithms can be implemented similarly, by starting from the source node and adding one edge at a time until all the specified vertices in V are spanned. The main difference between these two algorithms is the criterion for selecting which edge to be added at each iteration. Prim’s algorithm [58] selects the edge with the minimum length. In particular, Prim’s algorithm iteratively adds to the growing tree T a new node vj and edge eij , where vi ∈ T and vj ∈ V − T are chosen to minimize the edge length |eij |. In contrast, Dijkstra’s algorithm [57] attempts to minimize the pathlength from the source node when selecting an edge. Specifically, Dijkstra’s algorithm iteratively adds to the growing tree T a new node vj and edge eij , where vi ∈ T and vj ∈ V − T are chosen to minimize the the sum of the edge length |eij | and the pathlength li from the source node to vertex vi in T . Generalizing this similarity between the two traditional methods of Prim and Dijkstra, the AHHK algorithm iteratively adds to the growing tree T a new node vj and edge eij , where vi ∈ T and vj ∈ V −T are chosen to minimize the sum of the edge length |eij | and the pathlength li from the source node to vertex vi in T times a fixed constant c. In this hybrid scheme, the chosen constant 0 ≤ c ≤ 1 serves to smoothly trade-off total wirelength againt tree radius (i.e., source-to-sink pathlengths). In particular, when c = 0, the resulting AHHK tree is identical to Prim’s minimum spanning tree, and when c = 1, the resulting AHHK tree is the same as Dijkstra’s shortest paths tree. Varying the value Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C025 Finals Page 513 29-9-2008 #6 513 Timing-Driven Interconnect Synthesis 4 4 2 5 2 3 3 1 1 6 8 (a) 5 7 8 6 7 (b) FIGURE 25.3 Examples of AHHK tree in the Euclidean plane, with (a) c = 13 (radius 15.9 and cost 26.4) and (b) c = 23 (radius 10.3 and cost 29.7). The edge labels indicate the order of adding the edges in the algorithm. (From Alpert, C. J., Hu, T. C., Huang, J. H., Kahng, A. B., and Karger, D., IEEE Trans. Comput. Aided Des. Integrated Circuits Syst., 14, 890, 1995. With permission.) Steiner node FIGURE 25.4 Examples of converting a spanning tree into a rectilinear Steiner tree through edge overlapping. of c between 0 and 1 results in intermediate trade-off trees between the two extremes of Prim’s and Dijkstra’s constructions. Figure 25.3 gives examples of AHHK trees for different values of the trade-off parameter c. Once an AHHK spanning tree is obtained, it can be converted to a rectilinear Steiner tree using edge overlapping. That is, if the bounding boxes of two tree edges overlap, the overlapping portions can form a new edge with one end being a Steiner node, as illustrated in Figure 25.4. Such edge overlappings can usually reduce wirelength with respect to the original spanning tree.∗ If there are multiple options for edge overlapping at a given step, we can break ties by giving priority to overlapping edges that yield the greatest wirelength reduction. 25.3 STEINER ARBORESCENCES Historically, the primary application of rectilinear Steiner minimum trees in VLSI CAD has been in global routing, because older physical design paradigms did not require the modeling of wires in the placement and floorplanning stages. However, the last several generations of technology have made it necessary to model the impact of wiring much earlier in the design process. For example, during placement, physical synthesis, and even floorplanning, we commonly wish to perform static timing ∗ While edge overlapping is a practical technique that reduces wirelength in typical scenarios, there are known pathological pointset instances where edge overlapping over any minimum spanning tree does not yield any wirelength savings whatsoever [61], whereas other Steiner-point inducing methods can still yield substantial savings [62,63]. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C025 514 Finals Page 514 29-9-2008 #7 Handbook of Algorithms for Physical Design Automation s0 FIGURE 25.5 Minimum-cost RSA. analysis to evaluate the performance of the current design iteration. To predict this with reasonable accuracy, a model of the wiring of each net must be available. Because blocks and cells may move quite often during these earlier phases of the physical design process, it is imperative to be able to efficiently and accurately estimate wiring delays. Such interconnect estimation was traditionally formulated as the Steiner problem. However, given the scaling trends in VLSI technology, a Steiner tree often results in inaccurate timing estimates, which may in turn misguide the floorplanning, placement, and physical synthesis design phases. On the other hand, Elmore delay analyses and cost-radius trade-offs have motivated research into routing constructions that simultaneously optimize interconnect length, source–sink paths, and a quadratic objective that optimizes the sum of source–sink pathlengths [16]. In particular, it was discovered that a minimum-cost rectilinear Steiner arborescence (RSA) heuristically addresses all of these objectives reasonably well [64], and thus provides highly accurate (as well as efficient) timing estimates. The Rectilinear Steiner Arborescence Problem: Given a signal net S in the Manhattan plane with source pin s0 , find a minimum-cost Steiner tree T that spans S, where the pathlengths in the tree T from s0 to every sink are equal to the corresponding Manhattan distances. The RSA problem seeks a minimum-cost shortest paths Steiner tree (Figure 25.5), and is thus a special case of the Steiner version of the BRMRT problem discussed above (where = 0). The RSA problem originated with early works such as Refs. [65,66]. Efforts were made to find a polynomialtime optimal arborescence algorithm, resulting in a proliferation of RSA heuristics [64,67–70], until it was finally proven that the RSA problem is NP-complete [71]. The first well-known effective RSA heuristic was proposed in Ref. [69]. Given a signal net in the Manhattan plane, the heuristic of Ref. [69] maintains a set of points, originally being all of the pins of the net, and repeatedly merges (i.e., connects) in this set a pair of points/pins whose bounding box is farthest from the source pin. This process terminates when the resulting arborescence spans the entire net. Choosing a new merge point that is dominated by two existing points allows the greatest flexibility for subsequent merges to optimize wirelength while always maintaining the shortest paths property of partial solutions. Figure 25.6 describes this heuristic more formally, while Figure 25.7 gives an illustrative execution example. The running time of this method is O(n log n). Empirical studies indicate that for typical nets, the RSA heuristic of Ref. [69] as well as the A-tree construction of Ref. [64], both yield solutions with average cost within 4 percent of the optimal RSA cost. On the theoretical side, both of these approaches have been proven to produce rectilinear arborescence trees that are never worse than twice the optimal [69], and pathological examples were found where both methods meet this twice-optimal worst-case bound [16]. Whereas, previous approaches typically handle cases where the sinks lie in the first quadrant (with respect to Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C025 Finals Page 515 29-9-2008 #8 Timing-Driven Interconnect Synthesis 515 Algorithm: Rectilinear Steiner arborescence (RSA) Input: A set of sink vertices {v 1 ,v 2 ,. . .,v n } in the first quadrant Output: A rectilinear Steiner arborescence rooted at (0, 0) Let be the set of subtrees (Initially = ∅) For each sink v i at location (x i ,y i ) Insert into a subtree T i rooted at (x i ,y i ) which contains only v i While || > 1 Do Find two subtrees T j and T k in such that x r + y r is maximum, where x r = min(x j ,x k ) and y r = min(y j ,y k ) Create a new subtree T r by creating a new root at (x r ,y r ) Connect the new root to (x j ,y j ) and (x k ,y k ) by a horizontal and/or a vertical edge Remove T j and T k from Insert T r into Construct a tree T by connecting (0, 0) to (x r ,y r ) by a horizontal and/or a vertical edge Return T FIGURE 25.6 The RSA algorithm of Ref [69]. a net’s source pin), an extension to all four quadrants, with running time O(n log n), was given in Ref. [72]. The RSA problem was generalized to arbitrary graphs as follows [73]. For an arbitrary weighted graph G = (V , E) and two nodes u, v ∈ V , let minpathG (u, v) denote the cost of a shortest path between u and v in G. The graph Steiner arborescence (GSA) problem can now be defined. The Graph Steiner Arborescence Problem: Given a weighted graph G = (V , E), and a specified net N ⊆ V with source pin/node n0 ∈ N to be interconnected in G, construct a least-cost spanning tree T = (V , E ) with N ⊆ V ⊆ V and E ⊆ E such that minpathT (n0 , ni ) = minpathG (n0 , ni ) for all ni ∈ N. As with the rectilinear arborescence problem, the GSA problem is NP-complete [73]. Constructing an arborescence can be viewed as folding or overlapping paths within a shortest paths tree, so as to induce the maximum wirelength savings while maintaining shortest paths. Indeed, this is the operational principle of the RSA heuristic of Ref. [69], among others. To generalize this strategy to arbitrary graphs, we define dominance in weighted graphs as follows [73]. Definition 1 Given a weighted graph G = (V , E), and nodes {n0, p, s} ⊆ V , we say that p dominates s if minpathG (n0 , p) = minpathG (n0 , s) + minpathG(s, p). Thus, a node p dominates a node s if there exists a shortest path from the source n0 to p that also passes through s (Figure 25.8a). Keeping in mind that the shortest path between a pair of nodes in a graph may not be unique, MaxDom(p, q) is defined as a node in V dominated by both p and q, which maximizes the distance minpathG [n0 , MaxDom(p, q)] to the source node n0 (Figure 25.8b). The dominated vertex MaxDom is chosen to be as far from the source node as possible, so as to yield the greatest possible wirelength overlap between the two paths, while still maintaining the shortest paths property with respect to the two target nodes. The above definitions enable the following path-folding arborescence (PFA) heuristic [73], as follows. Starting with the set of nodes N that initially contains the net (i.e., the source and all the sinks), we find a pair of nodes p and q in N such that m = MaxDom(p, q) in G is farthest away from the source node n0 among all such pairs. We then replace p and q in N with m, and iterate until only the source remains in N. The overall GSA solution is formed by using shortest paths Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C025 516 Finals Page 516 29-9-2008 #9 Handbook of Algorithms for Physical Design Automation x + y = c2 x + y = c1 Source Source Source (a) (b) (c) x + y = c3 x + y = c4 Source Source (d) Source (e) (f) FIGURE 25.7 The RSA algorithm of Ref [69]. The solid circle in (a) is the source and the hollow circles are sinks. The first four iterations are shown in (b–e). At the beginning (a), there are seven (one node) subtrees, one per sink, plus the source itself. In (b) a pair of (distant-from-the-source) subtrees is merged to form a new subtree, resulting in five remaining subtrees. Trees continue to merge during subsequent iterations, resulting in the final RSA shown in (f). q minpathG(s, p) p p s m = MaxDom(p, q) minpathG(n0, s) n0 (a) minpathG(n0, p) minpathG(n0, m) n0 (b) FIGURE 25.8 Defining dominance in graphs: (a) Graph node p dominates node s when minpathG (n0 , p) = minpathG (n0 , s) + minpathG (s, p) and (b) shows MaxDom(p, q) with respect to p and q. To maximize the wirelength savings, we seek the farthest point m = MaxDom(p, q) from the source n0 , where p and q both dominate m. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C025 Finals Page 517 29-9-2008 #10 Timing-Driven Interconnect Synthesis 517 Path-folding arborescence (PFA) algorithm Input: Weighted graph G = (V, E ) and net N ⊆ V with source n0 ∈ N Output: A low-cost shortest-paths tree spanning N in G M =N While N = {n0 } Do Find a pair {p,q } ⊆ N such that m = MaxDom(p,q ) has maximum minpath(n0 ,m ) over all {p,q } ⊆ N N = {N −{p,q }} ∪ {m} M = M ∪ {m } Output the tree formed by connecting each node p ∈ M (using a shortest path in G ) to the nearest node in M that p dominates FIGURE 25.9 The graph-based PFA heuristic. M initially holds all the nodes to be spanned, and is then augmented with the MaxDom Steiner points found during each iteration. (From Alexander, M. J. and Robins, G., IEEE Trans. Comput. Aided Des., 15, 1505, 1996.) in G to connect each MaxDom(p, q) to p and to q (Figure 25.9). Empirical experiments indicate that the PFA method is effective in producing shortest paths trees with low wirelength (i.e., PFA’s average wirelength is close to that of the best existing graph Steiner heuristics) [73]. This observation was reconfirmed in Ref. [11], where it was demonstrated that using rectilinear arborescences during physical synthesis only induces an average of 2–4 percent wirelength penalty over rectilinear Steiner trees, while offering substantial accuracy gains in performance estimation. A different approach to the GSA problem generalizes the Iterated 1-Steiner (I1S) approach of Kahng and Robins [16,63] to yield an effective iterated-dominance (IDOM) arborescence methodology for arbitrary weighted graphs [73]. The IDOM heuristic iteratively selects a single Steiner point that minimizes the cost of the spanning arborescence over all the sinks and Steiner points selected thus far. The reason that we iterate a spanning arborescence construction to produce a Steiner arborescence tree is that the former is easy to compute,∗ while the latter is NP-complete. The IDOM heuristic thus repeatedly (and greedily) finds Steiner candidates that reduce the overall spanning arborescence cost, and includes them into the growing set of Steiner nodes (Figure 25.10). To achieve an improved runtime for the IDOM approach, Alexander and Robins [73] defined the DOM heuristic, which is a restricted version of the PFA heuristic (Figure 25.9), except where MaxDom(p, q) is selected only from N instead of allowed to be an arbitrary node in V . This substantially speeds up the search for MaxDom(p, q) at each iteration, because N is typically much smaller than V . The DOM subroutine constructs an arborescence by using a shortest path to connect each sink in N to the closest sink/source in N that it dominates, and then computes a shortest paths tree over the graph formed by the union of these paths. Given a set of Steiner candidate node S ⊆ V − N, the cost savings of S with respect to DOM is defined as DOM(G, N, S) = cost[DOM(G, N)] − cost[DOM(G, N ∪ S)]. The IDOM approach starts with an initially empty set of Steiner candidates S = ∅. It then finds a node t ∈ V − N that maximizes DOM(G, N, S ∪ {t}) > 0, and repeats this procedure with S ← S ∪ {t}. The wirelength required by DOM to span N ∪ S will decrease with each added node t, and the overall construction terminates when there is no t ∈ V − (N ∪ S) such that DOM(G, N, S ∪ {t}) > 0. The final overall solution is DOM(G, N ∪ S). This method is described in Figure 25.11, and a sample execution is given in Figure 25.12. ∗ Recall that a node p dominates a node s if there exists a shortest path from the root to p passing through s. An optimal spanning arborescences can be computed efficiently by using a shortest path to connect each sink to the closest sink/source that it dominates, and then computing Dijkstra’s [57] shortest paths tree over the graph formed by the union of these paths. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C025 518 Finals Page 518 29-9-2008 #11 Handbook of Algorithms for Physical Design Automation (a) KMB (cost = 16, maxpath = 16) (b) IGMST (cost = 14, maxpath = 12) (c) DJKA (cost = 19, maxpath = 8) (d) IDOM (cost = 14, maxpath = 8) FIGURE 25.10 Four routing solutions for the same four-pin net (the signal source is the gray-shaded square and the solid squares are sinks): (a) the solution produced by the KMB graph Steiner heuristic of Ref. [74]; (b) the optimal Steiner tree, which is also the solution produced by the graph I1S algorithm of Refs. [16,62]; (c) Dijkstra’s shortest paths tree of Ref. [57]; and (d) the optimal Steiner arborescence, which is also the solution produced by the IDOM algorithm of Ref. [73]. Note that the IDOM solution in (d) is optimal in terms of both total wirelength as well as maximum pathlength (although this double-optimal outcome is unusual). The IDOM approach is a general template for producing arborescences for designated subgraphs (i.e., nets) in arbitrary weighted graphs (i.e., underlying routing grids) [73]. Moreover, the IDOM heuristic escapes the known twice-optimal worst-case examples of previous arborescence heuristics, both in the rectilinear plane as well as in arbitrary weighted graphs.∗ The IDOM approach outperforms the previous heuristics on empirical benchmarks [73], including in field-programmable gate ∗ There exist very rare worst-case graphs that force IDOM to produce a tree with cost logarithmic factor times optimal, matching the best-known nonapproximability results for the GSA problem [73]. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C025 Finals Page 519 29-9-2008 #12 519 Timing-Driven Interconnect Synthesis Iterated dominance (IDOM) algorithm Input: A weighted graph G = (V, E ) , a net N ⊆ V with n0 ∈ N Output: A low-cost arborescence T = (V , E ) spanning N , where N ⊆ V ⊆ V and E ⊆ E S= ∅ Do Forever T = {t ∈ V −N |DOM(G, N, S ∪ {t}) > 0} If T = ∅ Then Return DOM(G, N ∪ S ) Find t ∈ T with maximum DOM(G, N, S ∪ {t}) S = S ∪ {t} FIGURE 25.11 IDOM algorithm for producing arborescences in arbitrary weighted graphs. (From Alexander, M. J. and Robins, G., IEEE Trans. Comput. Aided Des., 15, 1505, 1996.) array (FPGA) routing, which is inherently a graph-based regime. Subsequent graph arborescence algorithms, including fast polynomial-time heuristics as well as exponential-time optimal algorithms were introduced in Ref. [75]. B 2 S1 1 1 S2 1 A 1 B S3 1 1 1 1 2 2 C 3 C 3 2 2 2 3 1 S4 D 3 A (a) D (b) S2 B C 3 3 2 B 2 3 2 A D 1 S3 C D A 1 2 S3 (c) S2 A 3 S1 B C S4 S3 (d) D (e) FIGURE 25.12 Execution example for the IDOM algorithm: (a) GSA problem instance with source node A (gray), sink nodes {B, C, D} (solid), and graph edge weights shown; (b) initial DOM solution over the contracted pathlengths distance graph (over the net N = {A, B, C, D}) having cost = 8; (c) Steiner candidate S3 produces a savings of DOM = 2, which reduces the overall tree cost from 8 to 6; thus S3 is retained as a Steiner point; (d) Steiner candidate S2 is the final Steiner point with positive DOM, and further reduces the solution cost from 6 to 5; and (e) the final IDOM solution (having cost = 5), with paths reexpanded relative to the original input graph. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C025 520 Finals Page 520 29-9-2008 #13 Handbook of Algorithms for Physical Design Automation 25.4 ELMORE DELAY-BASED ROUTING CONSTRUCTIONS Objectives such as minimum tree cost, bounded radius, cost-radius trade-offs, and even arborescences were all motivated by analyses of the Elmore delay approximation [36–39]. However, these objectives are merely abstractions that do not directly optimize delay. This section describes approaches that optimize Elmore delay directly while synthesizing a routing tree. The earliest Elmore-based routing approach is the Elmore routing tree (ERT) spanning construction of Boese et al. [16,47,76] (Figure 25.13). Similar to Prim’s MST algorithm [58], the ERT heuristic starts with a tree T = (V , E) initially containing only the source s0 , and then repeatedly finds a terminal si ∈ V and a sink sj ∈ S − V so that adding edge (si , sj ) to T minimizes the maximum Elmore delay to any sink in the growing tree. The greedy approach implicit in the ERT algorithm easily generalizes to any delay model by using the corresponding delay estimator in the inner loop of Figure 25.13. For example, Ref. [77] proposed the use of a two-pole simulator within a similar greedy construction, and Ref. [78] used this strategy for multi-chip module (MCM) routing under a second-order delay model. The ERT algorithm template can produce a timing-driven Steiner Elmore routing tree (SERT) when new sinks are allowed to connect anywhere along an edge in the growing tree, inducing a Steiner node at that connection point [12]. Following the ERT approach, the SERT variant greedily minimizes the maximum source-to-sink Elmore delay at each tree-growing step. To allow additional optimization leeway, embeddings of L-shaped edges can remain indeterminate (within their bounding boxes) for as long as possible during the execution. The SERT variant produces a Steiner topology with low source-to-sink Elmore delays. Figure 25.14 depicts the execution of the SERT heuristic on a sample eight-sink net. In performance-driven layout, timing-critical paths are determined using timing analysis, and then cells along these paths are placed closer together [27–32]. Timing analysis thus iteratively drives changes within the placement as well as global routing phases. To avoid the “placement-routing mismatch” where inherently net-dependent methods fail to exploit the critical-path information available during iterative performance-driven layout, Boese et al. [47] proposed formulations that extend the basic (S)ERT scheme to accommodate critical sinks. They proved the NP-completeness of the critical-sink routing tree problem (CSRT) [46], and provided efficient heuristics that combine Steiner construction, delay estimation, and global slack removal [47]. To address the CSRT formulation, Boese et al. generalized their SERT method to produce a Steiner Elmore Routing Tree with identified critical sink (SERT-C) [47]. The SERT-C heuristic begins with a tree containing a direct connection (s0 , sc ) between the source and the specified critical sink, and then grows the routing tree around it while minimizing the Elmore delay (or an alternate delay model) from the source to the critical sink (Figure 25.15). Figure 25.16 illustrates the Elmore routing tree (ERT) algorithm Input: Signal net S with source s0 ∈ S Output: Routing tree T over S 1. T = (V, E ) = ({s0 },∅) 2. While |V | < |S | do 3. Find si ∈ V and sj ∈ S −V that minimize the maximum Elmore delay from s0 to any sink in the tree (V ∪ {sj }, E ∪ {(si ,sj )}) 4. V = V ∪ {sj } 5. E = E ∪ {(si , sj )} 6. Output resulting spanning tree T = (V, E ) FIGURE 25.13 ERT algorithm directly uses the Elmore delay formula in a greedy routing tree construction. (From Boese, K. D., Kahng, A. B., and Robins, G., Proc. ACM/IEEE Design Automation Conference, Dallas, TX, 1993. With permission.) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C025 Finals Page 521 29-9-2008 #14 521 Timing-Driven Interconnect Synthesis 6 7 2 5 5 s0 4 6 7 3 2 1 1 8 8 (a) (b) 6 7 5 6 7 2 5 s0 4 2 3 s0 4 1 3 1 8 8 (c) (d) 6 7 5 4 6 7 2 5 s0 3 4 1 2 s0 3 1 8 (e) 3 s0 4 8 (f) FIGURE 25.14 Execution of the SERT Steiner tree construction for an eight-sink net. The source terminal is labeled 1, and the remaining sinks are numbered in the order of their distance from the source. (From Boes, K. D., Kahng, A. B., McCoy, B. A., and Robins, G., IEEE Transactions Computer-Aided Design, 14, 1417, 1995. With permission.) execution of SERT-C for various choices of the critical sink (using the same eight-sink signal net as in Figure 25.14). The SERT-C algorithm can be implemented to run within time O(n2 log n) for n-pin nets. Similar to the ERT and SERT approaches, SERT-C’s direct optimization of the Elmore delay allows considerable flexibility with respect to the underlying technology parameters, delay model, and specific input instance. The methods described above easily extend to higher dimensions and alternate metrics and geometries, including to non-Manhattan interconnect architectures such as preferred-direction routing and λ-geometries [49–56]. The Elmore-based routing tree construction methods of [12] influenced followup works on performance-driven routing trees, addressing additional issues such as buffer insertion, wirelength estimation, alternative delay models, timing constraints, and antenna effects [79–85].

Handbook of algorithms for physical design automation part 54

Nội dung