Overcoming the Memory Bottleneck in Fully Automated High-Level Synthesis

In the past decade, FPGAs have emerged as a major platform for digital system implementation, since they strike a balance between off-the-shelf SoCs which are inexpensive but offer little design flexibility, and ASICs which allow full customization but come at a high development cost.

FPGAs are programmed in HDLs such as VHDL and Verilog, which are capable of exposing concurrency and providing bit-level control. In order to facilitate the use of FPGAs for software developers, HLS tools are used to translate between high-level languages, such as C, and these HDLs. Multiple concepts on the level of automation and forms of user intervention have been proposed. This work focuses on a fully automated HLS tool flow without any user interaction for kernel selection, HLS optimizations, and kernel integration.

One of the biggest problems for automated HLS tools is the memory bottleneck. On one side, it is caused by the lack of parallelism inside the kernel, preventing the accelerator from using the whole bandwidth of the memory interface. On the other side, memory dependencies prevent memory accesses from being executed in parallel or out-of-order.

In the first part of this thesis, multiple HLS optimizations are introduced: AutoBoxing is a scope-enhancing optimization that enables inlining and loop unrolling. Multi-way speculation is an improved version of the speculation optimization already used in many HLS tools to reduce control flow and increase instruction-level parallelism. ACD is an algorithm that promotes exclusive memory accesses and evenly distributes workload on the cache system.

In the second part of this thesis, a memory disambiguation toolbox, which contains five complementary disambiguation techniques, is presented. Each technique focuses on different memory access patterns and control flow structures. Additionally, an algorithm that wraps the memory disambiguation toolbox by automatically applying the disambiguation techniques is introduced.

Finally, an evaluation using a MicroBlaze soft-core processor and an Aritx-7 FPGA is conducted. It uses 27 benchmarks from three different benchmark suites covering different application domains, complexities, and memory access patterns. First, the impact of each optimization is discussed in detail, showing how HLS optimizations and disambiguation techniques work hand in hand to improve the performance of the accelerators. Afterwards, the automatic optimization is evaluated in order to determine the impact of the memory toolbox on a fully automated HLS tool flow. The evaluation will show that the optimizations presented in this work increase the acceleration of the benchmarks from an average of 7.17 to 24.6.

In den letzten zehn Jahren haben sich FPGAs als wichtige Plattformen für die Implementierung digitaler Systeme etabliert. Sie bieten einen Kompromiss zwischen handelsüblichen SoCs, die kostengünstig, aber in ihrer Designflexibilität eingeschränkt sind, und ASICs, die eine vollständige Anpassung ermöglichen, aber hohe Entwicklungskosten verursachen.

FPGAs werden in Hardwarebeschreibungssprachen wie VHDL und Verilog programmiert. Diese ermöglichen mehr Parallelität und eine bessere Kontrolle auf Bit-Ebene. Um Softwareentwicklern die Verwendung von FPGAs zu erleichtern, werden High-Level Synthese Tools verwendet, die Hochsprachen wie C in Hardware-Beschreibungssprachen übersetzen. Es gibt verschiedene Konzepte zum Automatisierungsgrad und zur Form der Benutzerinteraktion. Diese Arbeit konzentriert sich auf einen vollständig automatisierten HLS-Tool-Flow, der ohne jegliche Benutzerinteraktion für die Kernelauswahl, die HLS-Optimierungen und die Kernelintegration auskommt.

Eines der größten Probleme für automatisierte HLS-Tools ist der Speicherengpass. Einerseits wird dieser durch die mangelnde Parallelität im Kernel verursacht, wodurch die Beschleuniger nicht die gesamte Bandbreite der Speicherschnittstelle ausnutzen. Andererseits verhindern Speicherabhängigkeiten, dass Speicherzugriffe parallel oder außer der Reihe ausgeführt werden können.

Im ersten Teil dieser Arbeit werden mehrere HLS-Optimierungen vorgestellt: AutoBoxing ist eine Optimierung, die es dem HLS-Tool durch Inlining und Loop Unrolling ermöglicht, größere Kernel auszuwählen. Multi-Way-Spekulation ist eine verbesserte Version der Spekulationsoptimierung, die in vielen HLS-Tools bereits verwendet wird, um Kontrollfluss zu reduzieren und die Parallelität auf Instruktionsebene zu erhöhen. ACD ist ein Algorithmus, der die Anzahl exklusiver Speicherzugriffe erhöht und die Arbeitslast gleichmäßig auf das Cache-System verteilt.

Im zweiten Teil dieser Arbeit wird ein Werkzeugkasten vorgestellt, der fünf sich ergänzende Techniken enthält, um Speicherabhängigkeiten zu entkoppeln. Jede Optimierung konzentriert sich auf unterschiedliche Speicherzugriffs- und Kontrollflussmuster. Zusätzlich wird ein Algorithmus vorgestellt, der die Optimierungen des Werkzeugkastens automatisiert anwendet.

Abschließend wird eine Evaluation unter Verwendung eines MicroBlaze-Softcore-Prozessors und eines Aritx-7 FPGA durchgeführt. Dabei kommen 27 Benchmarks aus drei verschiedenen Benchmark-Suiten zum Einsatz, die unterschiedliche Anwendungsbereiche, Komplexitäten und Speicherzugriffsmuster abdecken. Zunächst wird der Effekt, den jede Optimierung für sich hat, diskutiert und es wird gezeigt, wie die HLS-Optimierungen und der Werkzeugkasten zusammenwirken, um die Beschleuniger zu verbessern. Anschließend wird evaluiert, wie der automatische Algorithmus den Werkzeugkasten für Speicheroptimierungen in einem vollständig automatisierten HLS-Tool-Flow einbindet. Die Evaluation wird zeigen, dass die in dieser Arbeit vorgestellten Optimierungen die Beschleunigung der Benchmarks von durchschnittlich 7,17 auf 24,6 erhöhen.