Shuffling and Sorting, Part 2

>> Sunday, October 23, 2011

My first post on this blog dealt with using OpenCL vector functions to sort data. Thanks to the as_type function, I've improved my original code. If input is a vector containing four floats, the following code will sort its components in place:

uint4 mask1 = (uint4)(1, 0, 3, 2);
uint4 mask2 = (uint4)(2, 3, 0, 1);
uint4 mask3 = (uint4)(3, 2, 1, 0);

int4 add1 = (int4)(1, 1, 3, 3);
int4 add2 = (int4)(2, 3, 2, 3);
int4 add3 = (int4)(1, 2, 2, 3);

int4 comp = input < shuffle(input, mask1);
input = shuffle(input, as_uint4(comp + add1));
comp = input < shuffle(input, mask2);
input = shuffle(input, as_uint4(comp * 2 + add2));
comp = input < shuffle(input, mask3);
input = shuffle(input, as_uint4(comp + add3));
This may look like a lot of work to sort four values, but there are no if statements in this code. Therefore, unless the shuffle function is implemented with branches, there are no delays associated with branch misses.

The sorting direction can be controlled with the bitwise exclusive-OR. For example, if dir is set to -1, the following code will sort the elements in descending order:
int4 comp = input < shuffle(input, mask1) ^ dir;
input = shuffle(input, as_uint4(comp + add1));
comp = input < shuffle(input, mask2) ^ dir;
input = shuffle(input, as_uint4(comp * 2 + add2));
comp = input < shuffle(input, mask3) ^ dir;
input = shuffle(input, as_uint4(comp + add3));
If dir is set to 0, the code will sort the input elements in ascending order.

1 comments:

Lee Shin June 14, 2013 at 1:25 AM  

spot on with this write-up, i like the way you discuss the things. i'm impressed, i must say. i'll probably be back again to read more. thanks for sharing this with us.

Lee Shin
www.trendone.net

Post a Comment

  © Blogger template Werd by Ourblogtemplates.com 2009

Back to TOP