Optimization of Multipliers for Reconfigurable Logic

• Applicant: Professor Dr.-Ing. Martin Kumm
• Subject Area: Computer Architecture, Embedded and Massively Parallel Systems
• Term: from 2019 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 426369132

• Final Report Year: 2023

Final Report Abstract

The goal of the DFG research project was to improve circuits for the multiplication operation on reconfigurable logic with respect to resources, runtime and energy requirements. The multiplication represents a basic arithmetic operation found in almost every complex algorithm. Many algorithms are accelerated using reconfigurable logic such as Field Programmable Gate Arrays (FPGAs). Improving the multiplication operation therefore improves a wide range of applications. The design of multipliers is conventionally divided into three steps: the generation of partial products, the reduction of the partial products, and the design of the final addition. On FPGAs, completely different circuits are used in each step. However, the design steps strongly influence each other, so that even the optimal solution of each step does not necessarily result in a globally optimal solution. Therefore, the goal was to use modern optimization methods to improve the multiplication operation for FPGAs. A key project result is the combined optimization of all three design steps. Here, the optimization problem was formulated as an integer linear programming problem, which results in optimal solutions for a given set of basic operations, producing significantly better results than previous methods. It was originally expected that the combined problem could only be solved for very small problem sizes. In fact, it was shown that the method can be used for multiplications on current computers up to 32 bit, which encompasses a majority of practical applications. For larger multipliers, new heuristics were developed to optimize large multiplications of 1024×1024 bits and beyond. Comparison with the optimal method showed that the improved heuristics generally find solutions that are very close to the optimum and require only a fraction of the runtime. Furthermore, improved basic operations for the reduction of partial products were developed. One method makes better use of the FPGA logic by allowing incomplete multipliers for partial products in the optimization process. Another method generalizes Karatsuba’s algorithm that saves resources at the cost of speed or additional latency. Furthermore, solutions have been developed to implement truncated multipliers with reduced accuracy requirements. These reduce the resources with guaranteed upper error bounds, as required in many applications. Here, the combined method mentioned above could be extended to determine resource-optimal solutions for given accuracy requirements. In addition, some unplanned work arose during the course of the project as a result of work package deliverables or the collaboration with partners. This includes the application of optimized multipliers in machine learning, the special case of squaring, the multiplication with constants and its application in digital filters. Most of the methods have been embedded in the open-source framework FloPoCo and are thus available to the public.

Publications

• Comparison of Arithmetic Number Formats for Inference in Sum-Product Networks on FPGAs. 2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) (2020, 5), 75-83. American Geophysical Union (AGU).
  Sommer, Lukas; Weber, Lukas; Kumm, Martin & Koch, Andreas
  
• Heuristics for the Design of Large Multipliers for FPGAs. 2020 IEEE 27th Symposium on Computer Arithmetic (ARITH) (2020, 6), 17-24. American Geophysical Union (AGU).
  Bottcher, Andreas; Kullmann, Keanu & Kumm, Martin
  
• Resource Optimal Truncated Multipliers for FPGAs. 2021 IEEE 28th Symposium on Computer Arithmetic (ARITH) (2021, 6), 102-109. American Geophysical Union (AGU).
  Bottcher, Andreas; Kumm, Martin & de Dinechin, Florent
  
• Hardware-Aware Design of Multiplierless Second-Order IIR Filters With Minimum Adders. IEEE Transactions on Signal Processing, 70(2022), 1673-1686.
  Garcia, Remi; Volkova, Anastasia; Kumm, Martin; Goldsztejn, Alexandre & Kuhle, Jonas
  
• Hardware-Aware Quantization for Multiplierless Neural Network Controllers. 2022 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS) (2022, 11, 11), 541-545. American Geophysical Union (AGU).
  Habermann, Tobias; Kühle, Jonas; Kumm, Martin & Volkova, Anastasia
  
• Resource Optimal Squarers for FPGAs. 2022 32nd International Conference on Field-Programmable Logic and Applications (FPL) (2022, 8), 40-46. American Geophysical Union (AGU).
  Bottcher, Andreas; Kumm, Martin & De Dinechin, Florent
  
• Truncated Multiple Constant Multiplication with Minimal Number of Full Adders. 2022 IEEE International Symposium on Circuits and Systems (ISCAS) (2022, 5, 28), 263-267. American Geophysical Union (AGU).
  Garcia, Remi; Volkova, Anastasia & Kumm, Martin
  
• Design of Optimal Multiplierless FIR Filters With Minimal Number of Adders. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(2), 658-671.
  Kumm, Martin; Volkova, Anastasia & Filip, Silviu-Ioan
  
• Towards Globally Optimal Design of Multipliers for FPGAs. IEEE Transactions on Computers, 72(5), 1261-1273.
  Böttcher, Andreas & Kumm, Martin