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

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

I have said this and my previous post

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

Contents

  I have said this and my previous post aminer <aminer@toto.net> - 2014-04-26 22:15 -0700

#2271 — I have said this and my previous post

I have said this and my previous post:

 >Although i am using a backoff mechanism to reduce the contention on 
 >the "Bus" system, there is still more contention on my algorithm than 
 >the Chriss Thomasson algorithm, cause my "tail" variable on the pop() 
 >side generate more data movements between caches than
 >the Chriss Thomasson concurrent FIFO queue, and when we say
 >more data movement between caches this means also more contention
 >on the Bus system and this means also more waiting time...
 >this is why my algorithm has scored 33% less throughput than
 >the Chriss Thomasson concurrent FIFO queue that uses the bakery 
 >algorithm."


For more proof and to be more precise i will say also this:

Look again the my pop() side in my algorithm:

===

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;

===



Look carefully at the "tail1:=tail" and to "tail=lasttail"

both of them will generate more data movements between caches
than the Chriss Thomasson algorithm, and you have to know that those
data movements between caches are more expensive than the other 
instructions on my code of the pop() side, so in the "repeat until" loop 
above since the "tail1:=tail" and to "tail=lasttail"  are expensive when 
they incur data movement between the caches they will take almost all 
the time that takes the "repeat loop" and what inside this loop , so 
this is why they will cause contention on the "Bus"
system for sure when there is data movement between caches, and this 
will incur more waiting time in the other popping threads cause the 
access to the Bus between the caches is serialized, this weakness do not 
exist in the Chriss Thomasson algorithm cause his variable "@c^.ver" 
will incur only one data movement and cache-line transfer, so this will 
not cause contention and will not incur more waiting time to the other 
poping threads this is why the Chriss Thomasson has scored 33% better on 
the throughput of the pop() side than my algorithm.


And i have tried to explained to you that i have noticed that
the PH.Ds papers don't explain to you there algorithm from
the point of view data movements between caches and there influence on 
the threads as i am explaining it to you.




Thank you,
Amine Moulay Ramdane.











This is how

[toc] | [standalone]

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

csiph-web