Writing a Parallel Sort in a Shader

Most of the shaders on glslsandbox.com are stateless. They define a function from the screen coordinates and time to a colour. This is a very neat paradigm because it forces you to write fast parallel algorithms, but sometimes it can be quite restrictive. We will examine how to write a less trivial algorithm using a shader: a parallel sort.

In order to simulate state we will use a backbuffer:

uniform sampler2D bb;

This sampler allows us to access the image that was generated in the previous frame. Now we can write a shader that is a kind of a recursive function. In GPGPU terms this is called a gather operation.

First we must generate some random values to sort. And we will use the red component of the bottom row to hold these values. To do this we need to define a function that returns values from 0 to 1:

float hash(float x) {
   return fract(sin(dot(vec2(x,x) ,vec2(12.9898,78.233))) * 43758.5453);
}

If the pixel that we are rendering is in row 0 we will set the red component to be our generated value. For the time being all other rows will be black. At this point our shader should look like this:

precision mediump float;
uniform float time;
uniform vec2 mouse;
uniform vec2 resolution;
uniform sampler2D bb;

float hash(float x) {
   return fract(sin(dot(vec2(x,x) ,vec2(12.9898,78.233))) * 43758.5453);
}

void main( void ) {
   float n = hash(gl_FragCoord.x + time);
   gl_FragColor = vec4(vec3(0), 1.0 );
   // save value as pixel red intensity
   if (int(gl_FragCoord.y) == 0) {
      gl_FragColor.r = n;
   }
}

You should see a black screen with the last row filled with flickering red dots.

At the moment our shader is constantly generating sets of random numbers, but we want to define a way of saying that we’re happy with the values and that we want to start sorting them. We will use the position of the mouse to do this. If the mouse is on the left side of the screen we keep on generating random numbers, otherwise we use the value from the previous frame.

float x = floor(gl_FragCoord.x);
float n = (mouse.x < .5) ? hash(x+time) : prev(x);

Of course we need to define the function to get the previous value. We will use the OpenGL texture2D to access our sampler. In particular we want the red component of the pixel at column x, row 0.

float prev(float x) {
   return texture2D(bb, vec2((x+.5)/resolution.x, 0.0)).r;
}

Finally let’s use all the other rows that are currently black for displaying vertical lines that represents the numbers stored in row 0. Now, our shader should look like this:

precision mediump float;
uniform float time;
uniform vec2 mouse;
uniform vec2 resolution;
uniform sampler2D bb;

float hash(float x) {
   return fract(sin(dot(vec2(x,x) ,vec2(12.9898,78.233))) * 43758.5453);
}

// the previous value at column x
float prev(float x) {
   return texture2D(bb, vec2((x+.5)/resolution.x, 0.0)).r;
}

vec4 line(float n) {
   vec2 position = ( gl_FragCoord.xy / resolution.xy );
   return vec4(vec3((n - position.y)*100.0), 1);
}

void main( void ) {
   float x = floor(gl_FragCoord.x);
   float n = (mouse.x < .5) ? hash(x+time) : prev(x);
   gl_FragColor = line(n);
   // save value as pixel red intensity
   if (int(gl_FragCoord.y) == 0) {
      gl_FragColor.r = n;
   }
}

Now we finally have the basis for defining our sort algorithm. We will implement the parallel bubblesort. In this algorithm every column will check the values of its neighbours and if needed swap the values. The algorithm is performed in alternate steps. On odd steps, the odd columns will check the neighbour to the left and the even columns will check the neighbour to the right. On even steps they will do the inverse.

float sort(float x) {
   if (odd(x) ^^ odd(time*20.)) {
      return min(prev(x), prev(x+1.0));
   } else {
      return max(prev(x-1.0), prev(x));
   }
}

bool odd(float x) {
   return (mod(x, 2.0) < 1.0);
}

At this point our shader should look like this:

precision mediump float;
uniform float time;
uniform vec2 mouse;
uniform vec2 resolution;
uniform sampler2D bb;

float hash(float x) {
   return fract(sin(dot(vec2(x,x) ,vec2(12.9898,78.233))) * 43758.5453);
}

// the previous value at column x
float prev(float x) {
   return texture2D(bb, vec2((x+.5)/resolution.x, 0.0)).r;
}

vec4 line(float n) {
   vec2 position = ( gl_FragCoord.xy / resolution.xy );
   return vec4(vec3((n - position.y)*100.0), 1);
}

bool odd(float x) {
   return (mod(x, 2.0) < 1.0);
}

float sort(float x) {
   if (odd(x) ^^ odd(time*20.)) {
      return min(prev(x), prev(x+1.0));
   } else {
      return max(prev(x-1.0), prev(x));
   }
}

void main( void ) {
   float x = floor(gl_FragCoord.x);
   float n = (mouse.x < .5) ? hash(x+time) : sort(x);
   gl_FragColor = line(n);
   // save value as pixel red intensity
   if (int(gl_FragCoord.y) == 0) {
      gl_FragColor.r = n;
   }
}

As an exercise you can fork this shader and try to implement a Bitonic Sort.