topic Very interesting, thank you. in IntelĀ® Moderncode for Parallel Architectures
https://community.intel.com/t5/Intel-Moderncode-for-Parallel/About-parallel-merging/m-p/994149#M6336
Very interesting, thank you.Tue, 25 Dec 2012 08:38:47 GMTAndrey_Tikhonov2012-12-25T08:38:47ZAbout parallel merging ...
https://community.intel.com/t5/Intel-Moderncode-for-Parallel/About-parallel-merging/m-p/994148#M6335
<P></P><P>Hello,<BR /><BR />I have just read the following paper on Parallel
Merging:<BR /><BR /><A href="http://www.economyinformatics.ase.ro/content/EN4/alecu.pdf" target="_blank">http://www.economyinformatics.ase.ro/content/EN4/alecu.pdf</A><BR /><BR /><BR />And
i have implemented this algorithm just to see what is the
performance.<BR /><BR />And i have noticed that the serial algorithm is 8 times
slower<BR />than the merge function that you find in the serial mergesort
algorithm.<BR />So 8 times slower, it's too slow.<BR /><BR />It's better to use the
following
algorithm;<BR /><BR /><A href="http://www.drdobbs.com/parallel/parallel-merge/229204454?queryText=parallel%2Bsort" target="_blank">http://www.drdobbs.com/parallel/parallel-merge/229204454?queryText=parallel%2Bsort</A><BR /><BR /><BR />The
idea is simple:<BR /><BR />Let's assume we want to merge sorted arrays X and Y.
Select X<M> median<BR />element in X. Elements in X[ .. m-1] are less than or
equal to X<M>.<BR />Using binary search find index k of the first element in Y
greater than <BR />X<M>. <BR />Thus Y[ .. k-1] are less than or equal to X<M> as
well. Elements in X[m+1 .. ]<BR />are greater than or equal to X<M> and Y[k .. ]
are greater. So merge(X, Y)<BR />can be defined as concat(merge(X[ .. m-1], Y[ ..
k-1]), X<M>, merge(X[m+1 .. ], Y[k .. ]))<BR />now we can recursively in parallel
do merge(X[ .. m-1], Y[ .. k-1]) and<BR />merge(X[m+1 .. ], Y[k .. ]) and then
concat results.<BR /><BR />And then you can continue to apply this method
recursivily.<BR /><BR /><BR /><BR />Thank you,<BR />Amine Moulay Ramdane.</M></M></M></M></M></M></P><P></P>Sun, 26 Aug 2012 18:49:22 GMThttps://community.intel.com/t5/Intel-Moderncode-for-Parallel/About-parallel-merging/m-p/994148#M6335aminer102012-08-26T18:49:22ZVery interesting, thank you.
https://community.intel.com/t5/Intel-Moderncode-for-Parallel/About-parallel-merging/m-p/994149#M6336
Very interesting, thank you.Tue, 25 Dec 2012 08:38:47 GMThttps://community.intel.com/t5/Intel-Moderncode-for-Parallel/About-parallel-merging/m-p/994149#M6336Andrey_Tikhonov2012-12-25T08:38:47ZThanks for these web-links.
https://community.intel.com/t5/Intel-Moderncode-for-Parallel/About-parallel-merging/m-p/994150#M6337
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 <STRONG>MergeSort</STRONG> 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 <STRONG>binary search</STRONG> find index k of the first element in Y greater than X<M>...
It is clear that application of a <STRONG>binary search</STRONG> inside of <STRONG>MergeSort</STRONG> will create additional overhead and possibly affect a performance.</M>Sun, 13 Jan 2013 22:45:26 GMThttps://community.intel.com/t5/Intel-Moderncode-for-Parallel/About-parallel-merging/m-p/994150#M6337SergeyKostrov2013-01-13T22:45:26Z