CAD for FPGAs
FPGAs present new problems in Computer-Aided Design that sometimes differ
from those in other implementation media such as Mask-Programmed Gate Arrays,
Standard Cells and full-custom design. Some of the CAD topics that our
research has addressed are:
Synthesis of interconnect for FPGAs. Given an abstract specification of the logical connectivity, synchronization constraints, a sense of the throughput-based importance of a given connection, determine the connectivity and pipelining of automatically generated interconnect. This is implemented in the Genie system synthesis
system, whic also instantiates the functional units of a system along with the interconnect.
The Genie software can be downloaded here, and
you can read several publications on its ability to synthesize both fine-grained and coarse-grained
- Placement and Routing for FPGAs - Placement is the determination of where on the FPGA each logic block or element is placed.
Routing is the determination of the paths that connect the logic - setting
the programmable switches of an FPGA correctly, so that the wires
are hooked up correctly.
VPR is a new placement and routing tool that has been developed at
the University of Toronto, explicitly for the purpose of exploring
FPGA architectures. You can download the latest release of VPR,
The latest version permits monolithic heterogeneous logic blocks, direct drive
routing, and a whole suite of electrically optimized architecture files.
It is described in various publications, including
A detailed description of original algorithms and it performance can
be found in
and the book
Architecture and CAD for Deep-Submicron FPGAs.
- Front end elaboration and synthesis from a hardware
description language (Verilog) for FPGAs. The main goal is to make it
easier to directly deal with the hard, heterogenous structures
now found in FPGAs, and to explore the architecture of such blocks.
See Peter Jamieson's paper on Odin
and the related software here.
A New Version, ODIN, is now more directly linked into the latest versions of VPR,
and can be found here.
- Although common placement algorithms work fine, it may
be necessary for the placement algorithm to understand some specific things
about the routing architecture. For example, when the routing channels
have differeinig thickness across the FPGA, the placement algorithm should
know about it and respond to it
- Automated Routing of FPGAs - the determination of the programmable
paths between the logic. Since the connections can only be made where pre-fabricated
switches exist, a router that understands this is necessary [Brown92]
. Also, since these switches incur significant delay, a timing-driven router
is often necessary to meet performance constraints.
- Technology Mapping for FPGAs - the packing of the user's logic into
the logic block function of the FPGA. For example, some of the first work
on this subject for lookup table -based FPGAs can be found in [Fran90]
and [Fran91a] and
We have also looked at the issue of mapping into an FPGA with
two different kinds of logic block; in particular two different
sizes of lookup table
- Assisting Manual Design of FPGAs with full information - All
CAD in IC design and design of FPGAs relies on incomplete informatin
when making optimization decisions upstream of routing and final timing
analysis. In this work, we create a design framework in which
the design has complete knowledge of the timing and routing success or
failure of his design. This is practical for small circuits
under small modifications made in the manual context. We were able
to show that packing and placement modifications of small
(less than 250 LUTs) Xilinx Virtex-E circuits could achieve an
average speed up of about 13%. See
[Chow02]. We have
enhanced this work by including logic synthesis modifications
to the circuit -
to Jonathan Rose's Page .Computer