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

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

Read again, i correct a last typo..

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

Contents

  Read again, i correct a last typo.. Horizon68 <horizon@horizon.com> - 2019-03-21 12:55 -0700

#4959 — Read again, i correct a last typo..

Hello..


Read again, i correct a last typo..

I have just "invented" a "highly" scalable Parallel Sort library
for shared memory architecture that supports highly scalable Mergesort, 
Quicksort and Heapsort. I think it is the "best" one in shared memory 
architecture because it also uses my other inventions of a fully 
scalable FIFO queue and a fully scalable Threadpool. So i think i will 
sell it to Google or to Microsoft or to Embarcadero or such big software 
companies.

Also i have have just invented the following Parallel Sort Library that
supports a new and more efficient Parallel merge algorithms that 
improves the worst-case performance:

My algorithm of Parallel merge of my  Parallel Sort Library that you 
will find here in my website:

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

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). But the new 
Parallel merge algorithm iof my Parallel Sort Library is 
O(log(|A|+|B|)), which is slightly worse. With further optimizations the 
order was reduced to O(log(2*min(|A|,|B|))), which is better, but is 2X 
more work, since both arrays may have to be searched. All algorithms are 
logarithmic. Two binary searches were necessary to find an even split 
that produced two equal or nearly equal halves. Luckily, this part of 
the merge algorithm is not performance critical. So, more effort can be 
spent looking for a better split. This new algorithm in the parallel 
merge balances the recursive binary tree of the divide-and-conquer and 
improve the worst-case performance of parallel merge sort.


So stay tuned !


Thank you,
Amine Moulay Ramdane.

[toc] | [standalone]

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

csiph-web