Automatic SIMD vectorization of SSA-based control flow graphs

Abstract

Applications that require the same computation to be performed on huge amounts of data play an important role in today’s computing landscape: Particle simulations, stock option price estimation, and video decoding are some examples for such data-parallel programs. Languages like OpenCL and CUDA facilitate their development. They allow to write a scalar function that is executed on different input values in parallel by a runtime system. To unleash the full parallel potential of modern processors, the compiler and runtime system of these languages then have to make use of all available cores as well as SIMD instructions: These allow to efficiently execute a single operation on multiple input values at once per core. This thesis presents Whole-Function Vectorization (WFV), an approach that allows a compiler to automatically exploit SIMD instructions in data-parallel settings. Without WFV, one processor core executes a single instance of a data-parallel function. WFV transforms the function to execute multiple instances at once using SIMD instructions. For simple, straight-line code, the transformation is easily applied and delivers drastically improved performance. However, problems such as particle simulations or shading in computer graphics exhibit more complex code. We show that in such scenarios, a na¨ive WFV approach will often not improve performance or even slow down execution. The focus of this thesis is to present an advanced WFV algorithm that includes a variety of analyses and code generation techniques that help to improve the generated code. An implementation of WFV has been evaluated in different settings: First, in a stand-alone OpenCL runtime system. Second, in a compiler for domain-specific languages used in real-time ray tracing. Third, in a compiler that performs classic loop vectorization upon request by the user. In all scenarios, WFV improves performance compared to state-of-the-art approaches. The performance of the OpenCL implementation is on par with the proprietary Intel driver, and faster than any other available CPU driver.

Anwendungen wie Partikelsimulationen oder die Optionspreisbewertung an Aktienmärkten, die gleiche Berechnungen auf eine Vielzahl von Daten anwenden, sind ein wichtiger Aspekt der heutigen Informatik. Um das Erstellen solcher Anwendungen zu vereinfachen wurden datenparallele Programmiersprachen wie OpenCL und CUDA entwickelt. Diese ermöglichen es, ein skalares Programm zu schreiben, das von einem Laufzeitsystem parallel für verschiedene Eingabewerte ausgeführt wird. Um das vollständige Potenzial heutiger Prozessoren auszunutzen, müssen der Übersetzer und das Laufzeitsystem sowohl alle verfügbaren Kerne als auch SIMD Befehle verwenden: Letztere führen dieselbe Operation effizient für mehrere Eingabewerte gleichzeitig aus. Die vorliegende Arbeit beschreibt Whole-Function Vectorization (WFV), einen Ansatz, der es dem Übersetzer erlaubt, in einem datenparallelen Kontext automatisch SIMD Instruktionen zu verwenden. Ohne WFV wertet jeder Prozessorkern eine einzelne Instanz einer Funktion aus. WFV transformiert die Funktion so, dass sie mit Hilfe von SIMD Befehlen mehrere Instanzen auf einmal auswertet. Diese Transformation ist für einfachen, verzweigungsfreien Programmcode leicht durchzuführen und bringt drastische Laufzeitverbesserungen. Probleme wie Partikelsimulationen jedoch verwenden komplexeren Code. Häufig verbessert dann ein naiver WFV Ansatz die Laufzeit nicht oder verschlechtert sie sogar. Die vorliegende Arbeit beschreibt einen Algorithmus für WFV, der neue Analysen und Techniken zur Codeerzeugung verwendet, die die Performanz des Programms verbessern. WFV wurde in unterschiedlichen Anwendungsgebieten evaluiert: Erstens in einem OpenCL Laufzeitsystem. Zweitens in einem Übersetzer für domänenspezifische Sprachen für Echtzeit-Ray-Tracing. Drittens in einem Übersetzer, der klassische Schleifenvektorisierung durchführt. In allen drei Szenarien zeigt die Auswertung Verbesserungen der Laufzeit bei Verwendung von WFV im Vergleich mit dem neuesten Stand der Technik. Das OpenCL Laufzeitsystem steht auf einer Stufe mit dem äquivalenten Produkt von Intel und ist effizienter als jeder andere CPU-basierte Ansatz.