We have an array of n elements. At the first stage, we start n / 2 threads and each thread adds two elements, i.e. in one iteration, we add together half of the elements in the array. And then in the loop we repeat all the same for the newly obtained array, until we aggregate the last two elements. As you can see, the smaller the array size, the fewer parallel threads we can run, i.e. it makes sense to aggregate large enough arrays on the GPU. Such an algorithm can be used to calculate the sum of elements (by the way, do not forget about the possible overflow of the data type you are working with), finding the maximum, minimum, or just searching.

But with sorting, everything already looks much more complicated.

The two most popular GPU sorting algorithms are:

Bitonic-sort
Radix-sort

But radix-sort is still used more often, and production-ready implementation can be found in some libraries. I will not go into detail on how these algorithms work, those interested can find a description of radix-sort at the links https://www.codeproject.com/Articles/543451/Parallel-Radix-Sort-on-the-GPU-using-Cplusplus- AMP and https://stackoverflow.com/a/26229897

But the idea is that even a nonlinear algorithm like sorting can be reduced to SIMD form.

And now, before looking at the real numbers that can be obtained from the GPU, let’s figure out how to program for this miracle of technology?