Recent

Author Topic: About my Parallel Sort library  (Read 3591 times)

aminer

  • Hero Member
  • *****
  • Posts: 956
About my Parallel Sort library
« on: November 01, 2012, 12:19:37 am »

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.


 

aminer

  • Hero Member
  • *****
  • Posts: 956
Re: About my Parallel Sort library
« Reply #1 on: November 01, 2012, 12:49:20 am »

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

  • Hero Member
  • *****
  • Posts: 956
Re: About my Parallel Sort library
« Reply #2 on: November 01, 2012, 01:41:24 am »


 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

  • Hero Member
  • *****
  • Posts: 956
Re: About my Parallel Sort library
« Reply #3 on: November 01, 2012, 01:48:22 am »


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

  • Hero Member
  • *****
  • Posts: 956
Re: About my Parallel Sort library
« Reply #4 on: November 01, 2012, 02:07:25 am »


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

  • Hero Member
  • *****
  • Posts: 956
Re: About my Parallel Sort library
« Reply #5 on: November 01, 2012, 02:57:38 am »


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

The tests was done on a quad cores system.


Amine Moulay Ramdane.





aminer

  • Hero Member
  • *****
  • Posts: 956
Re: About my Parallel Sort library
« Reply #6 on: November 01, 2012, 02:57:51 am »
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..

The tests was done on a quad cores system.


Amine Moulay Ramdane.



 

TinyPortal © 2005-2018