Constructing an arborescence intuitively entails "e;folding"e; (i.e., overlapping) paths in a shortest-paths tree to yield the greatest possible wirelength savings while maintaining the shortest-paths property. For pointsets in the Manhattan plane, an effective arborescence heuristic is the construction of Rao et al. [14], which has a performance ratio of twice optimal, as well as good empirical performance (a variation of the method of [14] was given in [5]. However, these methods rely on the underlying geometry of the Manhattan metric. In order to handle FPGA routing graphs, we first define the notion of dominance in arbitrary weighted graphs as follows:
Definition 3.1 Given a weighted graph G=(V,E), and nodes {n_0, p, s} in V, we say that p dominates s if minpath_G(n_0,p) = minpath_G(n_0,s) + minpath_G(s,p).
Thus, p dominates s if a shortest path from the source n_0 to p can pass through s. Note that the shortest path between a pair of nodes in an FPGA graph is generally not unique. We define MaxDom(p,q) as a node m in V dominated by both p and q which maximizes minpath_G(n_0,m). Selecting a MaxDom as far away from the origin as possible maximizes the overlap (i.e., the wirelength savings) between the two paths.
These definitions enable our Path-Folding Arborescence (PFA) heuristic which generalizes the method of [14] to arbitrary weighted graphs. Starting with the set of nodes containing the source and all sinks, find a pair of nodes p and q such that m=MaxDom(p,q) is farthest away from the source among all such pairs; then replace p and q by m and iterate until only the source remains. The graph Steiner arborescence solution is formed by using shortest paths in G to connect each MaxDom(p,q) to both p and q (Figure 5).
Path-Folding Arborescence (PFA) Algorithm
Input: Weighted graph G=(V,E) and net N subset of V Output: A low-cost shortest-paths tree spanning N
M = N While N != {n_0} Do Find a pair {p,q} subset of N such that m = MaxDom(p,q) has maximum minpath_G(n_0,m) over all {p,q} in N N = {N - {p,q}} U {m} M = M U {m} Output the tree formed by connecting each node p in M (using a shortest path in G) to the nearest node in M that p dominates
Figure 5: Path-Folding Arborescence (PFA) heuristic.
Since there are at most O(|N|) elements in set N, the time to compute all shortest-paths trees is bounded by O(|N|*|E|), and the total number of MaxDom computations performed is at most O(|V|*|N|^2). Storing the results of the MaxDom computations in a heap allows the next MaxDom to be determined efficiently, and results in an overall time complexity for PFA of O(|N|*|E| + |V|*|N|^2 * log|V|).
Our empirical results indicate that the PFA method is effective in producing shortest-paths trees at a relatively modest wirelength penalty. However, in considering the worst-case behavior of PFA, we found examples of graphs where PFA can perform as badly as O( N ) times optimal. Thus, the next section presents another heuristic for the graph arborescence problem which escapes such worst-case examples.