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

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

More precision...

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

Contents

  More precision... aminer <aminer@toto.net> - 2014-04-27 00:25 -0700

#2273 — More precision...

Hello,

We have to be more precise when dealing with scalable algorithms...

What i want to say now , is that i was wrong when i have explained
the 33% difference in throughtput between my algorithm and the Chriss 
Thomasson algorithm with the factor "contention", cause notice with me 
that i am using an efficient backoff , so i don't think it's the the 
"factor" that we call "contention" that is causing 33% less throughtput 
(on the pop() side) in my algorithm than the Chriss Thomasson algorithm, 
so now we have isolated more the cause, hence the cause is not the 
"contention", so what is the cause then ?


Look carefully at the pop() side of Chriss Thomasson algorithm:



===

function TWQueue.pop(var state:long):boolean;
     var ver:long;
         c:^cell;

begin
     ver := ATOMIC_XADD(@tail, 1);
     c :=  @fcount1^[ver and (fsize - 1)];
     while ATOMIC_LOAD(@c^.ver) <> ver + 1 do backoff;
     state := c^.state;
     ATOMIC_STORE(@c^.ver, ver + fsize);
     result:=true

end;

===


You will notice that this algorithm has more parallelism than
my algorithm , in my algorithm i am serializing with a Ticket
mechanism, but in the Chriss Thomasson algorithm many
threads can execute the "while ATOMIC_LOAD(@c^.ver) <> ver + 1"
in parallel , this is not the case with my algorithm, so
i think that from the hardware point when many threads
are executing the "while ATOMIC_LOAD(@c^.ver) <> ver + 1 do backoff"
and the "ATOMIC_LOAD(@c^.ver) <> ver + 1" for many threads in parallel 
than means that many threads have executed this instruction in parallel 
, so
in the hardware there must be some gain doing this instruction in
parallel, so the Chriss Thomasson algorithm has more parallelism
than my algorithm , cause in my algorithm i am using a Ticket
mechanism that serializes the execution of some instructions,
so finally this will give less parallelism and finally this
explains the 33% improvement of the Chriss Thomasson algorithm.


Thank you,
Amine Moulay Ramdane.

[toc] | [standalone]

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

csiph-web