A Stochastic Model to Predict the Routability of Field-Programmable Gate Arrays
Abstract
Field-Programmable Gate Arrays (FPGAs) have recently emerged as an
attractive
means of implementing logic circuits as a customized VLSI chip. FPGAs
have gained
rapid commercial acceptance because their user-programmability offers
instant manufacturing
turnaround and low costs. However, FPGAs are still relatively new and
require
architectural research before the best designs can be discovered. One
area of particular
importance is the design of an FPGAs routing architecture, which
houses the user-programmable
switches and wires that are used to interconnect the FPGAs 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
already been studied
using experimental techniques in [1] [2] and [3]. This paper describes
a stochastic
model that facilitates exploration of a wide range of FPGA routing
architectures using a
theoretical approach.
In the stochastic model an FPGA is represented as an N x N array of
logic blocks, separated
by both horizontal and vertical routing channels, similar to a Xilinx
[4] [5] [6]
FPGA. Each routing channel comprises a number of tracks and each track
consists of a set
of short wire segments. Routing switches are available to connect the
pins of the logic
blocks to the wire segments, and to connect one wire segment to
another. The number of
routing switches and their distribution over the wire segments are
parameters of the stochastic
model. A circuit to be routed is represented by additional parameters
that specify
the total number of connections, and each connections length and
trajectory.
The stochastic model gives an analytic expression for the routability
of the circuit in
the FPGA, which is defined as the percentage of the circuits
connections that can be
accommodated by the FPGAs routing architecture. Practically speaking,
routability can
be viewed as the likelihood that a circuit can be successfully routed
in a given FPGA. The
routability predictions from the model are validated by comparing them
with the results of
a previously published experimental study on FPGA routability.
Reference
Stephen D. Brown, Jonathan Rose and Zvonko G. Vranesic, "A Stochastic Model to Predict the Routability of Field-Programmable Gate Arrays," IEEE Transactions on Computer Aided Design of Integrated Circuits and System, Vol 12, No. 12, Dec. 1993, pp 1827-1838.
(Download Full Paper)