bitonic_merge_sort_example

GPU Bitonic Merge Sort Example (Vulkan Compute)

Applies a parallel sorting algorithm to a given buffer of pixel data.

Before	After
Initial image	Image after 55 of 190 steps

The algorithm runs on the GPU via compute shaders. Pixels are sorted by perceptual brightness, via the Oklab colorspace.

The bitonic merge sort algorithm and its implementation are described in much more detail (diagrams! formulas! mini-visualisations!) in the companion blog post to this example.

Note that by default, the algorithm is applied in extreme slow-motion (if let run freely, it could easily sort 1M pixels under 4ms) - this is for visual effect. Accelerate your sort by pressing the CURSOR_DOWN key (for more Keyboard Controls see below).

You can drag and drop image files onto the application window to see their pixels sorted. Image files with a width of 1024px will look best.

Keyboard Controls:

• SPACEBAR: reset pixel buffer to random noise
• CURSOR_UP: increase slow motion delay
• CURSOR_DOWN: decrease slow motion delay (0 delay switches off slow motion and runs optimised algorithm at full speed)
• F11 : toggle app fullscreen

Techniques used:

• Vulkan compute
• visualising raw buffer data via fragment shader
• explicit cpu-side synchronisation
• compute shader: workgroup local memory
• image loading
• implements bitonic merge sort (based on the alternative representation shown on wikipedia

Build instructions

Configure build environment using CMake:

mkdir build 
cd build
cmake -G Ninja ..

Note that if you are using Qt Creator you may skip manually setting up the build environment, and simply open the project CMakeLists.txt using Qt Creator.

Build using Ninja:

ninja

Run application:

./Island-BitonicMergeSortExample