FPGA technology mapping: a study of optimality


This paper attempts to quantify the optimality of FPGA technology mapping algorithms. We develop 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. We iteratively apply this technique 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. We show that for some circuits the total area improvement can be up to 67%.


A. C. Ling, D. P. Singh, Stephen D. Brown, "FPGA technology mapping: a study of optimality", nominated for best paper in Proceedings of the 42nd Design Automation Conference (DAC05), pp 427-432, Anaheim, CA, June 2005.

(Download Full Paper)