Groups > comp.programming.threads > #1182

ParallelSort version 3.0

Path	csiph.com!usenet.pasdenom.info!news.albasani.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From	"aminer" <aminer@toto.com>
Newsgroups	comp.programming.threads, comp.programming
Subject	ParallelSort version 3.0
Date	Wed, 24 Oct 2012 10:07:46 -0500
Organization	A noiseless patient Spider
Lines	70
Message-ID	<k68sg9$c66$1@dont-email.me> (permalink)
Injection-Date	Wed, 24 Oct 2012 14:03:53 +0000 (UTC)
Injection-Info	mx04.eternal-september.org; posting-host="c43ca82f9e8d62a602307fe9d2e9b807"; logging-data="12486"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+irl4yZJWDUnjdxNklcgZ4"
X-MimeOLE	Produced By Microsoft MimeOLE V6.00.2900.6157
X-RFC2646	Format=Flowed; Original
X-Newsreader	Microsoft Outlook Express 6.00.2900.5931
Cancel-Lock	sha1:XTZZFUPovbR8Uoq2RY7anEkp68w=
X-Priority	3
X-MSMail-Priority	Normal
Xref	csiph.com comp.programming.threads:1182 comp.programming:2381

Cross-posted to 2 groups.

Show key headers only | 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