Field-Programmable Gate Arrays (FPGAs) are a new type of user-programmable integrated circuits that supply designers with inexpensive, fast access to customized VLSI. A key component in the design of an FPGA is its routing architecture, which comprises the wiring segments and routing switches that interconnect the FPGA’s logic cells. Each of the user-programmable switches in an FPGA consumes significant chip area and has appreciable capacitance and resistance, leading to a tradeoff in the design of a good routing architecture. Providing a large number of switches will yield a flexible architecture in which the logic cells are easily interconnected, but too many switches wastes area and degrades speed performance. On the other hand, fewer switches allows better speed performance and uses less area, but if there are too few switches then it may not be possible to implement the desired circuits. This thesis studies FPGA routing architectures with regard to this tradeoff, yielding three main contributions.

A novel detailed routing algorithm that can account for the limited connectivity in FPGA routing architectures has been developed. It can be used over a wide range of FPGA routing architectures, and represents the first published algorithm that approaches detailed routing in FPGAs in a general way. The algorithm addresses the unique issues in FPGA routing by accounting for the side-effects that the routing of one connection may have on others, allowing it to resolve contention for the routing resources. It is shown that the router yields excellent results for a set of relatively large industrial circuits implemented as FPGAs. The router is the principal tool that is used for the experimental study of FPGA routing architectures done in this thesis.

Experiments have been conducted to study the effects of the flexibility of FPGA routing architectures on the routability, which is the percentage of connections that can be successfully completed, of circuits. Flexibility is a measure of the total number of routing switches and wiring segments in a routing architectures. The experiments show that a high flexibility is required in the connection blocks that join the logic cells to the routing channels, but a relatively low flexibility is sufficient in the switch blocks at the intersections of horizontal and vertical channels. It is also shown that a surprisingly small number of tracks per routing channel is sufficient to allow circuits to be configured, even when the flexibility is low.

Finally, a stochastic model has been developed that allows the study of FPGA routing architectures using a theoretical approach. In the model, both an FPGA and a circuit to be configured are represented as simple parameters, and probability theory is used to predict the effect of routing the circuit in the FPGA. The model corroborates the experimental results with the same circuits. It provides the foundation of a theoretical approach that can be used in future studies of FPGA routing architectures, without time-consuming experiments.