All times are UTC-06:00




Post new topic  Reply to topic  [ 5 posts ] 
Author Message
PostPosted: Wed Jul 20, 2005 6:54 am 
Offline

Joined: Wed Oct 13, 2004 7:26 am
Posts: 348
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


Top
   
PostPosted: Thu Jul 21, 2005 3:10 am 
Offline

Joined: Mon Oct 11, 2004 12:49 am
Posts: 35
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.


Top
   
PostPosted: Tue Aug 16, 2005 1:01 am 
Offline
Genesi

Joined: Fri Sep 24, 2004 1:39 am
Posts: 1422
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...:-)


Top
   
PostPosted: Tue Aug 16, 2005 7:46 am 
Offline
Genesi

Joined: Fri Sep 24, 2004 1:39 am
Posts: 1422
<bump>


Top
   
 Post subject:
PostPosted: Wed Jun 13, 2012 6:31 am 
Offline

Joined: Wed Jun 13, 2012 4:42 am
Posts: 1
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


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 5 posts ] 

All times are UTC-06:00


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
PowerDeveloper.org: Copyright © 2004-2012, Genesi USA, Inc. The Power Architecture and Power.org wordmarks and the Power and Power.org logos and related marks are trademarks and service marks licensed by Power.org.
All other names and trademarks used are property of their respective owners. Privacy Policy
Powered by phpBB® Forum Software © phpBB Group