Evolutionary Algorithms in Decomposition-Based Logic Synthesis

Functional decomposition is a logic synthesis method that has recently gained much recognition. The main reason is the evolution of field programmable gate-arrays (FPGAs) as a new technology for digital system implementation. Architecture of FPGA is based on the lookup table (LUT) as basic building block. An n-input LUT is capable of implementing any Boolean function of up to n variables. Thus, logic synthesis for LUT-based FPGAs must transform a logic network into network that consists of nodes with up to n inputs only. Each node of such network can be then implemented by a single LUT. For this reason, for the case of implementation targeting FPGA structure, decomposition is a very efficient method. Modern FPGA devices have very complex structure. Today's FPGAs are entire programmable systems on a chip (SoC) which are able to cover an extremely wide range of applications. The Altera Stratix III and Xilinx Virtex-5 families of devices, both using a 65 nm manufacture process, can be used as examples of contemporary FPGAs. The basic architecture of FPGAs has not changed dramatically since their introduction in the 1980s. Early FPGAs used a logic cell consisting of a 4-input lookup table and register. Present devices employ larger numbers of inputs (6-input for Virtex-5 and 7-input for Stratix III) and have other associated circuitry. Another enhancement extensively used in modern FPGAs are specialized embedded blocks, serving to improve delay, power and area if utilized by the application, but waste area and power if unused. Early embedded blocks included fast carry chains, memories, phase locked loops, delay locked loops, boundary scan testing and multipliers. More recently, multipliers have been replaced by digital signal processing (DSP) blocks which add support for logical operations, shifting, addition, multiply-add, complex multiplication etc. Some architectures even contain hardware CPU cores. This greatly extends the space of possible solution during the process of mapping the design into FPGA structure with such embedded blocks. Unfortunately such heterogeneous structure of available logic resources greatly increases the complexity of mapping algorithms. The existing CAD tools are not well suited to utilize all possibilities that such modern programmable structures offer due to the lack of appropriate logic synthesis methods. Functional decomposition is perceived as one of the best logic synthesis methods targeted FPGAs. It relies on breaking down a complex system into a network of smaller and relatively independent co-operating subsystems, in such a way that the original system’s behavior is preserved. A system is decomposed into a set of smaller subsystems, such that each of them is easier to analyze, understand and synthesize. Decomposition allows