THE RESEARCH OF POSSIBILITIES OF ACCELERATION OF PARALLEL ALGORITHMS FOR RADIX SORTING ON GPGPU

UDC 004.424.5.032.24

G. V. Vorontsov, A. P. Preobrazhenskiy, O. N. Choporov


This paper analyzes parallel RADIX sorting on GPGPU. First, they consider the naive algorithm of radix sorting. It is indicated that using two types of radix sorting – at Junior and senior level. Given an example of their use. In order to increase the performance of the radix sorting algorithm is proposed to use a parallel solution, although this raises additional issues that require resolution. Analyzes possible approaches for the parallelization proposed by various authors. In the proposed algorithm the data is stored in GPU memory, and sorting is performed directly on the GPU. This algorithm is a parallel Radix sort consists of 3 subsystems: counting binary combinations in the current category, prefix summing, the final key according to the computed positions. The first step of the algorithm is the process of counting the frequency of each element in the sequence. To have it done in a parallel way there is a separation of the input array into blocks. It then computes the local frequency of all possible elements for each block. Next, for each mask is the prefix summation. The next step is to obtain from the local lists of the frequency of the global. Simulation results demonstrated the increase of several times the performance of the proposed algorithm in comparison with the known.

Keywords: : parallel sorting, algorithm, data, processor.

Full text:
VoronzovSoavtori_1_1_18.pdf