LURU: global-scope FPGA technology mapping with content-addressable memories

The paper proposes a technique for area-optimized FPGA technology mapping. The LURU algorithm maps a combinational circuit to a network of K-input lookup tables (LUTs). The LURU algorithm uses content addressable memory (CAM) to enable parallel pattern matching in a Boolean network. As a result, it is possible to perform global searches quickly within an entire Boolean network, thus increasing the quality of results compared to algorithms of local scope. To utilize CAM for the LURU algorithm, a circuit is described as a set of one dimensional text strings, each of which independently represents the topology of a portion of the circuit. The LURU algorithm was tested with specially partitioned circuits from the ISCAS´85 set of combinational benchmarks. These results are compared with results obtained from the mapping algorithms FlowMap and CutMap. It is demonstrated that using LURU leads to an average of 25% area improvement over both FlowMap and CutMap.