next up previous
Next: Mis-pga Up: CIS4930 Final Report: Survey Previous: CIS4930 Final Report: Survey

Introduction

Due to its high density and programmability, FPGA's are becoming popular for those design logic circuits for relatively small quantity. Especially SRAM-based FPGA's have a great advantages over other types of FPGA's for quick proto-typing; they can be re-programmed at users' site in a short time period.

Implementation of a logic circuit by FPGA's take the following steps:

Design Entry
Various form of methods are provided, such as schematic capture (e. g. OrCAD, Cadence), hardware description languages (e. g. VHDL, Verilog/HDL).

Network File Extraction
The designs entered by human designers are then converted into the internal format that is easy for computer programs to handle. There are many different formats for this network file as there are many CAD systems, however they are essentially equivalent to the boolean network.

Logic Optimization
The design is then optimized by redundancy removal and subexpression elimination. Usually this step does not consider the type of elements by which the final circuit is implemented. Therefore it is called technology-independent logic optimization.

Technology Mapping
The design is re-constructed in this step so that it can be implemented by the building blocks (Configurable Logic Block (CLB)'s in Xilinx) of the target FPGA. The circuit is optimized to reduce the number of building blocks, or the number of levels.

Placement and Routing
By the technology mapping, the design has been converted into the network of building blocks. This step physically maps the network to the instances of the building blocks, and connects them using the interconnection resources provided by the target FPGA.

Conventional methods for technology mapping use a limited set of pre-determined circuits such as a standard cell library. Each library cell is given a cost, and the conventional library-based algorithms try to minimize the cost of generated circuit which is the sum of component library cells. A Look-Up Table (LUT) that is used in Xilinx FPGA's is a universal function generator; it can generate arbitrary function for the given number of inputs. Hence to apply library-based approaches to LUT-based FPGA's, an impractically large number of library cells are required. For this reason, new algorithms for LUT-based FPGA technology mapping have been developed.

There are several criterion that characterize technology mapping algorithm:

LUT Number Minimization
Less LUT's mean a larger circuit can be implemented on a FPGA chip.
Routability
Due to limitation of wiring resource and physical topology of the design, it may not be possible to route CLB's used for implementing logic circuits.
Delay Minimization
To guarantee operation speed of the generated circuit.

The objective of this report is to survey various technology mapping algorithms developed so far. The book written by Brown et al [1] which was published in 1992, is a comprehensive and exhaustive guide to this topic. This report depends on the book (also original articles when available) for the algorithms developed before 1992. There are also newer algorithms presented after the publication of the book. From the following section, each algorithm is described. The benchmark circuits developed at Microelectronics Center of North Carolina (MCNC) was used by the developers of the algorithms in their experiments. The configuration block of Xilinx FPGA is called CLB, and it contains a LUT (two LUT's in 4000 series). In this report, LUT and CLB are used interchangeably where confusion is not expected.



next up previous
Next: Mis-pga Up: CIS4930 Final Report: Survey Previous: CIS4930 Final Report: Survey



Hitoshi Oi
All Rights Reserved