Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #1182

ParallelSort version 3.0

Cross-posted to 2 groups.

Show all headers | View raw

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 — 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