Ein Verfahren zur Integration von Allocation und Binding in das Modulo Scheduling unter Verwendung komplexer Teilschaltungen

• Antragsteller: Professor Dr.-Ing. Peter Zipf
• Fachliche Zuordnung: Rechnerarchitektur, eingebettete und massiv parallele Systeme
• Förderung: Förderung von 2019 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 420658696

• Erstellungsjahr: 2023

Zusammenfassung der Projektergebnisse

In diesen Projekt sollten bestehende Verfahren zur Erzeugung von Schaltungen auf Register­Transfer-Ebene aus Verhaltensbeschreibungen (z.B. C/C++) verbessert, bzw. neue Verfahren entwickelt werden. Als Ausgangslage dienten folgende Verfahren: 1. Iterative Ressourcenallokation: Die in der Hardwareimplementierung zur Verfüfung stehenden Ressourcen (z.B. Anzahl der Multiplizierer, Block-RAM-Instanzen oder Speicherinterfaces) werden iterativ verändert, um verschiedene Durchsatz/Hardware­Tradeoffs zu ermöglichen, wodurch die nachfolgenden Schritte des Syntheseprozesses für jede Ressourcenallokation durchlaufen werden müssen. 2. Modulo Scheduling für eine gegebene Ressourcenallokation: Aufeinander folgende Berechnungen des zu implementierenden Algorithmus werden ineinander verschränkt ausgeführt, um die zur Verfügung stehende Hardware möglichst effizient auszulasten, indem Parallelität in der Eingangsbeschreibung ausgenutzt wird. Dabei müssen die Berechnungszeitpunkte der auszuführenden Operationen so gewählt werden, dass lediglich die in der vorherigen Allokation bereitgestellten Ressourcen benötigt und verwendet werden. 3. Binding für gegebenes Modulo Schedule: Die Zuordnung, welche Operation auf welcher Hardwareeinheit ausgeführt wird, beeinflusst direkt den Zusatzaufwand im Datenpfad, um die Recheneinheiten mit den korrekten Daten zu versorgen. Daher werden Einding-Algorithmen verwerdet, um für ein gegebenes Modulo Schedule zu entscheiden, welche Operation auf welcher Hardwareeinheit ausgeführt wird, sodass der zusätzliche Implementierungsaufwand minimiert wird. Diese isolierte Lösung der einzelnen Schritte, die Komplexität des Modulo Scheduling Problems und die Größe von praxisrelevanten Problemen haben zur Folge, dass typischerweise nur ein Bruchteil des gesamten Entwurfsraums exploriert werden kann und oft auch nur sub-optimale Lösungen bzgl. des Durchsatz/Hardware-Tradeoffs erzielt werden können. Daher wurden die folgenden Antragsziele definiert: 1. Bereitstellung durchsatzoptimaler Hardwareimplementierungen durch die Kombination von Allokation und Modulo Scheduling 2. Reduzierung der HLS-Laufzeit durch eine neuartige, hardwarebewusste Subgraph Mining Heuristik. 3. Verringerung der Berechnungszeit für Modulo Scheduling durch Verwendung der Ergebnisse der Subgraph Mining Heuristik. Die Umsetzung von Ziel 1 zeigte, dass Pareto-optimale Schaltungen bzgl. Hardwareaufwand/Durchsatz gezielt identifiziert werden können und dass dominierte Lösungen teils übersprungen werden können ohne explizit berechnet werden zu müssen. Durch die Umsetzung des zweiten Ziels konnte eine Reduktion des Zeitaufwands zum Subgraph Mining durch problemspezifische Einschränkungen des Suchraums erreicht werden und dessen Verwendung zur Lösung des dritten Ziels bewirkte eine systemati­ sche Verkleinerung der resultierenden Modulo Scheduling-Probleme, was eine signifikante Laufzeitverkürzung zur Folge hat.

Projektbezogene Publikationen (Auswahl)

• Design-Space Exploration with Multi-Objective Resource-Aware Modulo Scheduling. Lecture Notes in Computer Science, 170-183. Springer International Publishing.
  Oppermann, Julian; Sittel, Patrick; Kumm, Martin; Reuter-Oppermann, Melanie; Koch, Andreas & Sinnen, Oliver
  
• Isomorphic Subgraph-based Problem Reduction for Resource Minimal Modulo Scheduling. 2019 International Conference on ReConFigurable Computing and FPGAs (ReConFig), 1-8. IEEE.
  Sittel, Patrick; Fiege, Nicolai; Kumm, Martin & Zipf, Peter
  
• Modulo Scheduling with Rational Initiation Intervals in Custom Hardware Design. 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC), 568-573. IEEE.
  Sittel, Patrick; Wickerson, John; Kuimm, Martin & Zipf, Peter
  
• Optimal and Heuristic Approaches to Modulo Scheduling With Rational Initiation Intervals in Hardware Synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(3), 614-627.
  Sittel, Patrick; Fiege, Nicolai; Wickerson, John & Zipf, Peter
  
• Speeding Up Optimal Modulo Scheduling with Rational Initiation Intervals. 2022 32nd International Conference on Field-Programmable Logic and Applications (FPL), 322-326. IEEE.
  Fiege, Nicolai; Sittel, Patrick & Zipf, Peter
  
• BLOOP: Boolean Satisfiability-based Optimized Loop Pipelining. ACM Transactions on Reconfigurable Technology and Systems, 16(3), 1-32.
  Fiege, Nicolai & Zipf, Peter