FPGA CAD Research – U of T
FPGAs and CPLDs 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:
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.
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 - [Czajkowski04].
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 from here. A detailed description of the algorithms and it performance can be found in [Betz97b] and the book Architecture and CAD for Deep-Submicron FPGAs.
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 [Betz96].
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 [Fran91b]. 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 [He94].