Routing architectures and algorithms for field-programmable gate arrays

A Field-Programmable Gate Array (FPGA) is a (re)programmable logic device that implements multi-level logic. FPGA's can be configured by designers at their sites, eliminating the time-consuming fabrication step, and thus result in low prototyping cost and short manufacturing time. These advantages have made FPGA's very popular since their first introduction in mid-1980s. However, as a relatively new technology, FPGA architectures are constantly evolving, and current approaches for designing the traditional Application-Specific Integrated Circuits (ASIC's) do not apply to FPGA's well. Thus it is desirable to consider architectures for FPGA design and develop FPGA-specific computer-aided-design tools.; Logic circuits are implemented in an FPGA by partitioning logic into logic modules and then interconnecting the modules. FPGA interconnection resources consist of pre-fabricated wire segments and programmable switches. Routing in FPGA is performed by programming the switches to connect the wire segments. The programmable switches usually have high resistance and capacitance, and consume a large amount of area. Due to the area and delay constraint, the number of switches that can be placed in a switch module is usually limited, implying limited routability. It is thus of importance to design switch modules that maximize routability under the area and delay constraints.; This thesis focuses on two closely related issues for FPGA's: routing and its architectures. (1) Routing architecture: There are two types of switch modules: switch blocks and switch matrices. We present techniques for designing and analyzing a class of universal switch blocks which accommodate all types of nets routed through them, and show theoretically and experimentally that they outperform the switch blocks currently available. For switch matrices, we show the nonexistence of their universality, analyze the routability of commercially available architectures, and present effective approaches for designing good switch matrices. (2) Routing: We show a class of network-flow-based approximation algorithms for a switch-module routing problem and prove that they have guaranteed constant performance bounds. Solutions to this switch-module routing problem pave the way for developing a novel congestion metric for FPGA global routing. Experimental results show that the new metric significantly improves a router's area performance. Area and speed are two most important concerns in router design. To consider area and speed simultaneously, we study a model of timing-driven routing, arising from the special properties of FPGA routing architectures. We explore the complexity of this problem and present efficient and effective approximation algorithms for the problem.