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.