Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.programming.threads > #1183

Re: ParallelSort version 3.0

Cross-posted to 2 groups.

Show all headers | View raw

Hello,


For exemple i have added the following in ParallelSort library:


The idea:

Let's assume we want to merge sorted arrays X and Y. Select X[m]
median element in X. Elements in X[ .. m-1] are less than or equal to
X[m]. Using binary search find index k of the first element in Y greater
than X[m]. Thus Y[ .. k-1] are less than or equal to X[m] as well.
Elements in X[m+1..] are greater than or equal to X[m] and Y[k .. ]
are greater. So merge(X, Y) can be defined as
concat(merge(X[ .. m-1], Y[ .. k-1]), X[m], merge(X[m+1.. ], Y[k .. ]))
now we can recursively in parallel do merge(X[ .. m-1], Y[ .. k-1]) and
merge(X[m+1 .. ], Y[k .. ]) and then concat results.


I have implemented a Parallel hybrid divide-and-conquer
merge algorithm that performs 0.9-5.8 times better than sequential merge, on
a quad-core processor, with larger arrays outperforming by over 5 times.
Parallel processing combined with a hybrid algorithm approach provides a
powerful high performance result.


And now ParallelSort library gives better performance and scalability.


Please look at the source code to understand more...

You can download ParallelSort library from:

http://pages.videotron.com/aminer/



Thank you,
Amine Moulay Ramdane.



"aminer" <aminer@toto.com> wrote in message 
news:k68sg9$c66$1@dont-email.me...
> Hello,
>
> Parallel Sort Library was updated to version 3.0.
>
> In this new version i have implemented a Parallel hybrid 
> divide-and-conquer merge algorithm that performs 0.9-5.8 times better than 
> sequential merge, on a quad-core processor, with larger arrays 
> outperforming by over 5 times. Parallel processing combined with a hybrid 
> algorithm approach provides a powerful high performance result.
>
>
> Description:
>
> Parallel Sort Library that supports Parallel Quicksort, Parallel HeapSort 
> and Parallel MergeSort on Multicores systems.
>
> Parallel Sort Library uses my Thread Pool Engine and quicksort many array 
> parts - of your array -  in parallel using Quicksort or HeapSort or 
> MergeSort and after that it finally merge them - with the merge() 
> procedure -
>
> In the previous parallelsort version i have parallelized only the sort 
> part, but in this new parallelsort version i have parallelized also the 
> merge procedure part and it gives better performance.
>
> I have implemented a Parallel hybrid divide-and-conquer merge algorithm 
> that performs 0.9-5.8 times better than sequential merge, on a quad-core 
> processor, with larger arrays outperforming by over 5 times. Parallel 
> processing combined with a hybrid algorithm approach provides a powerful 
> high performance result.
>
> And as you know , Quicksort is a divide and conquer algorithm that have 
> the following best case performance:
>
> T(n) = T(n/2) + T(n/2) + O(n)
>       = 2T(n/2) + (n)
>
> And from case 2 of Master theorem, the recurrence equation gives:
>
>        T(n) = (n lg n)
>
>
> Parallelizing the Sorts
>
> One way to parallelize the sorts is:
>
>    Divide the data among the processors
>    Sort the data on the individual processors.
>    Merge the various data
>
> Note that the merge operation is a reduction operation !
>
>
> And please look at test.pas inside the zip, a parallel quicksort on many 
> cores, you have to compile and run gendata.pas  before running test.pas, 
> and please set the number of threads to  8 times the number of cores to be 
> more optimal, i have giving you an exemple on how to do it , look inside 
> test.pas...
>
> You can download ParallelSort library from:
>
> http://pages.videotron.com/aminer/
>
>
>
> Thank you,
> Amine Moulay Ramdane.
>
>
> 

Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

ParallelSort version 3.0 "aminer" <aminer@toto.com> - 2012-10-24 10:07 -0500
  Re: ParallelSort version 3.0 "aminer" <aminer@toto.com> - 2012-10-24 10:49 -0500
  Re: ParallelSort version 3.0 "aminer" <aminer@toto.com> - 2012-10-24 10:57 -0500
  Re: ParallelSort version 3.0 "aminer" <aminer@toto.com> - 2012-10-24 11:25 -0500

csiph-web