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.