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

Groups > comp.programming > #2427 > unrolled thread

About my ParallelSort library

Back to article view | Back to comp.programming

Contents

  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

#2427 — About my ParallelSort library

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.


 

[toc] | [next] | [standalone]

#2429

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

[toc] | [prev] | [next] | [standalone]

#2430

 The best case complexity of ParallelSort using mergesort  is:

((n/p)* log(n/p)) + O(n/p)


The worst case complexity of parallel sort library using mergesort is:

 ((n/p)* log(n/p)) +  O(n)



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

[toc] | [prev] | [next] | [standalone]

#2431

Hello,

The best case complexity of ParallelSort using mergesort  is:

 ((n/p)* log(n/p)) + O(n/p)

so the best case complexity  is:  ((n/p)* log(n/p))

The worst case complexity of parallel sort library using mergesort is:

 ((n/p)* log(n/p)) +  O(n)

so the worst case complexity is approximatly: O(n)



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

[toc] | [prev] | [next] | [standalone]

#2432

To explain more:

The best case complexity of ParallelSort using mergesort  is:

 ((n/p)* log(n/p)) + O(n/p)

the ((n/p)* log(n/p)) is the complexity of the sorting part.

O(n/p) is the best case complexity of the merging part.

so the best case complexity  is:  ((n/p)* log(n/p))

The worst case complexity of parallel sort library using mergesort is:

 ((n/p)* log(n/p)) +  O(n)

the ((n/p)* log(n/p)) is the complexity of the sorting part.

O(n) is the worst  case complexity of the merging part.

so the worst case complexity is approximatly: O(n)



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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web