An efficient algorithm for finding the minimal-area FPGA technology mapping
Chi‐Chou Kao, Yen‐Tai Lai · ACM Transactions on Design Automation of Electronic Systems · 2005
Minimum area is one of the important objectives in technology mapping for lookup table-based field-progrmmable gate arrays (FPGAs). Although there is an algorithm that can find an optimal solution in polynomial time for the minimal-area FPGA technology mapping problem without gate duplication, its time complexity can grow exponentially with the number of inputs of the lookup-tables. This article proposes an algorithm with approximate to the area-optimal solution and lower time complexity. The time complexity of this algorithm is proven theoretically to be bounded by O ( n 3 ), where n is the total number of gates in the given circuit. It is shown that except for some cases the proposed algorithm can find an optimal solution of a given problem. We have combined the proposed algorithm with the existing postprocessing procedures which are used to find the gates that can be duplicated on a set of benchmark examples. The experimental results demonstrate the effectiveness of our algorithm.