RoCoCo: row and column compression for high-performance multiplication on FPGAs

Abstract

Multiplication is, in no doubt, one of the top few frequently used operations in hardware and software. In high-performance hardware design, after high-level optimizations are exhausted, component level optimizations are employed such as building fast multipliers. Most fast multiplier architectures use some form of a Carry Save Adder (CSA) Tree, which is also called Column Compression (CC). We propose a new CC method called RoCoCo (Row and Column Compression), which also compresses the tree along rows so that the final adder is small and fast. Although CC results in faster multipliers in ASIC implementations, it is an assumption by designers that they are not the wisest choice on FPGAs. On the contrary, we were able to show through Xilinx synthesis results that RoCoCo (and sometimes Dadda CC) frequently offer faster multipliers than the built-in implementation of the multiply operation in Xilinx ISE synthesis tool.