Area Optimized Synthesis of Compressor Trees on Xilinx FPGAs Using Generalized Parallel Counters

Early compressor trees based on carry-save adders and single-column parallel counters show good performance in ASIC design, but do not adapt well to modern field-programmable gate arrays (FPGAs). Recently, compressor trees built from generalized parallel counters (GPCs) were synthesized on FPGAs to address this issue. Despite the improved timing performance of GPC-based compressor trees, area reduction is not as significant as delay, and can be further optimized. In this paper, we propose improved GPC mappings as well as new approaches for GPC cascading and binding for Xilinx FPGAs. With these improvements, we develop an integer linear programming (ILP) method for FPGA synthesis of GPC-based compressor trees that supports cascading and binding between GPCs. Experimental results show that the single-cycle compressor trees produced by the proposed ILP can reduce the average area by 42.40% compared with those generated by existing heuristic method, but are 13.16% slower; the pipelined compressor trees produced by the proposed ILP can reduce the average area by 33.43% at the cost of an average 14.35% decrease in maximum clock frequency compared with those obtained by existing heuristic method.