Optimierung von Life Sciences Algorithmen für GPUs mit CUDA/OpenCL

Ein Forschungsschwerpunkt in Scientific Computing beschäftigt sich mit der Parallelisierung von Algorithmen für GPUs, da die theoretische maximale Leistung von GPUs ein Vielfaches größer ist als von CPUs. In der Masterarbeit wird zunächst auf die Nvidia-Fermi-GPU-Architektur und auf die Änderungen gegenüber der Vorgängerarchitektur GT200 näher eingegangen. Im nächsten Schritt werden die GPU-Programmiersprachen CUDA und OpenCL erklärt und die Unterschiede in der Programmierung gegenübergestellt. Das Ziel der Masterarbeit ist die Optimierung von zwei Life-Science-Algorithmen (Needleman-Wunsch/Smith-Waterman und Direct Coulomb Summation) für die Ausführung auf Grafikkarten (Nvidia-Fermi und Nvidia-GT200) bei Verwendung der Programmiersprachen CUDA und OpenCL. Der DCS-Algorithmus ist für Grafikkarten deutlich besser als der NW/SW-Algorithmus geeignet, da der Parallelisierungsgrad wesentlich größer ist. In der Masterarbeit wird ermittelt, wie wirksam einzelne Optimierungstechniken bei unterschiedlichen GPU-Architekturen (Fermi und GT200) und bei unterschiedlichen GPU-Programmiersprachen (CUDA und OpenCL) sind. Dabei wird überprüft, ob Optimierungstechniken, wie Memory Coalescing und Verwendung der kleinen on-chip-Speicher, durch die mit der Fermi-Architektur eingeführte Cache-Hierarchie über den Global Memory nicht mehr notwendig sind und dadurch eine einfachere Überführung von CPU-Code in GPU-Code ohne Einbußen bei der Performance möglich ist. Ebenfalls ein wichtiges Thema der Masterarbeit ist der faire Vergleich des GPU-Programms mit dem CPU-Programm beim Beantworten der Frage, ob bei beiden Algorithmen auf der GPU ein Speedup gegenüber der CPU erreicht werden kann. Für einen fairen Vergleich werden unter anderem bei der CPU mit der Programmiersprache OpenMP alle Kerne verwendet. In der Masterarbeit wird auch auf die limitierenden Faktoren eingegangen, die dazu führen, dass der Algorithmus nicht die Peak-Leistung der GPU erreicht.A research focus in scientific computing deals with the parallelisation of algorithms for GPUs because the theoretical maximum performance of GPUs is many times higher than of CPUs. The master thesis starts with the Nvidia Fermi GPU architecture and the changes compared to the predecessor architecture GT200. In the next step the GPU programming languages CUDA and OpenCL are explained and the differences in programming are compared. The aim of the master thesis is the optimization of two life science algorithms (Needleman-Wunsch/Smith-Waterman, Direct Coulomb Summation) for the execution on graphics cards (Nvidia-Fermi, Nvidia-GT200) by using the programming languages CUDA and OpenCL. The DCS algorithm is much more suitable for graphics cards than the NW/SW algorithm because the degree of parallelisation is significantly higher. In this master thesis, it is determined how effective the optimization techniques are on different GPU architectures (Fermi, GT200) and on different GPU programming languages (CUDA, OpenCL). In doing so, it is checked whether the new cache hierarchy for the global memory in the Fermi architecture replaces optimization techniques (memory coalescing, use of the small on chip memories) and therefore makes an easier transfer from CPU code to GPU code without losing performance possible. Another important issue of the master thesis is the fair comparison between GPU program and CPU program when answering the question whether the two algorithms can reach a speedup on the GPU in comparison with the CPU. For a fair comparison all cores on the CPU are used with the programming language OpenMP