About parallel merging ...

About parallel merging ...

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.

It's better to use the
following
algorithm;

http://www.drdobbs.com/parallel/parallel-merge/229204454?queryText=paral...

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.

3 Beiträge / 0 neu
Letzter Beitrag
Nähere Informationen zur Compiler-Optimierung finden Sie in unserem Optimierungshinweis.

Very interesting, thank you.

Thanks for these web-links.

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

I'm not surprised with your results because MergeSort is easily parallelizable by design: it splitts a source ( input ) data set in half on every recursion call until it reaches a threshold value two or four.

Note: A threshold value depends if a data-mining step ( pair-switching ) was performed before processing.

>>...Using binary search find index k of the first element in Y greater than X[m]...

It is clear that application of a binary search inside of MergeSort will create additional overhead and possibly affect a performance.

Kommentar hinterlassen

Bitte anmelden, um einen Kommentar hinzuzufügen. Sie sind noch nicht Mitglied? Jetzt teilnehmen