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

Groups > comp.programming.threads > #1039 > unrolled thread

About Parallel Merging paper...

Back to article view | Back to comp.programming.threads

Contents

  About Parallel Merging paper... "aminer" <aminer@videotron.ca> - 2012-08-26 14:36 -0500
    Re: About Parallel Merging paper... "aminer" <aminer@videotron.ca> - 2012-08-26 14:45 -0500

#1039 — About Parallel Merging paper...

Hello,

I have just read the following paper on Parallel Merging:

http://www.economyinformatics.ase.ro/content/EN4/alecu.pdf


And i have implemented this algorithm just to see what is the performance.

And i have noticed that the serial algorithm is 8 times slower
than the merge function that you find in the serial mergesort algorithm.
So 8 times slower, it's too slow.




Thank you,
Amine Moulay Ramdane. 

[toc] | [next] | [standalone]

#1040

Hello,

It's better to use the following algorithm;

http://www.drdobbs.com/parallel/parallel-merge/229204454?queryText=parallel%2Bsort


The idea is simple:

Let's assume we want to merge sorted arrays X and Y. Select X[m] median
element in X. Elements in X[ .. m-1] are less than or equal to X[m].

Using binary search find index k of the first element in Y greater than 
X[m].
Thus Y[ .. k-1] are less than or equal to X[m] as well. Elements in X[m+1 
.. ]
are greater than or equal to X[m] and Y[k .. ] are greater. So merge(X, Y)
can be defined as concat(merge(X[ .. m-1], Y[ .. k-1]), X[m], merge(X[m+1 
.. ], Y[k .. ]))
now we can recursively in parallel do merge(X[ .. m-1], Y[ .. k-1]) and
merge(X[m+1 .. ], Y[k .. ]) and then concat results.


And then you can continue to apply this method recursivily.



Thank you,
Amine Moulay Ramdane.



"aminer" <aminer@videotron.ca> wrote in message 
news:k1dqb6$7cb$1@dont-email.me...
>
> Hello,
>
> I have just read the following paper on Parallel Merging:
>
> http://www.economyinformatics.ase.ro/content/EN4/alecu.pdf
>
>
> And i have implemented this algorithm just to see what is the performance.
>
> And i have noticed that the serial algorithm is 8 times slower
> than the merge function that you find in the serial mergesort algorithm.
> So 8 times slower, it's too slow.
>
>
>
>
> Thank you,
> Amine Moulay Ramdane.
> 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web