Extending C++ for explicit data-parallel programming via SIMD vector types

Data-parallel programming is more important than ever since serial performance is stagnating. All mainstream computing architectures have been and are still enhancing their support for general purpose computing with explicitly data-parallel execution. For CPUs, data-parallel execution is implemented via SIMD instructions and registers. GPU hardware works very similar allowing very efficient parallel processing of wide data streams with a common instruction stream. These advances in parallel hardware have not been accompanied by the necessary advances in established programming languages. Developers have thus not been enabled to explicitly state the data-parallelism inherent in their algorithms. Some approaches of GPU and CPU vendors have introduced new programming languages, language extensions, or dialects enabling explicit data-parallel programming. However, it is arguable whether the programming models introduced by these approaches deliver the best solution. In addition, some of these approaches have shortcomings from a hardware-specific focus of the language design. There are several programming problems for which the aforementioned language approaches are not expressive and flexible enough. This thesis presents a solution tailored to the C++ programming language. The concepts and interfaces are presented specifically for C++ but as abstract as possible facilitating adoption by other programming languages as well. The approach builds upon the observation that C++ is very expressive in terms of types. Types communicate intention and semantics to developers as well as compilers. It allows developers to clearly state their intentions and allows compilers to optimize via explicitly defined semantics of the type system. Since data-parallelism affects data structures and algorithms, it is not sufficient to enhance the language's expressivity in only one area. The definition of types whose operators express data-parallel execution automatically enhances the possibilities for building data structures. This thesis therefore defines low-level, but fully portable, arithmetic and mask types required to build a flexible and portable abstraction for data-parallel programming. On top of these, it presents higher-level abstractions such as fixed-width vectors and masks, abstractions for interfacing with containers of scalar types, and an approach for automated vectorization of structured types. The Vc library is an implementation of these types. I developed the Vc library for researching data-parallel types and as a solution for explicitly data-parallel programming. This thesis discusses a few example applications using the Vc library showing the real-world relevance of the library. The Vc types enable parallelization of search algorithms and data structures in a way unique to this solution. It shows the importance of using the type system for expressing data-parallelism. Vc has also become an important building block in the high energy physics community. Their reliance on Vc shows that the library and its interfaces were developed to production quality.Datenparalleles Programmieren ist wichtiger als jemals zuvor, denn die serielle Leistung stagniert. Alle wichtigen Computerarchitekturen haben ihre Unterstützung für universales Rechnen in expliziter datenparalleler Ausführung erweitert und weitere Erweiterungen sind angekündigt. Hauptprozessoren implementieren datenparallele Ausführung mittels SIMD Instruktionen und Registern. Grafik Hardware arbeitet sehr ähnlich und ermöglicht effiziente parallele Verarbeitung von breiten Datenströmen mit dem selben Instruktionsstrom. Diese Fortschritte paralleler Hardware wurden allerdings nicht von den entsprechend nötigen Erweiterungen der etablierten Programmiersprachen begleitet. Softwareentwickler wurden also nicht in die Lage versetzt die inhärente Datenparallelität ihrer Algorithmen explizit anzugeben. CPU und GPU Hersteller haben daher neue Sprachen, Spracherweiterungen oder Dialekte entwickelt, um datenparalleles Programmieren zu ermöglichen. Allerdings ist es diskutabel ob die eingeführten Programmierparadigmen dieser Ansätze die beste Lösung liefern. Des Weiteren haben einige Ansätze Mängel durch einen hardwarespezifischen Fokus des Sprachdesigns. Es gibt einige Aufgabenstellungen, die sich mit den erwähnten Ansätzen nicht sinnvoll oder flexibel genug ausdrücken lassen. Die vorliegende Dissertation befasst sich daher mit einer datentypbasierten Lösung für die C++ Programmiersprache. Die präsentierten Konzepte und Schnittstellen sind spezifisch für C++, aber so abstrakt wie möglich dargestellt, um die Übernahme in andere Programmiersprachen zu erleichtern. Der präsentierte Ansatz stützt sich auf die Beobachtung, dass Datentypen in C++ sehr ausdrucksstark sind. Datentypen kommunizieren sowohl den Entwicklern als auch dem Compiler Intention und Semantik. Der Entwickler wird entsprechend befähigt seine Intentionen klar auszudrücken während der Compiler seine Optimierungen auf die eindeutig definierte Semantik des Typsystems stützen kann. Da Datenparallelität sowohl Datenstrukturen als auch Algorithmen betrifft, reicht es nicht aus die Programmiersprache nur in einem Gebiet zu erweitern. Die Definition von Datentypen, deren Operatoren datenparallele Ausführung ausdrücken, erweitert automatisch die Möglichkeiten Datenstrukturen zu erstellen. Diese Dissertation definiert daher systemnahe, vollständig portable, arithmetische Datentypen sowie Maskendatentypen. Diese Datentypen bilden eine flexible und portable Abstraktion für datenparalleles Programmieren. Darauf aufbauend präsentiert die Arbeit höhere Abstraktionen, so wie Vektoren und Masken fester Breite, Abstraktionen für die Schnittstelle zu skalaren Datentypen und einen Ansatz für die automatisierte Vektorisierung strukturierter Datentypen. Die Vc Bibliothek ist eine Implementierung dieser Datentypen. Ich habe die Vc Bibliothek entwickelt, um datenparallele Datentypen zu erforschen und als eine Lösung für das explizit datenparallele Programmieren. Um die Relevanz der Bibliothek zu zeigen, diskutiert diese Dissertation einige Beispielanwendungen der Vc Bibliothek. Die Vc Datentypen ermöglichen auf einzigartige Weise die Parallelisierung von Suchalgorithmen und Datenstrukturen. Es zeigt wie wichtig es ist das Typsystem zu nutzen, um Datenparallelität auszudrücken. Vc ist außerdem zu einem wichtigen Baustein für Software in der Hochenergiephysik geworden. Ihr Vertrauen in die Vc Bibliothek zeigt, dass die Arbeit in ein Qualitätsprodukt entwickelt wurde