Effective and efficient circuit synthesis for LUT FPGAs : based on functional decomposition and information relationship measures

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