Numerical solution of the N-body problem on the graphics card

Współczesne karty graficzne poza renderowaniem obrazu mają wiele zastosowań. Przykładem są symulacje zjawisk fizycznych takich jak problem N-ciał. W pracy zaprezentowana jest podstawowa implementacja rozwiązania problemu N-Ciał w języku c++ dla CPU. Implementacja ta jest używana jako wzorcowa do sprawdzenia poprawności wszystkich implementacji w kolejnych rozdziałach. Następnie zostaje opisana platforma testowa, na której będą mierzone czasu działania wszystkich implementacji. Wybranym modelem karty graficznej jest Radeon'a HD 6870, a językiem programowania po stronie GPU jest OpenCL. W głównej części pracy zaimplementowano problem N-ciał dla GPU w języku OpenCL. Implementacja ta jest poddawana modyfikacjom w celu jak najkrótszego czasu wykonania programu na wybranej karcie graficznej. W pierwszej kolejności wyeliminowana jest instrukcja warunkowa "if", która zapobiega dzieleniu przez zero. Następnie minimalizowana jest ilość mnożeń i dzieleń, zastosowane są operacje wektorowe. Zoptymalizowany zostaje odczyt danych wejściowych z pamięci globalnej. W następnym zostają przeprowadzone kolejne próby zoptymalizowania wykorzystania pamięci globalnej poprzez zmianę struktury danych wejściowych.Całość pracy podsumowuje analiza czasów wykonania poszczególnych wersji implementacji oraz porównanie najszybszej z uzyskanych implementacji z implementacją stworzoną przez NVIDIA.Modern graphics cards have many applicatons besides rendering the image. Egzamples are simulations of the physical phenomena such as the n-body problem. The thesis presents basic implementation of the n-body problem in c++ for the CPU. This implementation is used to validate all implementation in the following chapters.Next there is description of the test platform, which is used to measure runtimes of all implementations. The chosen model of graphics card is Radeon'a HD 6870. OpenCL programming language is used to program GPU.In the main part of the thesis there is basic implementation of N-body problem. This implementation is subject to modifications, which purpose is runtime optimization on chosen graphics card. The first optimization is elimination of "if" instruction, which prevents division by zero. Next ones minimize the number of multiplications and divisions and usage of vector operations. Finally reading input data from global memory is optimized. In the following chapter there are further attempts to optimize the usage of global memory by changing the structure of input data. The thesis is concluded by the analysis of the time of execution of the various versions of the implementation and comparison of the fastest implementation with the implementation developed by NVIDIA