3 ms·
Yes, I think most GPU sorting is based on sorting networks as there are no data dependent branches (I mean, if you exclude the exchange)
by justincormack 5y ago
Yes, I think most GPU sorting is based on sorting networks as there are no data dependent branches (I mean, if you exclude the exchange)
- dragontamer 5y agoOnly within a CUDA block / OpenCL workgroup of ~1024 items maximum. Beyond 1024 "threads", its difficult and inefficient for communication to take place. ------------- GPU Mergepath seems like the coolest algorithm for sorting more than 1024 elements in 1024-way parallel. In practice, I think only the 32-way or 64-way optimal sorting network was calculated, and then its all merge-path beyond that. (Merge 64 + 64 sorted lists == 128 sorted list) Mergepath is a very efficient means of parallelizing the "Merge" step of mergesort's algorithm. There's a little branch divergence: but even with the branch divergence you're at O(n + p*log(n)) overall work per merge (assuming constant "p", number of processors, where p is much smaller than "n"... its effectively a O(n) algorithm and therefore asymptotically work efficient with original O(n) mergesort. Parallel Bitonic sort fails in this test) IIRC, CUDA Thrust's Mergepath algorithm is designed to scale beyond one SM (so it can compute in parallel larger than 1024 elements), because the Mergepath algorithm has very little communication that gets the job done. In contrast, an optimal sorting network of large size (ex: size 1-million) would require arbitrary communication between elements, which is just not how modern computers / GPUs work.
- touisteur 5y agoPlease if you know where to find the optimal 64-way sorting network) or even better, selecting network, I'm yugely interested.
- dragontamer 5y agoSeems like it's just a bitonic network sort over 32 or 64 elements at the bottom. So not optimal. I guess I was mistaken.
- touisteur 5y agoOh :-) thanks anyway