Multi-level logic synthesis based on function decomposition.

摘要

With the growing complexity of VLSI circuits, automatic synthesis of digital circuits has gained increasing importance. The synthesis process transforms an abstract representation of a circuit into an implementation in a target technology optimizing some objective function. One of the key steps in this process is logic synthesis, which produces an optimal gate level design from a register-transfer level description.; In this thesis, we describe a multi-level logic synthesis approach based on function decomposition. In particular, we present Boolean methods for extracting common subfunctions from multiple-output Boolean functions under different objectives including area, delay, energy, and energy-delay product. The extraction problem is cast as an encoding problem and a number of encoding methods are proposed. These methods include column encoding, shared subfunction encoding, and a graph-based approach for extracting logic with a large number of supporting variables. We use ordered binary decision diagrams to represent Boolean functions so that this approach can be implemented more efficiently.; Application of these methods to the synthesis of look-up table (LUT)-based field programmable gate arrays (FPGAs) is presented next. In many instances, we had to adapt the proposed extraction techniques to the FPGA architecture. For example, we used a two-layer decomposition technique to map to Xilinx XC4000 device and used variable input-size decomposition to map to Xilinx XC5000 device. These techniques produce results which are much better than state-of-the-art techniques in terms of area, delay, and power.