Karatsuba with Rectangular Multipliers for FPGAs

Martin Kumm 1 Oscar Gustafsson 2 Florent de Dinechin 3 Johannes Kappauf 1 Peter Zipf 4
1 University of Kassel
2 LIU - Linköping University
3 SOCRATE - Software and Cognitive radio for telecommunications
Inria Grenoble - Rhône-Alpes, CITI - CITI Centre of Innovation in Telecommunications and Integration of services
4 MES - Microelectronic Systems Institute
Abstract : This work presents an extension of Karatsuba's method to efficiently use rectangular multipliers as a base for larger multipliers. The rectangular multipliers that motivate this work are the embedded 18×25-bit signed multipliers found in the DSP blocks of recent Xilinx FPGAs: The traditional Karatsuba approach must under-use them as square 18×18 ones. This work shows that rectangular multipliers can be efficiently exploited in a modified Karatsuba method if their input word sizes have a large greatest common divider. In the Xilinx FPGA case, this can be obtained by using the embedded multipliers as 16×24 unsigned and as 17×25 signed ones. The obtained architectures are implemented with due detail to architectural features such as the pre-adders and post-adders available in Xilinx DSP blocks. They are synthesized and compared with traditional Karatsuba, but also with (non-Karatsuba) state-of-the-art tiling techniques that make use of the full rectangular multipliers. The proposed technique improves resource consumption and performance for multipliers of numbers larger than 64 bits.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download
https://hal.inria.fr/hal-01773447
Contributor : Florent de Dinechin <>
Submitted on : Saturday, April 21, 2018 - 11:58:35 PM
Last modification on : Tuesday, October 30, 2018 - 9:55:51 AM
Long-term archiving on : Tuesday, September 18, 2018 - 10:26:37 PM

File

2018-Arith-rectangularKaratsub...
Files produced by the author(s)

Identifiers

Collections

INSA-LYON | INRIA | CITI | INSA-GROUPE

Citation

Martin Kumm, Oscar Gustafsson, Florent de Dinechin, Johannes Kappauf, Peter Zipf. Karatsuba with Rectangular Multipliers for FPGAs. ARITH 2018 - 25th IEEE International Symposium on Computer Arithmetic, Jun 2018, Amherst, United States. pp.13-20, ⟨10.1109/ARITH.2018.8464809⟩. ⟨hal-01773447⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

425

Files downloads

470

Contact


archive-ouverte@inria.fr