An Efficient FPGA Technology Mapping Tightly Coupled with Logic Minimization

摘要

The FPGA logic synthesis consists of logic minimization step and technology mapping step. These two steps are usually performed separately to reduce the complexity of the problem. Conventional logic minimization methods try to minimize the number of literals of a given Boolean network, while FPGA technology mapping techniques attempt to minimize the number of basic blocks. However, minimizing the number of literals, which is target architecture-independent feature, does not always lead to minimization of basic block count, which is a FPGA architecture specific feature. Therefore, most of the existing technology mapping systems take into account reorganization of its input circuits to get better mapping results. Such a loosely coupled logic synthesis paradigm may cause difficulties in finding the optimal solution. In this paper, we propose a new logic synthesis approach where logic minimization and technology mapping steps are performed tightly coupled. Our system takes into account FPGA specific features in logic minimization step and thus our technology mapping step does not need to resynthe-size the Boolean network. We formulate the technology mapping problem as a graph covering problem. Such formulation provides more global view to optimality and supports versatile cost functions. In addition, a fast and exact library management technique is devised for efficient FPGA cell matching which is one of the most frequently used operations in the FPGA logic synthesis. To demonstrate the efficiency of our approach, we applied our system to MCNC benchmarks and compared the results with those of the existing systems. The experimental results show that our approach is better than any of the existing systems in terms of area and delay.