Resource Optimal Design of Large Multipliers for FPGAs
Authors:
- Martin KummMKMartin Kumm
- Johannes KappaufJKJohannes Kappauf
- Matei IstoanMIMatei Istoan
- Peter ZipfPZPeter Zipf
- 1 July 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636889,p. 131-138
Abstract
This work presents a resource optimal approach for the design of large multipliers for FPGAs. These are composed of smaller multipliers which can be DSP blocks or logic-based multipliers. A previously proposed multiplier tiling methodology is used to describe feasible solutions of the problem. The problem is then formulated as an integer linear programming (ILP) problem which can be solved by standard ILP solvers. It can be used to minimize the total implementation cost or to trade the LUT cost against the DSP cost. It is demonstrated that although the problem is NP-complete, optimal solutions can be found for most practical multiplier sizes up to 64x64. Synthesis experiments on relevant multiplier sizes show slice reductions of up to 47.5% compared to state-of-the-art heuristic approaches.Keywords
This publication has 14 references indexed in Scilit:
- An Efficient Softcore Multiplier Architecture for Xilinx FPGAs2015
- Partial-product generation and addition for multiplication in FPGAs with 6-input LUTs2014
- Arithmetic core generation using bit heaps2013
- Asymmetric large size multipliers with optimised FPGA resource utilisationIET Computers & Digital Techniques, 2012
- Compressor tree synthesis on commercial high-performance FPGAsACM Transactions on Reconfigurable Technology and Systems, 2011
- Multipliers for floating-point double precision and beyond on FPGAsACM SIGARCH Computer Architecture News, 2010
- Efficient synthesis of compressor trees on FPGAs2008
- Partitioning a Square into Rectangles: NP-Completeness and Approximation AlgorithmsAlgorithmica, 2002
- Hard Tiling Problems with Simple TilesDiscrete & Computational Geometry, 2001
- Cutting and Packing Problems: A Categorized, Application-Orientated Research BibliographyJournal of the Operational Research Society, 1992