All times are UTC-06:00

 Post new topic  Reply to topic Page 1 of 1 [ 5 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Altivec-optimized Insertion Sort AlgorithmPostPosted: 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
 Post subject: Re: Altivec-optimized Insertion Sort AlgorithmPostPosted: 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
 Post subject: Re: Altivec-optimized Insertion Sort AlgorithmPostPosted: 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
 Post subject: Re: Altivec-optimized Insertion Sort AlgorithmPostPosted: 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: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Post new topic  Reply to topic Page 1 of 1 [ 5 posts ]

 All times are UTC-06:00

#### Who is online

Users browsing this forum: No registered users and 2 guests

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

Search for:
 Jump to:  Select a forum ------------------ Power2People Projects Power Developer    Developers    Users    News    Miscellaneous Hardware Discussions    ARM Architecture    ColdFire Architecture    Power Architecture Linux Distributions    Crux    Debian    Fedora    Gentoo    OpenSUSE    Ubuntu Other Operating Systems    Android    AROS    MorphOS    QNX    Other
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.