Optimierung von Multiplizierern für rekonfigurierbare Logik

• Antragsteller: Professor Dr.-Ing. Martin Kumm
• Fachliche Zuordnung: Rechnerarchitektur, eingebettete und massiv parallele Systeme
• Förderung: Förderung von 2019 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 426369132

• Erstellungsjahr: 2023

Zusammenfassung der Projektergebnisse

Das Ziel des DFG-Forschungsprojekts war es, Schaltungen für die Multiplikationsoperation auf rekonfigurierbare Logik bezüglich Ressourcen-, Laufzeit- und Energiebedarf zu verbessern. Die Multiplikation stellt eine grundlegende arithmetische Operation dar, die in fast jedem komplexerem Algorithmus zu finden ist. Viele Algorithmen werden mittels rekonfigurierbarer Logik wie den Field Programmable Gate Arrays (FPGAs) beschleunigt. Eine Verbesserung der Multiplikationsoperation kommt daher einer Vielzahl von Anwendungen zugute. Der Entwurf von Multiplizierern wird herkömmlicherweise in drei Schritte aufgeteilt: die Generierung partieller Produkte, die Reduktion der partiellen Produkte sowie der Entwurf der finalen Addition. Gerade auf FPGAs können hier in jedem Schritt völlig unterschiedliche Schaltungsteile zum Einsatz kommen. Die Entwurfsschritte beeinflussen sich jedoch gegenseitig stark, so dass selbst bei der optimalen Lösung jedes einzelnen Schrittes nicht notwendigerweise eine global optimale Lösung entsteht. Ziel war es daher, mit modernen Optimierungsmethoden die Multiplikations-Operation für FPGAs zu verbessern. Ein zentrales Projektergebnis ist die kombinierte Optimierung aller drei Entwurfsschritte. Hier wurde das Optimierungsproblem mittels ganzzahliger linearer Programmierung formuliert, welches für eine vorgegebene Menge von Basisoperationen optimale Lösungen liefert und signifikant bessere Ergebnisse erzeugt als bisherige Methoden. Es wurde ursprünglich erwartet, dass sich das kombinierte Problem nur für sehr kleine Problemgrößen lösen lasst. Tatsächlich konnte gezeigt werden, dass sich die Methode für Multiplikationen auf aktuellen Computern mit bis zu 32 Bit einsetzen lässt, was einen Großteil praktischer Anwendungen umfasst. Für größere Multiplizierer wurden neue Heuristiken entwickelt, um große Multiplikationen mit 1024x1024 Bit und darüber hinaus zu optimieren. Der Vergleich mit dem optimalen Verfahren ergab, dass die verbesserten Heuristiken in der Regel Lösungen finden, die sehr nahe am Optimum liegen und dafür nur einen Bruchteil der Laufzeit benötigen. Darüber hinaus wurden verbesserte Basisoperationen für die Reduktion der partiellen Produkte entwickelt. Eine entwickelte Methode nutzt die FPGA-Logik besser, in dem auch unvollständige Multiplizierer für partiellen Produkte im Optimierungsprozess erlaubt werden. Eine andere Methode generalisiert den Algorithmus von Karatsuba, um insgesamt Ressourcen auf Kosten von Geschwindigkeit bzw. zusätzlicher Latenz einzusparen. Weiterhin wurden Lösungen entwickelt, um Multiplizierer mit reduzierter Genauigkeitsanforderung zu realisieren. Diese reduzieren den Aufwand bei garantierten oberen Fehlerschranken, wie sie in vielen Anwendungen benötigt werden. Hier konnte das oben genannte kombinierte Verfahren erweitert werden, um ressourcenoptimale Lösungen bei gegebenen Genauigkeitsanforderungen zu bestimmen. Darüber hinaus ergaben sich im Projektverlauf einige ungeplante Arbeiten, die durch die Ergebnisse von Arbeitspaketen oder der Zusammenarbeit mit Kooperationspartnern entstanden sind. Dies beinhaltet die Anwendung der optimierten Multiplizier im Bereich des maschinellen Lernens, den Spezialfall der Quadrierung, der Multiplikation mit Konstanten und dessen Anwendung in digitalen Filtern. Der Großteil der Verfahren wurde im Open-Source Framework FloPoCo eingebettet und ist somit der Öffentlichkeit zugänglich.

Projektbezogene Publikationen (Auswahl)

• 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