Lock-free Ringbuffer , lock-free flqueue , lock-free ParallelQueue and scalability

Lock-free Ringbuffer , lock-free flqueue , lock-free ParallelQueue and scalability

Post by amine » Sun, 19 Sep 2010 10:39:23


We have to be smart here, so please follow with me...

My new scalability mathematical model says that:



Speed(t,N,Sic,Soc) = 1 / (Sic * ((((1) * () / 2 )/ + (P / N))

Sic: serial part inside the critical region(locked regions)
Soc: serial part outside the critical region
P: parallel part
n: number of threads (or processes)
N: number of cores
C: contention factor in percentage,

C = average number of contended threads / n

and = C * n

And of course n (number of threads or processes) mus> be >= 2

So if you take a look at (benchmarks) graphs:


You will notice that my lock-free ParallelQueue is scaling better
than lockfree RingBuffer and flqueue, cause my lock-free
is lock-free and it's keeping the locked region very small, just
a CAS(longword(tail[0]),longword(lasttail),longword(newtemp))
on the Push() side, and a CAS(head[0],lasthead,lasthead+1)
on the Pop() side , so it is reducing the Sic part in my


Also i am using lock-striping in my lock-free algorithm , that
means that i am REDUCING the Sic part in my scalability equation
even more, but since the Sic is very small, but it still exists, my
scalability mathematical model predict that when n(number of threads)
will grow, = C * n will grow also, but since in equation [1] above
factor ((((1) * () / 2 )/ = ((1) * () / (2 * is growing
much faster
in the numerator ((1) * () than the denominator (2 * , that
that there will be a retrogade throuput when n (number of threads)
becomes much bigger, and this rectrograde throuput is reached
more quickly with lock-free flqueue and lock-free Ringbuffer than
with my lock-free Parallelqueue.

Welcome to my webpages:




Amine Moulay Ramdane.