Radix sort for massively parallel hardware: a multi-GPU implementation

  • Computers, servers and supercomputers with more than one GPU become more and more common. To fully utilize such systems the application needs to be aware of the additional GPUs. E.g., computational workload needs to be distributed across the GPUs. Along with that goes data movement as well as communication. Recently, NVIDIA introduced new features, Unified Memory and Cooperative Groups, that enable programmers to extend their applications with multi-GPU capabilities. In this thesis the aforementioned features are presented in detail and evaluated in the context of the GPU molecular dynamics simulation HAL's MD package on the latest NVIDIA GPU architecture Pascal. A hotspot analysis with the NVIDIA Visual Profiler identified the radix sort as a major hotspot within HAL's MD package. This thesis presents an approach towards a multi-GPU implementation of radix sort. The individual kernels are analysed and an implementation is discussed. Then, the radix sort is transformed into a multi-GPU implementation kernel per kernel. For each step the individual runtime measurements and bottlenecks are presented to analyse the approach. A general sequence diagram of the implementation shows how the individual parts interact with each other. The outlook discusses the further development of HAL's MD package, especially the force computation for multi-GPU which has not been covered in this thesis.
  • Computer, Server und Supercomputer mit mehr als einer GPU sind immer häufiger zu finden. Um solche Systeme komplett ausnutzen zu können, müssen Anwendung für die Verwendung mehrerer GPUs angepasst werden. Z.B. müssen die Berechnungen zwischen den GPUs verteilt werden. Damit einher gehen die Kommunikation zwischen den GPUs sowie der Austausch der Daten. Mit Unified Memory und Cooperative Groups hat NVIDIA zwei neue Funktionen vorgestellt, damit Programmierer ihre Anwendungen einfach an Multi-GPU Systeme anpassen können. Im Rahmen dieser Arbeit werden die oben genannten Funktionen im Detail vorgestellt und anhand der Molekulardynamiksimulation HAL's MD package auf der neuesten NVIDIA GPU Architektur Pascal evaluiert. Eine Hotspot Analyse von HAL's MD package mit dem NVIDIA Visual Profiler hat den Radix Sort als einen großen Hotspot identifiziert. Daher stellt diese Arbeit eine Multi-GPU Implementierung für Radix Sort vor. Dabei werden die einzelnen Kernel Schritt für Schritt vorgestellt und ihre Implementierung, insbesondere Laufzeiten und Probleme bei der Umsetzung, im Detail diskutiert. Ein Sequenzdiagramm der einzelnen Teile von Radix Sort zeigt dabei, wie die einzelnen Teile in der Multi-GPU Implementierung zusammenarbeiten. Abschließend wird, ausgehend von den Ergebnissen, die zukünftige Entwicklung von HAL's MD package unter besonderen Berücksichtigung einer vollständigen Multi-GPU Molekulardynamiksimulation betrachtet.
Metadaten
Author:Alexander Kammeyer
Document Type:Master's Thesis
Granting Institution:Freie Universität Berlin
Advisor:Thomas Steinke, Katinka Wolter, Felix Höfling
Date of final exam:2018/05/30
Year of first publication:2018
Pagenumber:67