Implementing Bitonic Merge Sort in Vulkan Compute

added on 2021/02/05 @ 14:02:42 | 933 views| category: programming

A bitonic sorting network lays out a sequence of compare-and swap operations that, when applied to an array of sortable elements, sorts these elements. The beauty of this algorithm is that it maps really well onto parallel hardware, such as a GPU, where it has constant and relatively low performance complexity O(log2(n)). That is to say: it's quite fast. The implementation I'm discussing here was able to sort 1M random ints in 4ms. Compared to the 40ms I measured for C++'s std::sort, that's a 10x speedup! On top of that, for a given number of sortable elements, it will always take the same amount of time to complete.

tags: #vulkan #computing #gpu