Well, I don't have much battery left where I am so I'll just post the links, I describe everything in the paper anyway (hint: up to 50x faster!!!):

Altivec Insertion Sort/Merge Sort Algorithm Paper:

http://people.debian.org/~markos/powerpc/vectorsort.pdf

Code:

http://people.debian.org/~markos/powerpc/vectorsort.c

My Altivec presentation in DebConf5:

http://people.debian.org/~markos/powerpc/Altivec.sxi

PS. I am in the process of altivec-optimizing Quicksort as well!!

Regards

Konstantinos

Nice! And well documented, which is the key to spreading the knowledge.

I always thought it might be fruitful to start with sorting algorithms that have inherent data parallelism. Shellsort for instance, although I don't know if that would keep its order of complexity if you changed the strides to better match vector length.

Another very interesting algorithm is called "Batcher's Method" in Knuth's famous book (The Art of Computer Programming, Sorting and Searching). It has a particularly simple structure when input size is a power of two. Maybe it is possible to virtually pad an input array to such a size (using the maximal value for that data type) without ever actually storing those filler elements in memory. It might be possible to simply terminate all loops early, with special case handling for the final vector (or final vectors?).

Both of the above sorts are based on "compare and exchange" operations that do not depend on input data. One vec_min and one vec_max can accomplish such an operation for all elements of a vector in parallel. Memory access patterns are fairly linear, but both algorithms do several passes over the whole array, so bandwidth will become a problem with large data sets. Order of complexity is also worse than the usual O(N log N), but these algorithms might still win due to their simplicity. They could make a building block for an industrial strength sort which first subdivides a large data set into cache-friendly blocks, and then sorts each block quickly with a special purpose sort.

markos, anything new on this? It seems you have done some great things since EuroSNDF and PegasosPPC Day!

http://www.ppcnux.de/modules.php?name=N ... 4208#part2

Thanks Hobold for checking in and contributing what are always interesting posts.

R&B

P.S. Just noticed there are pictures of both of you at PegasosPPC Day...

<bump>

hello markos!
I have seen that you tried to write the quicksort algorithm using altivec instructions...did you do it in the end?please can you send me the pdf and the code on the email chill_muesta@yahoo.com or if you can upload it somewhere because here it is not anymore...thank you very much