As graphics processing units (GPUs) are being used increasingly for general purpose processing, efficient tooling for programming such parallel architectures becomes essential. Despite the continuous effort of programmability improvement in CUDA and OpenCL, they remain relatively low-level languages and require in-depth archi- tecture knowledge to achieve high-performance implementations. Developers have to perform memory management manually to exploit the multi-layered compute and memory hierarchy. This type of hand-tuned expert implementations suffers from performance portability, namely, existing implementations are not guaranteed to be efficient on new architectures, and developers have to perform the tedious tuning and optimization repeatedly for every architecture. To circumvent this issue, developers can choose to utilize high-performance libraries offered by hardware vendors as well as open-source communities. Utilizing libraries is performance portable as it is the library developer’s job to maintain the implementation. However, it lacks programmability. Library functions are provided with pre-defined APIs, and the level of abstraction may not be sufficient for developers of a certain do- main. Furthermore, using library-based implementations precludes the possibility of applying system-level optimizations across different functions. In this thesis, we present a domain-specific language (DSL) approach that can achieve both perfor- mance portability and programmability within a particular domain. This is possible by exploiting domain-specific abstractions and combining them with architecture- specific optimizations. The abstractions enable programmability and flexibility for domain developers, and the compiler-based optimization facilitates performance portability across different architectures. The core of such a DSL approach is its optimization engine, which combines algorithm and hardware knowledge to explore the optimization space efficiently. Our contributions in this thesis target system-level optimizations and code generations for GPU architectures. Today’s applications such as in image processing and machine learning grow in complexity and consist of many kernels in a computation pipeline. Optimizing each kernel individually is no longer sufficient due to the rapid evolution of modern GPU architectures. Each architecture generation reveals higher computing power as well as memory bandwidth. Nevertheless, the computing power increase is generally faster than the memory bandwidth improvement. As a result, good locality is essential to achieve high-performance implementations. For example, the inter- kernel communications within an image processing pipeline are intensive and exhibit many opportunities for locality improvement. As the first contribution, we present a technique called kernel fusion to reduce the number of memory accesses to the slow GPU global memory. In addition, we automate the transformation in our source-to-source compiler by combining domain knowledge in image processing and architecture knowledge of GPUs. Another trend we can observe following recent architecture development is the increasing number of CUDA cores and streaming multiprocessors (SMs) for compu- tation. Traditionally, GPU programming is about exploring data-level parallelism. Following the single instruction, multiple threads (SIMTs) execution model, data can be mapped to threads to benefit from the massive computing power. Nevertheless, small images that were considered costly on older architectures can no longer occupy the device fully on new GPUs. It becomes important to explore also kernel-level parallelism that can efficiently utilize the growing number of compute resources on the GPU. As the second contribution, we present concurrent kernel execution techniques to enable fine-grained resource sharing within the compute SMs. In addition, we compare different implementation variants and develop analytic models to predict the suitable option based on the algorithmic and architecture knowledge. After considering locality and parallelism, which are the two most essential op- timization objectives on modern GPU architectures, we can start examining the possibilities to optimize the computations within an algorithm. As the third contri- bution in this thesis, we present single-kernel optimization techniques for the two most commonly used compute patterns in image processing, namely local and global operators. For local operators, we present a systematic analysis of an efficient border handling technique based on iteration space partitioning. We use the domain and architecture knowledge to capture the trade-off between occupancy and instruction usage reduction. Our analytic model assists the transformation in the source-to- source compiler to decide on the better implementation variant and improves the end-to-end code generation. For global operators, we present an efficient approach to perform global reductions on GPUs. Our approach benefits from the continuous effort of performance and programmability improvement by hardware vendors, for example, by utilizing new low-level primitives from Nvidia. The proposed techniques cover not only multi-kernel but also single-kernel opti- mization, and are seamlessly integrated into our image processing DSL and source- to-source compiler called Hipacc. In the end, the presented DSL framework can dras- tically improve the productivity of domain developers aiming for high-performance GPU implementations.

Durch den steigenden Einsatz von Grafikprozessoren (GPUs) zur Durchführung gewöhnlicher Berechnungen gewinnen effiziente Programmierwerkzeuge für diese immer mehr an Bedeutung. Unabhängig von den andauernden Bestrebungen zum Erreichen einer besseren Programmierbarkeit in CUDA und OpenCL, bleiben diese Sprachen dennoch relativ Hardware-nah und erfordern ein tiefgreifendes Architektur- verständnis, um gute Ergebnisse zu erzielen. Entwickler und Entwicklerinnen müssen den Grafikspeicher manuell verwalten, um die vielschichtige Berechnungs- und Spei- cherhierarchie voll auszuschöpfen. Die Leistungsfähigkeit dieser händisch optimier- ten Implementierungen ist wenig portabel, d.h. es ist nicht garantiert, dass sich diese auf neuen Architekturen effizient ausführen lassen. Stattdessen müssen Entwickelnde für jede neue Architektur wiederholt aufwendige Optimierungen durchführen. Um dieses Problem zu umgehen, können Entwickelnde Hochleistungsbibliotheken ein- setzen, die von den Hardware-Herstellerfirmen oder der Open-Source-Gemeinschaft bereitgestellt werden. Durch den Einsatz solcher Bibliotheken wird die Portabilität erhöht, da es die Aufgabe des Anbietenden der Bibliothek ist deren Effizienz auf verschiedenen Architekturen sicherzustellen. Allerdings ist der Einsatz solcher Biblio- theken mit eingeschränkten Freiheitsgraden bei der Programmierbarkeit verbunden. Bibliotheksfunktionen werden über ein vordefinierte Programmierschnittstelle (API) angeboten, dessen Abstraktionsebene für Entwickelnde einer bestimmten Domäne nicht unbedingt ausreichend sein muss. Außerdem sind bibliotheksbasierte Ansätze hinderlich bei der Optimierung auf Systemebene über verschiedene Funktionen hinweg. In dieser Arbeit wird ein Ansatz mittels einer domänenspezifischen Sprache (DSL) vorgestellt, der sowohl einen hohen Grad an portabler Leistungsfähigkeit als auch an Programmierbarkeit bietet. Dies wird ermöglicht durch die Kombination von domänenspezifischen Abstraktionen mit architekturspezifischen Optimierungen. Die Abstraktionen bieten ein hohes Maß an Programmierbarkeit und Flexibilität für Domänenentwickelnde, während die Compiler-basierten Optimierungen die Portabi- lität der Leistungsfähigkeit über verschiedene Architekturen hinweg sicherstellen. Der Kern eines solchen DSL-Ansatzes sind Optimierungen, welche algorithmisches Wissen mit Hardware-Wissen kombinieren, um Varianten effizient zu explorieren. Die wissenschaftlichen Beiträge dieser Arbeit liegen im Bereich von Optimierungen auf Systemebene und der Quellcodegenerierung für GPUs. Heutige Applikationen aus den Bereichen der Bildverarbeitung und dem ma- schinellen Lernen wachsen stetig in ihrer Komplexität und bestehen aus mehreren Berechnungskernen (engl. Kernel) einer Berechnungskette. Jeden Kernel einzeln zu optimieren ist durch die schnelle Evolution moderner GPU-Architekturen nicht mehr zielführend. Mit jeder neuen Architekturgeneration steigt die Rechenleistung und die zur Verfügung stehende Speicherbandbreite. Dabei überwiegt der Anstieg zusätzlicher Leistung deutlich gegenüber dem Anstieg zusätzlicher Bandbreite. Da- her ist eine gute Datenlokalität essenziell, um Hochleistungsimplementierungen zu erhalten. So birgt beispielsweise die Inter-Kernel-Kommunikation innerhalb einer Bildverarbeitungskette großes Potential für verbesserte Datenlokalität. Als erster wissenschaftlicher Beitrag wird eine Technik namens Kernel-Fusion vorgestellt, mit deren Hilfe die Anzahl und Zugriffe auf den langsamen GPU-Hauptspeicher redu- ziert werden kann. Zusätzlich wird gezeigt, dass diese Transformation von einem Quelltext-zu-Quelltext-Übersetzer automatisiert durchgeführt werden kann, indem Domänenwissen aus der Bildverarbeitung mit dem Architekturwissen über GPUs kombiniert wird. Ein weiterer beobachtbarer Trend in der Architekturentwicklung ist die zuneh- mende Anzahl an CUDA-Rechenkernen und Streaming-Prozessoren (SMs) zur Be- rechnung. Herkömmliche GPU-Programmierung konzentriert sich auf die effiziente Ausnutzung der vorhandenen Datenparallelität. Mit dem Single-Instruction, Multiple Threads (SIMT) Model können Daten einzelner Ausführungsfäden (engl. Threads) zugewiesen werden, um von der massiven Rechenleistung zu profitieren. Allerdings kann die GPU für kleinere Bilder, die auf älteren Architekturen noch als sehr be- rechnungsintensiv galten, nicht mehr voll belegt werden. Um dennoch die steigende Anzahl an Rechenwerken einer GPU effizient auszunutzen, wird es immer wichtiger auch die Parallelität auf Kernel-Ebene zu betrachten. Als zweiter wissenschaftlicher Beitrag werden Techniken zur nebenläufigen Kernel-Ausführung vorgestellt, mit deren Hilfe Betriebsmittel innerhalb der Rechenwerke feingranular geteilt werden können. Zusätzlich werden verschiedene Implementierungsvarianten verglichen und analytische Modelle entwickelt, um geeignete Entwurfspunkte basierend auf algorithmischem und architekturellem Wissen vorherzusagen. Nachdem Datenlokalität und Parallelität betrachtet wurden, welche die zwei wich- tigsten Optimierungsziele moderner GPU-Architekturen darstellen, werden weitere Optimierungsmöglichkeiten der Berechnungen innerhalb eines Algorithmus erörtert. Als dritter wissenschaftlicher Beitrag dieser Arbeit werden Techniken zur Opti- mierung einzelner Kernels für lokale und globale Operatoren vorgestellt, die zu den am weitverbreitetsten Berechnungsschritten der Bildverarbeitung gehören. Für lokale Operatoren wird eine systematische Analyse zur effizienten Randbehand- lung basierend auf Iterationsraumpartitionierung vorgestellt. Dazu wird Domänen- und Architekturwissen verwendet, um einen geeigneten Arbeitspunkt zwischen der Ressourcenbelegung und Reduzierung der Instruktionsauslastung zu finden. Das analytische Model unterstützt dabei die Quelltext-zu-Quelltext-Transformation, um zu entscheiden welches die bessere Implementierungsvariante ist und damit die Ende-zu-Ende-Quellcodeerzeugung zu verbessern. Für globale Operatoren wird ein effizienter Ansatz zur Ausführung globaler Reduktionen auf GPUs vorgestellt. Der Ansatz profitiert von den kontinuierlichen Verbesserungen der Leistung und Programmierbarkeit durch die Hardwarehersteller, wie beispielsweise die Nutzung neuer Hardware-naher Primitive bereitgestellt durch Nvidia. Die vorgestellten Techniken beschränken sich nicht nur auf Optimierungen für mehrere Kernels, sondern betrachten auch einzelne Kernels und lassen sich nahtlos in unsere DSL zur Bildverarbeitung und den dazugehörigen Quelltext-zu-Quelltext- Übersetzer namens Hipacc integrieren. Schließlich kann mit dem vorgestellten DSL- Framework die Produktivität der Entwicklerin bzw. Entwicklers, die nach hochleis- tungsfähigen GPU-Implementierungen streben, drastisch verbessert werden.