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

Groups > comp.programming.threads > #1207

Re: About my ParallelSort library

Cross-posted to 2 groups.

Show all headers | View raw

I wrote:
>I have done some tests with my ParallelSort library and
>i have noticed that it can give up to 3.8x scalability with
>strings, and it give  3x scalability with integers..


Why it scale to 3.8x with strings and only 3x with integers...


I will explain:


In the SequentialMerge() method QSort() method inside Parallel Sort library, 
i am calling the Scompare() method and also in both of them i am copying to 
the memory system.


So when i am using strings the Scompare() method is more
expensive, so the parallel part p in the Amdahl equation
1/ S + P/N (S: the serial part, P: parallel part and N: the number
of cores) is bigger than with integers so the Amadahl equation will scale 
better,
but when we are using integers the Scompare() method is
less expensive than the SCompare() with strings, so the parallel part p in 
the Amdahl equation is less bigger than with strings. so this is why 
parallel sorting with strings scales better than with integers.


Thank you,
Amine Moulay Ramdane.

"aminer" <aminer@toto.com> wrote in message 
news:k6sbo2$anb$2@dont-email.me...
>
> Hello all,
>
> I have done some tests with my ParallelSort library and
> i have noticed that it can give up to 3.8x scalability with
> strings, and it give  3x scalability with integers..
>
> The complexity of ParallelSort using mergesort for exemple, is:
>
> ((n/p)* log(n/p)) + O(n/p)
>
>
> And as you know:
>
> If f1 is O(g1) and f2 is O(g2),
> then f1 + f2 is O(max (f1, f2)), where
> max (f1, f2) (x) = max (f1 (x), f2 (x)); for every  x
>
> So the complexity of my Parallel Sort library using mergesort
> is:
>
> (n/p)* log(n/p))  // p is the number of cores.
>
>
> Also i have implemented Parallel MergeSort and Parallel Quicksort,
> but MergeSort is faster and the reccurence equation of the complexity of 
> mergesort is:
>
> T(n) = 2 * T(n/2) + n
>
> cause it take O(n) for the merging part.
>
> It gives:
>
> T(n) = 2 * T(n/2) + n
>
> = 2 (2T(n/4) +n/2) + n
>
> =4T(n/4)+n+n
>
> =4T(n/4)+2*n
>
> =4 (2T(n/8) +n/4) + 2*n
>
> =8T(n/8)+n+2n
>
> =8T(n/8)+3*n
>
> =2k T(n/2^k) + k*n
>
> We want:
>
> n/2k = 1
>
> n = 2k
>
> log n = k
>
> so the reccurence equation gives:
>
> = nT(1) +n*log(n)
>
> = n+ (n * log(n))
>
> So the mergesort complexity in the best case and in the worst case is:
>
> n * log(n)
>
> But the complexity of the quicksort in the worst case is:
>
> T(n)= n + T(n-1)
>
> it gives:
>
> T(n) = n + (n-1) + T(n-2)
>
> T(n) = n + (n-1) + (n-2)+ T(n-3)
>
> T(n) = 1 + 2+ 3+.+N
>
> T(n) = O(n^2)  // n power of 2
>
>
> You can download Parallel Sort 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

About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 19:21 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 19:50 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 20:40 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 20:48 -0500
  Re: About my ParallelSort library "aminer" <aminer@toto.com> - 2012-10-31 21:08 -0500

csiph-web