A STOCHASTIC-MODEL TO PREDICT THE ROUTABILITY OF FIELD-PROGRAMMABLE GATE ARRAYS

Field-programmable gate arrays (FPGA's) have recently emerged as an at tractive means of Implementing logic circuits as a customized VLSI chi p. FPGA's have gained rapid commercial acceptance because their user-p rogrammability offers instant manufacturing turnaround and low costs. However, FPGA's are still relatively new and require architectural res earch before the best designs can be discovered. One area of particula r importance is the design of an FPGA's routing architecture, which ho uses the user-programmable switches and wires that are used to interco nnect the FPGA's logic resources. Because the routing switches consume significant chip area and introduce propagation delays, the design of the routing architecture greatly influences both the area utilization and speed performance of an FPGA. FPGA routing architectures have alr eady been studied using experimental techniques in [1]-[3]. This paper describes a stochastic model that facilitates exploration of a wide r ange of FPGA routing architectures using a theoretical approach. In th e stochastic model an FPGA is represented as an N x N array of logic b locks separated by both horizontal and vertical routing channels, simi lar to a Xilinx [4]-[6] FPGA. A circuit to be routed is represented by additional parameters that specify the total number of connections, a nd each connection's length and trajectory. The stochastic model gives an analytic expression for the routability of the circuit in the FPGA . Practically speaking, routability can be viewed as the likelihood th at a circuit can be successfully routed in a given FPGA. The routabili ty predictions from the model are validated by comparing them with the results of a previously published experimental study on FPGA routabil ity.