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 verical 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));
   }
}

Let’s look into more detail here. The x parameter represents the column number. The step is defined by the time. We will accelerate the time by a factor of 20. You shouldn’t put this number higher than the FPS otherwise you end up skipping steps. In the if expression we do a XOR to select our neighbour. Each column will pull the previous value from the selected neighbour if necessary. The odd function is:

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s