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

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

Read again, i correct a little mistake..

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

Contents

  Read again, i correct a little mistake.. Horizon68 <horizon@horizon.com> - 2019-03-24 09:31 -0700

#4961 — Read again, i correct a little mistake..

Hello,


Read again, i correct a little mistake..

My Parallel Sort Library was updated to version 3.6

I have enhanced it more, and now it scales more and it is
faster.

Description:

My Parallel Sort Library that supports Parallel Quicksort, Parallel 
HeapSort and Parallel MergeSort on Multicores systems.

Parallel Sort Library uses my Thread Pool Engine and sort many array 
parts - of your array - in parallel using Quicksort or HeapSort or 
MergeSort and after that it finally merge them - with the merge() 
procedure -

In the previous parallelsort version i have parallelized only the sort 
part, but in this new parallelsort version i have parallelized also the 
merge procedure part and it gives better performance.

My new parallel sort algorithm has become more cache-aware, and i have 
done some benchmarks with my new parallel algorithm and it has given up 
to 5X scalability on a Quadcore when sorting strings, other than that i 
have cleaned more the code and i think my parallel Sort library has 
become a more professional and industrial parallel Sort library , you 
can be confident cause i have tested it thoroughly and no bugs have 
showed , so i hope you will be happy with my new Parallel Sort library.

My algorithm of finding the median in Parallel merge is 
O(log(min(|A|,|B|))), where |A| is the size of A, since the binary 
search is performed within the smaller array and is O(lgN).

The idea:

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.


You can download it from:

https://sites.google.com/site/scalable68/parallel-sort-library



Thank you,
Amine Moulay Ramdane.

[toc] | [standalone]

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

csiph-web