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

Groups > comp.programming.threads > #2726

I explain my new algorithm

Show all headers | View raw

Hello,

I will explain my new algorithm of a scalable distributed sequential 
lock that is very powerful...


You have to understand first that people can become smarter by learning 
more and more, this is my case , i think that i am becoming smarter by 
reading PhD papers and by reading about synchronization algorithms, so 
first comes first , you have to understand that my point of view on the 
subject of intelligence is that intelligence is multifactorial, it
is influenced not only positively by the factor of "genetics" , but also 
by the factor of "culture"... this is my point of view and the point of 
view of many scientists... but on how much percentage of influence can 
we give to culture as a factor that enhance intelligence is a subject of 
debat... so you have to understand my point of view first on this 
subject first, now about my new invention of a scalable distributed 
sequential lock, i have arrived at my new algorithm by also reading many 
PhD papers and by looking first at the weakness of the following 
algorithm of Dmitry Vyukov's Reader-writer mutex:

http://www.1024cores.net/home/lock-free-algorithms/reader-writer-problem/distributed-reader-writer-mutex

look at the writer side of the Dmitry Vykov's algorithm , it is doing 
with  every rwlock in each corresponding core:

for (i = 0; i != mtx->proc_count; i += 1)
         pthread_rwlock_wrlock(&mtx->cell[i].mtx);


but this render this algorithm inefficient for the writer side , cause
every pthread_rwlock_wrlock() call transfer many cache-lines betwenn 
cores, so this will generate too much cache line transfers between cores 
when each writer executes distr_rw_mutex_wrlock() and this will become 
worse and worse when you add more and more cores, i mean this will 
tranfer more and more cache-lines between cores with more and more 
cores... so this will render the writer side throughput slow and this is 
the weakness of this algorithm...

So this is why i have used a sequential lock mechanism in the writer
side of my new algorithm so that to minimize efficiently the cache-lines 
transfers, so if you look at my algorithm, i am doing this inside the 
RLock() function on the writer side:

if (FCount6^.fcount6 mod GetSystemThreadCount)=0
then FCount5^.fcount5:=1;

FCount6^.fcount6 is a counter and i have applied to it a modulo of 
GetSystemThreadCount(), and GetSystemThreadCount() will return
the number of cores, so every "number of cores" calls to RLock() ,
my new algorithm switches from a sequential lock to  a distributed lock 
so that to eliminate the "livelock" and "starvation" weaknesses of 
Seqlock, cause Seqlock is a lockfree mechanism that can starve threads,
and that can livelock when there is more writers , cause Seqlock gives 
preference to writers threads over reader threads, but my new invention 
of a scalable distributed sequential lock  eliminates
"livelock" and "starvation" of Seqlock when there is more writers cause 
it switches to a distributed lock on every "number of cores" call
to the RLock() method , so this is why my new invention beats Seqlock,
and my new invention beats also the Dmitry's Reader-writer mutex
cause it switches to a distributed lock on every number of cores
call to RLock(), so in the remaining calls it switches to a sequential 
lock that render the writer side faster cause it generate much
less cache-lines tranfers than the Dmitry Vyukov's distributed 
reader-writer mutex. On the reader side of my algorithm i am using a 
Sequential lock mechanism. And i think that since my new algorithm
of a scalable distributed sequential lock is very powerful, so
i think it can even replace RCU.


You can download my new scalable distributed sequential lock from:

https://sites.google.com/site/aminer68/scalable-distributed-sequential-lock


Hope you have understood my new algorithm that is very powerful,
and you are free to port it to other languages like C++ and Java etc.




Thank you,
Amine Moulay Ramdane.

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

I explain my new algorithm Ramine <ramine@1.1> - 2014-12-03 18:10 -0800
  Re: I explain my new algorithm Ramine <ramine@1.1> - 2014-12-03 18:59 -0800

csiph-web