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)