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).