FPGA technology mapping: a study of optimality

This paper attempts to quantify the optimality of FPGA technology mapping algorithms. The authors developed an algorithm, based on Boolean satisfiability (SAT), that is able to map a small subcircuit into the smallest possible number of lookup tables (LUTs) needed to realize its functionality. This technique was applied iteratively to small portions of circuits that have already been technology mapped by the best available mapping algorithms for FPGAs. In many cases, the optimal mapping of the subcircuit uses fewer LUTs than is obtained by the technology mapping algorithm. It is shown that for some circuits the total area improvement could be up to 67%.