Asp Forum - About parallel sort algorithms

Ramine

2/18/2015 3:16:00 AM

Hello again my dear programmers,

Let's talk about my parallel sort library, my parallel sort library
divides the array to be sorted into mutiple sub-arrays, and it sorts
those sub-arrays in parallel then it uses a parallel merge algorithm to
merge the final sub-arrays to be sorted:

Here is the kind of parallel merge that is used, read here:

http://dzmitryhuba.blogspot.ca/2010/10/parallel-merge...

Here is the steps of the parallel merge algorithm:

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

But there is still a problem that i have talked about before, this
parallel merge sort above or the parallel sort algorithms of my parallel
sort library are limited by the serial part of the Amdahl's law that
correspond to the memory transfers from the memory to the L2 caches,
this serial part will limit the scalability to not more than 8X or 4X ,
so what i have said before that on my next project i will render my
parallel sort library scalable on NUMA architecture so that those memory
transfers from the memory to the L2 caches will be parallelized and this
will make my parallel sort library a very powerful library. So stay tuned...

You can also use sameplesort, but my parallel sort library will be very
good also when it will become scalable on NUMA architecture.

Thank you,
Amine Moulay Ramdane.

comp.programming

About parallel sort algorithms

Ramine

x Login to ForumsZone