This article introduces the concept of parallel sorting, discussing the theory and implementation of a shader that can sort pixels.
You can read the full series here:
You can find a link to download the Unity source code at the end of this tutorial.
If you did not study Computer Science in the 80s or 90s, chances are you will struggle to understand the excitement some developers have for sorting algorithms. What could seem at first like a minor task, turns out to be a cornerstone of Computer Science.
But first of all, what are sorting algorithm? Imagine that you have a list of numbers. A sorting algorithm is a program that takes that same list and reorders its numbers. Sorting algorithms are often introduced during the study of Computational Complexity, another vast subject that will be covered extensively in a future series. There are countless ways in which a list of items can be sorted, and each strategy offers a unique trade-off between cost and performance.
Most of the complexity of sorting algorithms comes from the way the problem is defined and approached. In order to decide how to rearrange the elements, an algorithm must compare numbers. In the scientific literature, each comparison performed adds up to the complexity of the algorithm. The number of comparisons one performs is the way complexity is measured.
However, things are not that easy: the number of comparisons and swaps depend on the list itself. This is why in the field of Computational Complexity there are more objective ways to measure the performance of an algorithm. What is the worst possible scenario for an algorithm? How many steps will it take, at most, to sort the most un-sorted list it can work with? Such a way to approach the problem is known, unsurprisingly, as worst-case scenario analysis. We can ask the same question for the best-case scenario. What is the minimum amount of comparisons that an algorithm has to perform to sort an array? Loosely speaking, the latter is often with the Big O notation, which measures complexity as a function of the number of elements to sort, . It has been proved that under this framework, no algorithm can perform better than . This means that it cannot exist an algorithm that always sorts every input array of length by making less than comparisons.❓ This is not what O(n log n) means!
You can imagine the Big O notation as a way to express the “order of magnitude” of a function. So with elements to sort doesn’t really mean comparisons. It could be 10, or even 100 times that. What matters for the purpose of a superficial understanding is that that the number of comparisons necessary to sort an array grows proportional to .
A future series will focus on the subject of Computational Complexity, from a purely Mathematical point of view.
The Limitations of the GPU
Traditional sorting algorithms are built based on two simple concepts:
- Comparison: the act of comparing two elements of a list, in order to decide which one is larger;
- Swaps: the act of swapping the position of two elements, in order to bring the list in a new state that is closer to the desired one.
The list to be sorted is often given in the form of an array. Accessing random elements of an array is extremely efficient, and it is possible to swap any two elements with no restrictions.
If we want to use a shader to sort, we first need to understand the intrinsic limitations of this new medium. While it is possible to provide a list of number to a shader, that is not the best way to exploits its parallelism. Conceptually, we can imagine the GPU executing the same shader code on each pixel, at the same time. This is not generally what happens, since a GPU is unlikely to have the computational power to parallelize the computation for each pixel. Some parts of the image will be processed in parallel, but we shouldn’t make any assumptions on which ones. For this reason, the shader code has to operate under the same constraints of true parallelism, even if in reality that is not necessarily how it runs.
The most serious constraint, however, is the fact that the shader code is localised. If the GPU is executing a piece of code on a pixel at coordinate we cannot write to any other pixel but . On a shader, the swap operation requires the synchronisation of both pixels.
Sorting on a GPU
The approach presented in this tutorial is conceptually simple.
- The data to sort is provided in a texture;
- If we have an array of elements, we create a texture of size pixels;
- The value in the red channel of each pixel contains the number to sort;
- Each rendering pass will bring the array closer to its final state.
For example, let’s imagine we have a list of fours numbers to sort: . We can feed it to a shader by creating a texture of pixels, storing the values in the red channel (below):
As discussed before, the swap operation is much more complex when done in a shader, since it needs to be executed in parallel by two independent pixels. The easiest way to work with such a limitation is to swap nearby couples of pixels (below):
It’s important to notice that, conversely to what happens on a CPU, the process happens somehow in reverse. The first pixel samples its previous value, and the one on its right, . Since it is the on the left-side of the swap couple, it needs to take the smaller one. The second pixel in the couple needs to perform the opposite operation.
Since those calculations are done independently, both pieces of code should agree on which value to propagate down without any communication. This is where the challenge of parallel sorting lies. If we are not careful, both pixels in the swap couple could pick the same number, de-facto duplicating it.
If we repeat this swapping process, nothing would change. Each couple can be sorted in a single step. Replicating this process will not lead to any changes. The way to overcome this, is to change the swapping couples. We can see this in the diagram below:
❓ What about the pixels on the edge?
The first approach is to consider these two pixels as part of a single swap couple. While this works, it requires to write additional conditions that in the shader code that are inevitably going to impact the performance.
A simpler solution is to simply clamp the texture. The two extreme pixels will perform swaps between themselves (below):
We can keep alternating these two steps, until the entire image is sorted:
Such a technique has been around for quite a long time, and it exists in many different flavours and variations. It is often referred to as odd-even sort, since it alternates swaps between odd/even and even/odd indices. It’s working mechanism is deeply connected with the bubble sort, so it is not surprising to find this algorithm under the name of parallel bubble sort.
When working on a GPU, we should assume that the same shader code is executed on each pixel independently, and at the same time. In a traditional CPU, we should consider each comparison/swap as an individual operation. A shader pass would count as operations. Under the assumption that we can compute all of them in parallel, the time to execute one or to execute is the same. As a result, the parallel complexity of each shader pass is .
What is the complexity in the worst case scenario? We can see that each step brings a pixel closer to its final position. The further a pixel can travel is , so we need at most steps to sort the list.
If we look at this problem from a more traditional perspective, things are very different. Each shader pass analyses each pixel at least once, which means adding complexity . When coupled with the number of passes , it brings the complexity to . This shows how inefficient the odd-even sort really is when executed sequentially.
The next post will focus on the implementation details of this algorithm. We will see how to recreate it in Unity, using a vertex and fragment shader.
You can read the full series here:
You can download all the assets necessary to reproduce a GPU sorting shader. There are two downloads available:
|GPU Sorting Shader||✅||✅|
|In Place Sorting Support||❌||✅|
|Sorting by Hue||❌||✅|
|Sorting by Red Channel||❌||✅|
|Sorting by Luminosity||❌||✅|
|Export as a GIF||❌||✅|