Improving performance of simulations and heuristic optimization on GPUs

Abstract

Parallelization is a ubiquitous technique for improving runtime performance of algorithms. Although parallelization is generally challenging and often leads to programming bugs, it is a leading method for processing growing amounts of data today. Due to the ongoing trend of exploring the unexplored, known methods are reaching their limits in terms of scalability and thus applicability. Particularly challenging is the use of graphics processing units (GPUs) that require specially optimized algorithms but feature impressive compute power. Unfortunately, the term "optimized" usually refers to newly developed algorithms that exploit the peculiarities of the underlying GPUs or at least follow their specific programming methodologies. The list of tweaked algorithms available for GPUs is already quite long and touch a wide range of domains. These include the well-known fields of massively parallel simulations and solving of optimization problems. Prominent examples in this context include particle simulations of physical processes (like molecular-dynamics simulations) and machine-learning based optimizers. However, existing approaches from these two domains often suffer from severe runtime, memory consumption, and applicability limitations. In this thesis, we present new approaches for both domains. Our methods considerably outperform current state of the art in terms of runtime and memory consumption. We were able to achieve runtime speedups of up to several orders of magnitude while reducing the amount of memory required compared to existing methods. Regarding applicability, our algorithms are designed to fit seamlessly into existing simulation programs and optimizers. This makes them a particularly valuable contribution to real-world applications as well.

Parallelisierung ist eine allgegenwärtige Technik zur Verbesserung der Laufzeitleistung von Algorithmen. Obwohl Parallelisierung im Allgemeinen eine Herausforderung darstellt und oft zu Programmierfehlern führt, ist sie heute eine führende Methode zur Verarbeitung wachsender Datenmengen. Aufgrund des anhaltenden Trends, das Unerforschte zu erforschen, stoßen die bekannten Methoden an ihre Grenzen der Skalierbarkeit und damit der Anwendbarkeit. Eine besondere Herausforderung ist der Einsatz von Grafikprozessoren (GPUs), die speziell optimierte Algorithmen erfordern, aber eine beeindruckende Rechenleistung aufweisen. Allerdings bedeuted der Begriff "optimiert" in der Regel neue Algorithmen zu entwickeln, die die Besonderheiten der zugrundeliegenden GPUs ausnutzen oder zumindest deren spezifischen Programmiermethodologien folgen. Die Liste der optimierten Algorithmen, die für GPUs verfügbar sind, ist bereits lang und deckt ein breites Bereichsspektrum ab. Dazu gehören die bekannten Anwendungsfelder der massiv parallelen Simulationen und das Lösen von Optimierungsproblemen. Prominente Beispiele in diesem Zusammenhang sind Partikelsimulationen physikalischer Prozesse (wie z.B. Molekulardynamiksimulationen) und der Einsatz von Optimierern auf der Basis des maschinellen Lernens. Bestehende Ansätze aus diesen beiden Bereichen leiden jedoch oft an schwerwiegenden Einschränkungen in Bezug auf Laufzeit, Speicherverbrauch und Anwendbarkeit. In dieser Arbeit stellen wir neue Ansätze für beide Domänen vor. Sie übertreffen den aktuellen Stand der Technik in Bezug auf Laufzeit und Speicherverbrauch deutlich. Es konnten signifikante Beschleunigungen von bis zu mehreren Größenordnungen im Vergleich zu bestehenden Verfahren erreicht und dabei zugleich den Speicherbedarf deutlich reduziert werden. Hinsichtlich der Anwendbarkeit sind unsere Algorithmen so konzipiert, dass sie sich nahtlos in bestehende Simulationsprogramme und Optimierer integrieren lassen. Dies macht sie damit auch zu einem besonders wertvollen Beitrag für reale Anwendungen aus der Praxis.