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

Groups > comp.programming.threads > #2267

My very new algorithm explanation...

Cross-posted to 2 groups.

Show all headers | View raw

Hello,

I will present to you my reasonning to prove to you that my concurrent 
FIFO queue algorithm that is starvation-free is correct...

You will find the source code of my very fast concurrent FIFO queue here:

http://pages.videotron.com/aminer/


We begin by the push() method, its source code look like this:

===

function TWQueue.push(tm : long):boolean;
var lastHead,newtemp:long;
i,j:integer;
begin

if getlength >= fsize
   then
       begin
           result:=false;
           exit;
       end;

newTemp:=LockedIncLong(head);
lastHead:=newtemp-1;

repeat
asm pause end;
until fcount1^[lastHead and fMask].flag=0;
setObject(lastHead,tm);
fcount1^[lastHead and fMask].flag:=1;
if fwait then sema.signal;
result:=true;
end;

===


you have to know that "fsize" is fixed to the length of the queue minus 
a "margin" that is equal to 1000 , that means that it's limited to 1000 
threads in total that can run at the same time the push(), but you can 
vary the margin to higher the number of threads that can run the push() 
at the same time...

So if getlength equal fsize-1 that means that 1000 threads can cross 
because "if getlength >= fsize" can be false at the same time, but even 
if it is false at the same time , there a margin of 1000 threads, so my 
reasonning is correct here.

Now we look at the rest of the code...

Every cell of the array based queue look like this:

type cell = record
     obj:long;
     flag:long;
     {$IFDEF CPU32}
     cache:typecache2;
     {$ENDIF CPU32}
     {$IFDEF CPU64}
     cache:typecache3;
     {$ENDIF CPU64}
     end;

It's cache padded to a cache-line size and the array is aligned on 64 
bytes so that to avoid false-sharing...

After that we increment the "head" like this with an atomic increment...

newTemp:=LockedIncLong(head);
lastHead:=newtemp-1;

and if fcount1^[lastHead and fMask].flag=0 that means there is no item
in the cell , we will write the item on the cell by doing this:

setObject(lastHead,tm);

and after that we set the flag of the cell to 1 so that the pop()
can read from it when it's set to 1 like this:

fcount1^[lastHead and fMask].flag:=1;

so as you have noticed i have reasonned and explained to you the push() 
side, and i think my reasonning is correct here.

Now here is the new pop() method...

==

function TWQueue.pop(var obj:long):boolean;

var lastTail,newtemp,tail1,head1,count: long;
     i:integer;
begin

if fwait then sema.wait;

result:=true;

newTemp:=LockedIncLong(temp);
lastTail:=newtemp-1;

repeat
if fcount1^[lastTail and fMask].flag=1 then break;
sleep(0);
until (false);

obj:=getObject(lastTail);

repeat

head1:=lastTail;
tail1:=tail;
   if head1 < tail1
        then count:= (High(long)-tail1)+(1+head1)
        else count:=(head1-tail1);

if count>0 then for i:=0 to count*40 do asm pause end;

if tail=lasttail
    then
       begin
        fcount1^[lastTail and fMask].flag:=0;
        tail:=newtemp;
        exit;
       end;
sleep(0);
until false;

end;

==


So as you have noticed we have to reason about this algorithm to prove 
that all is correct, so follow with me please...

When the threads enter the pop() method they will atomically increment 
the "temp" variable , and after that they will wait that 
fcount1^[lastTail and fMask].flag is equal to 1, that means that an item 
is available, and after that they will get the item from the cell and 
enters a carefully designed backoff that is mandatory to reduce the 
cache-coherence traffic and to reduce the contention,  after that it 
uses a Ticket mechanism to be able to increment "Tail:", but before 
incrementing "tail" we set  fcount1^[lastTail and fMask].flag to 0 so 
that the push side will be able to to put an item on the cell, but even 
though we set fcount1^[lastTail and fMask].flag to 0 before incrementing 
"Tail",  the algorithm is correct since the push threads are limited on 
how much they can push by the length of fsize+margin, so i think my 
algorithm is correct and efficient.

So as you have noticed i have reasonned about my algorithm an i think my 
algorithm is correct now.

Finally i have benchmarked my algorithm without using my SemaMonitor and 
has almost the same throughtput on the pop() side as the Chriss 
Thomasson Queue that uses the bakery algorithm and it gives the same 
throughput on the push() side as the Chriss Thomasson Queue that uses 
the bakery algorithm and it`s starvation-free on the push and the pop 
side and it  minimizes efficiently the cache-coherence traffic and it 
reduces the contention efficiently so that it can better scale with more 
and more cores.

You can download my new algorithm of a very fast concurrent FIFO queue from:

http://pages.videotron.com/aminer/




Thank you,
Amine Moulay Ramdane.

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

Thread

My very new algorithm explanation... aminer <aminer@toto.net> - 2014-04-26 11:59 -0700

csiph-web