Bit matrix compression is a highly relevant operation in computer arithmetic. Essentially being a multi-operand addition, it is the key operation behind fast multiplication and many higher-level operations such as multiply-accumulate, the computation of the dot product or the implementation of FIR filters. Compressor implementations have been constantly evolving for greater efficiency both in general and in the context of concrete applications or specific implementation technologies. This paper is building on this history and describes a generic implementation of a bit matrix compressor for Xilinx FPGAs, which does not require a generator tool. It contributes FPGA-oriented metrics for the evaluation of elementary parallel bit counters, a systematic analysis and partial decomposition of previously proposed counters and a fully implemented construction heuristic with a flexible compression target matching the device capabilities. The generic implementation is agnostic of the aspect ratio of the input matrix and can be used for multiplication the same way as it can be for single-column population count operations.
A heuristic for constructing compressors for Altera devices was proposed by Parandeh- in 2008 @cite_8 . They used a single-pass heuristic selecting the most efficient from a selection of parallel counter that would fit into the work still to do by the compression step starting from the least-significant and proceeding to the most-significant bit position. The compression goal was a matrix of, at most, three rows. This relaxed goal definition exploits the fact that ternary adders map well onto modern FPGA architectures. It also has the tremendous benefit that half adders can be avoided altogether. Half-adders only have a reshaping function and do not reduce the number of bits in the matrix. As shown in figHAmust , they must be used to reshape an almost done two-row matrix in parallel so that it can accommodate just one more carry efficiently. This pressure disappears with a goal of three rows.
@cite_8
2110452354
FPGA performance is currently lacking for arithmetic circuits. Large sums of k > 2 integer values is a computationally intensive operation in applications such as digital signal and video processing. In ASIC design, compressor trees, such as Wallace and Dadda trees, are used for parallel accumulation; however, the LUT structure and fast carry-chains employed by modern FPGAs favor trees of carry-propagate adders (CPAs), which are a poor choice for ASIC design. This paper presents the first method to successfully synthesize compressor trees on LUT-based FPGAs. In particular, we have found that generalized parallel counters (GPCs) map quite well to LUTs on FPGAs; a heuristic, presented within, constructs a compressor tree from a library of GPCs that can efficiently be implemented on the target FPGA. Compared to the ternary adder trees produced by commercial synthesis tools, our heuristic reduces the combinational delay by 27.5 , on average, within a tolerable average area increase of 5.7 .