in Programming, Shaders, Tutorial, Unity

GPU Sorting

You can read the full series here:

You can find a link to download the Unity source code at the end of this tutorial.

Introduction

In the previous part of this tutorial, we have discussed the limitations that we face when working in a parallel environment. Conceptually, the same shader code is executed on each pixel of a texture at the same time. While this is not necessarily what happens on a GPU, we cannot rely on the traditional assumptions that we take for granted on sequential machines.

The previous post introduced the odd-even sort, which is one of the simplest sorting algorithms that can be implemented on a GPU. It works by dividing the grouping the pixels on each line of a texture in groups of two. Each one is called a swap couple, and the shader swaps them if they are not already in order. The next step shifts the swap couples, and the process repeats. You can see this in the diagram below:

As discussed before, the complexity of this algorithm is \mathcal{O}\left(n\right), since it takes at most n shader passes to sort an image of n pixels.

Shaders for Simulation

Shaders are usually used to process an input textures. Their result is visualised on the screen, leaving the original textures unaffected. What we want to do here is different, since we need the shader to keep iterating on the same texture. We have discussed how to do this extensive a previous series called How to Use Shaders for Simulations.

The idea behind this is to create two render textures, which are special textures amenable to shader manipulation. The diagram below shows how this process works.

The two render textures are cyclically swapped the shader pass can always use the previous one as the input and the other ones as the ouput.

This tutorial relies on the very implementation presented in How to Use Shaders for Simulations. If you have not read that tutorial yet, fear not. While we will focus on the sorting algorithm only, this is all you need to know:

The fragment function of the shader will contain the sorting code. The variable uv indicates the UV coordinates of the current pixel being drawn, while s represents the size of a pixel in UV space.

⭐ Suggested Unity Assets ⭐
Unity is free, but you can upgrade to Unity Pro or Unity Plus subscriptions plans to get more functionality and training resources to power up your projects.

Re-ordering the Swap Couple

In the previous part, we have introduced the concept swap couple. Pixels are grouped in couples, which are then sorted in a single shader pass. Let’s imagine having two nearby pixels, which colours x and y represents two numbers. The shader pass has to sample these two pixels and reorder them accordingly.

To do so, the pixel on the left side of the swap couple will sample the two pixels above, and pick min\left(x,y\right) as its final colour. The pixel on the right will do the opposite:

The position of the pixel does not only determine which operation to do. It also determines which pixels to sample. Min pixels need to sample the pixels at their current position and the one to their right. Max pixels need to sample the pixel on their left instead.

On top of that, the min and max pixels are swapped after each iteration. The diagram below shows which pixels perform a min operation (blue) and which one performs a max operation (red):

The two determinant factors in deciding which operation to perform are the iteration number _Iteration and the element index x  (or y, if we are sorting columns instead of rows).

By looking at the diagram above, we can derive the final condition that determines whether we have to perform a min or max operation:

That condition makes sure that during even iterations (the second, the fourth, …) pixels in an even position perform a max operation, and pixels in an odd position perform a min operation. On odd iterations (the first, the third, …) this is swapped.

For this effect to work, both render textures must be set to Clamp, as the shader code does not have any boundary conditions to prevent accessing pixels outside the texure.

Conclusion

You can find more sorting animations in this gallery:

GPU Sorting – Alan Zucconi

You can read the full series here:

Download

Become a Patron!
You can download all the assets necessary to reproduce a GPU sorting shader. There are two downloads available:

Feature Standard Premium
GPU Sorting Shader
In Place Sorting Support
Sorting by Hue
Sorting by Red Channel
Sorting by Luminosity
Export as a GIF
Download Standard Premium
💖 Support this blog

This websites exists thanks to the contribution of patrons on Patreon. If you think these posts have either helped or inspired you, please consider supporting this blog.

Twitter_logo

YouTube_logo
📧 Stay updated

You will be notified when a new tutorial is relesed!

📝 Licensing

You are free to use, adapt and build upon this tutorial for your own projects (even commercially) as long as you credit me.

You are not allowed to redistribute the content of this tutorial on other platforms. Especially the parts that are only available on Patreon.

If the knowledge you have gained had a significant impact on your project, a mention in the credit would be very appreciated. ❤️🧔🏻

Write a Comment

Comment

  1. Great article Alan! One thing I don’t understand:
    in these lines
    if ( ( EVEN(_Iteration) && EVEN(x) ) ||
    ( ODD (_Iteration) && ODD (x) )
    )
    the if statement is always true right? Because it will always be an odd or an even number. So the else statement will never be executed. Am I wrong with my reasoning?

    • Hi Federico!

      If the statement were “EVEN(x) || ODD (X)” yes, you’d be right.
      But the condition is slightly different.
      It checks is “_Iteration” and “x” are both either EVEN or ODD.
      So it’s like: (BOTH EVEN || BOTH ODD).

      I hope this makes sense!

  2. Trying to implement this with opengl compute shaders on a 2d list of ints, it works great up until the list of ints hits a certain limit(around 2560) when the sorting stops fully sorting the ints every frame, my condition for calling another swap is while (sFlags[0]|| streak < 2), sFlags[0] is the gpu's way of telling the cpu whether any swaps happened, and streak is ensuring that the gpu had to do no swaps twice in a row(shifted swap and unshifted swap). I feel like the loop condition for doing more parallel swaps should work to ensure the list is sorted every frame but as you can see in this video https://youtu.be/cANG6Yxjy1A (sorting based off height, color representative) the sorting allows many frames to pass before it is completely sorted, what can i do to fix this, it seems like my while condition is good as it is. thx for this article -ben

Webmentions

  • GPU Sorting - Alan Zucconi January 12, 2020

    glFinish() is what i needed to ensure all computing is done before another swap call is made etc… sorry to make a mess of your comments