Technology mapping for Field Programmable Gate Arrays using Content-Addressable Memory (CAM)

The growing complexity of Field Programmable Gate Arrays (FPGA’s) is leading to architectures with high input cardinality look-up tables (LUT’s). This paper describes a methodology for area-optimal combinational technology mapping, specifically designed for such FPGA architectures. This methodology, called LURU, leverages the parallel search capabilities of Content-Addressable Memories (CAM’s) to outperform traditional mapping algorithms in both execution time and quality of results. The LURU algorithm is fundamentally different from other techniques for technology mapping in that LURU uses textual representations of circuit topology in order to efficiently store and search for circuit patterns in a CAM. A circuit is mapped to the target LUT technology using exact, inexact, or hybrid matching techniques. Common subcircuit expressions (CSE’s) are also identified and used for architectural optimization—a small set of CSE’s is shown to effectively cover an average of 96% of the test circuits. LURU was tested with the ISCAS ’85 suite of combinational benchmark circuits and compared with the mapping algorithms FlowMap and CutMap. The area requirement of LURU’s mapping is, on average, 20% less than FlowMap or CutMap. The asymptotic runtime complexity of LURU is shown to be better than that of both FlowMap and CutMap.