2. Problem Formulation

An FPGA architecture consists of a set of user-configurable logic ``blocks'', and a set of programmable interconnection resources used for routing [3,16] (Figure 1). Each logic block implements a portion of the design logic, and the routing resources are used to interconnect the logic blocks. This paper focuses on the routing phase of FPGA design; thus, we assume that technology mapping, partitioning, and placement have already been performed.

Previous work on FPGA routing concentrated on solution feasibility and resource-usage minimization. For example, the CGE [3] and SEGA [13] routers handle nets based on demand and assign critical nets a higher routing priority. Other papers studied FPGA routing with switch blocks of limited flexibility [18], explored modified architectures [15], or computed lower bounds on routing rather than providing actual routes [4]. Recently [1,2]. developed a routing framework where mutually competing objectives (e.g., congestion, wirelength, jog minimization) are simultaneously optimized. However, these works do not directly minimize source-sink signal propagation delays, and while many approaches implicitly equate delay minimization with wirelength optimization, these two goals are not synonymous [11].

In order to apply graph-based techniques, we model the FPGA as a graph, where the overall graph topology mirrors the complete FPGA architecture; paths in this graph correspond to feasible routes on the FPGA, and vice versa (Figure 2). Let G=(V,E) denote such a graph, where each graph edge e_ij in E has a weight w_ij that corresponds to the wirelength of the associated FPGA routing wire segment (weights may also reflect congestion, jog penalties, etc.). A net N = { n_0, n_1, ..., n_k } subset of V is a set of pins that are to be electrically connected, where n_0 is the signal source and the remaining pins are sinks. A routing solution for a net is a tree T subset of G which spans N, and the cost of a tree T, denoted cost(T), is the sum of its edge weights.

Prior to routing, nets may be classified as either critical or non-critical based on timing information that becomes available during iterative layout. When routing non-critical nets, we seek not to optimize delay but rather to maximize the likelihood of completely routing all nets on the given FPGA; this resource-usage minimization objective motivates the following graph Steiner minimal tree formulation:

Graph Steiner Minimal Tree (GSMT) Problem: Given weighted graph G=(V,E), and net N subset of V, find a minimum-cost spanning tree T=(V',E') with N subset of V' subset of V and E' subset of E.

Any node in V-N may be used as a potential Steiner point in order to optimize the overall wirelength. The GSMT problem is known to be NP-complete and arises in numerous applications [9]. The high-performance requirement of critical nets dictates a shortest source-sink paths objective, with wirelength minimization being a secondary optimization criteria. For a weighted graph G=(V,E) and two nodes u,v in V, let minpath_G(u,v) denote the cost of a shortest path between u and v in G. We thus formulate the graph Steiner arborescence problem as follows:

Graph Steiner Arborescence (GSA) Problem: Given weighted graph G=(V,E), and net N subset of V to be routed in G, construct a least-cost spanning tree T=(V',E') with N subset of V' subset of V and E' subset of E such that minpath_T (n_0 , n_i) = minpath_G (n_0 , n_i) for all n_i in N.

Since the GSA problem is NP-complete [7], and FPGA routing graphs are generally large, we must seek efficient heuristics for this problem. On the other hand, we can prove the following non-approximability result:

Theorem 2.1 The GSA problem can not be approximated in polynomial time to within a performance bound of better than O(log N) times optimal (unless deterministic polylog space coincides with non-deterministic polylog space, which is a longstanding open problem).

Figure 3 illustrates routing solutions produced by the algorithms discussed below (the source is the lightly-shaded square, and the dark squares are sinks). The two solutions at the top depict Steiner trees, while the two lower constructions are Steiner arborescences: (a) the KMB heuristic of [12], (b) our IGSMT solution (which is also the optimal Steiner tree here), (c) DJKA, a variant of Dijkstra's algorithm [6], (d) our IDOM construction (which is also the optimal arborescence here).