Abstract
The narrowing opportunity window and the dramatically increasing development costs
of deep sub-micron application specific integrated circuit (ASIC) designs have presented
new challenges to the development process. The cost of ASICs development and fabrication
is presently so high that more and more companies are seeking alternative implementation
platforms.
Today, programmable logic devices (PLDs), in particular the family known as lookup-
table (LUT) based field programmable gate arrays (FPGAs), provide this alternative
platform. Being introduced in 1984, LUT based FPGAs quickly evolved into sophisticated
re-configurable system-on-a-chip (SoC) platforms that contained huge arrays of
configurable logic blocks and interconnections for random logic implementation, efficient
memory blocks, and embedded processor or intellectual property (IP) cores. FPGAs and
FPGA-based re-configurable SoC platforms are from-the-shelf components produced in
huge quantities. This not only reduces their cost, but also increases their quality.
On the other hand, the complexity of the contemporary designs requires new efficient
and effective synthesis methods and tools for taking the designs from register transfer
level (RTL) to silicon.
The research reported in this thesis is aimed at development of an effective and efficient
method and electronic design automation (EDA) tool for the circuit synthesis targeting
LUT based FPGAs and FPGA-based SoC platforms. The method is assumed to be based
on the information-driven approach to circuit synthesis, general functional decomposition
and information relationships measures. Despite the fact that circuit synthesis methods
for FPGAs have been a standard research topic during the last two decades, the topic as
it is addressed here remains crucial for at least two key reasons.
First, earlier approaches tried to incorporate traditional synthesis methods based
on some minimally functionally complete systems of logic gates implementing only few
very specific functions (e.g., AND+OR+NOT). Such approaches require a post synthesis
technology mapping for other implementation structures. If the actual synthesis target
strongly differs from a given minimal system, as in FPGAs case, any technology mapping
cannot guarantee a good result because the initial synthesis is performed without close
relation to the actual target.
Second, the new methods, based on functional decomposition, are computationally
complex. Because of this computational complexity, it was important to develop adequate
approaches and heuristics to make the synthesis methods effective and efficient. To make
the heuristics robust, an adequate design decision-making apparatus that controls the
decomposition process is vital.
In the late nineties, a very promising design decision-making apparatus was proposed
by J´o´zwiak [J´o´z97a].The apparatus was based on information flow modeling in discrete
finite functions and relations and analysis of information importance in the modeled flows
and information relationships between the flows. The early applications of that apparatus
confirmed its potential as a successful measurement apparatus for controlling the heuristic
optimization algorithms in the logic synthesis area. The research reported in this thesis
is a continuation of that research.
The primary goal of the proposed circuit synthesis process is to find the best trade-off
between the circuit area and speed represented by the number of look-up-tables and the
number of levels in the resulting network that implements a given multiple-output incompletely
specified Boolean function. A secondary goal is minimization of the number and
length of interconnections. The method developed in this work is unique in many ways. It
uses the (enhanced) compositional bottom-up approach to the functional decomposition.
Other methods use unordered or top-down reduction approach. In the proposed method,
all crucial decisions are made with the use of the theory of information relationships and
information relationship measures [J´o´z97a] during the decomposition process. The most
important of these are: the predecessor sub-function input support construction and selection,
and the binary encoding of the multiple-valued sub-functions. Other functional
decomposition methods mainly use some structural properties of the resulting networks
for decision-making. Sometimes, even the most crucial decisions are made randomly.
A novel, exact, and heuristic methods for symmetry detection in the incompletely
specified Boolean functions were proposed and implemented in the scope of the presented
research. The proposed symmetry detection method is based on information modeling
using set-systems. The adequate usage of symmetries of Boolean functions results in a
significant simplification of the resulting network, but also expedites the decomposition
process.
The circuit synthesis method developed in the scope of this research was implemented
in the form of an electronic design automation (EDA) software tool called IRMA2FPGAS
(Information Relationship Measures Applied to FPGA Synthesis). Using this tool and
several benchmarks, including MCNC benchmarks used in academia, an extensive experimental
study was performed. The experimental results prove the capability of the
information-driven functional decomposition approach and the proposed method to robustly
construct high quality solutions for the FPGA-related circuit synthesis problems.
Our IRMA2FPGAS tool significantly outperformed all other tools used in the experiments
for both the circuit speed and area.
Original language | English |
---|---|
Qualification | Doctor of Philosophy |
Awarding Institution |
|
Supervisors/Advisors |
|
Award date | 16 Dec 2004 |
Place of Publication | Eindhoven |
Publisher | |
Print ISBNs | 90-386-1673-2 |
DOIs | |
Publication status | Published - 2004 |