Portability of irregular randomized simulations to GPUs

Abstract

Graphics Processing Units (GPUs) have become fundamental to high-performance computing, offering substantial acceleration for data-parallel workloads. However, their architectural design - optimized for regular, uniform computations - poses significant challenges when applied to irregular randomized simulations, which are prevalent in fields such as particle physics, fluid dynamics, and molecular modeling. This thesis investigates the GPU-based acceleration of the Direct Simulation Monte Carlo (DSMC) algorithm, a stochastic method used to simulate rarefied gas dynamics and a representative case of irregular computation. Focusing on the DSMC implementation in the PICLas software framework, the work identifies key GPU challenges such as thread divergence, irregular memory access, and control flow variability. To address these, an abstraction model was developed and translated into a CUDA-based GPU prototype, incorporating optimization strategies including memory coalescence, hierarchical sorting, and divergence-aware sampling via Metropolis-Hastings. Experimental evaluations demonstrate significant performance improvements over both a naive GPU and sequential CPU baseline, particularly in complex simulation scenarios. The optimized GPU implementation achieved speed-up factors of up to four orders of magnitude for large-scale simulations, while preserving algorithmic correctness and scalability. These results confirm that, with carefully designed abstractions and architecture-aware optimizations, irregular randomized simulations like DSMC can be effectively ported to GPUs. This thesis contributes a validated prototype, generalizable optimization strategies, and insights into the performance boundaries of GPU-based stochastic simulation, paving the way for broader application in high-performance scientific computing. Grafikprozessoren (engl. Graphics Processing Units, GPUs) haben sich als essenzielle Komponenten des wissenschaftlichen Hochleistungsrechnens etabliert und ermöglichen erhebliche Beschleinigung bei der Verarbeitung datenparalleler Verfahren. Ihre Architektur ist jedoch primär auf reguläre, homogen strukturierte Berechnungen ausgelegt, was ihre Anwendung auf unregelmäßige, stochastisch geprägte Simulationsverfahren erheblich erschwert. Solche Verfahren finden breite Anwendung in Disziplinen wie der Teilchenphysik, der Strömungsmechanik und der Molekülmodellierung. Gegenstand dieser Arbeit ist die GPU-basierte Beschleunigung des Direct Simulation Monte Carlo (DSMC)-Algorithmus - eines probabilistischen Verfahrens zur Simulation von Gasströmungen im Bereich mit geringer Dichte - als repräsentatives Beispiel für unregelmäßige Berechnungen (engl. irregular computations). Im Fokus steht die Implementierung des DSMC-Verfahrens innerhalb des Software-Frameworks PICLas. Dabei werden zentrale Herausforderungen identifiziert, die beim Einsatz von GPUs für unregelmäßige Algorithmen auftreten - insbesondere thread divergence, irreguläre Speicherzugriffe und ein nicht-deterministischer Kontrollfluss. Zur Bewältigung dieser Probleme wurde ein Abstraktionsmodell entwickelt, das in einen CUDA-basierten GPU-Prototyp überführt wurde. Dieser integriert eine Reihe gezielter Optimierungsstrategien, darunter memory coalescing, hierarchiebasiertes Sortieren sowie die Generation zufälliger Zahlen (engl. sampling) ohne thread divergence auf Basis des Metropolis-Hastings-Algorithmus. Die experimentellen Ergebnisse belegen substanzielle Performanzgewinne gegenüber sowohl einer naiven GPU-Implementierung als auch zu einer sequenziellen CPU-Referenz. Besonders in komplexen Simulationsszenarien konnten speed-up-Faktoren von bis zu vier Größenordnungen erreicht werden - bei gleichzeitiger Wahrung der algorithmischen Korrektheit und linearer Skalierbarkeit. Diese Resultate verdeutlichen, dass unregelmäßige, stochastische Simulationsverfahren wie DSMC durch gezielte Abstraktion und architekturadäquate Optimierung effizient auf GPU-Architekturen übertragbar sind. Die vorliegende Arbeit liefert einen validierten Prototyp, übertragbare Optimierungskonzepte und einen Beitrag zum Verständnis der Leistungsgrenzen für unregelmäßige, stochastische Simulationen auf GPUs - und schafft damit eine Grundlage für die breitere Nutzung solcher Verfahren im wissenschaftlichen Hochleistungsrechnen.