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

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

About Ph.Ds papers and more ...

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

Contents

  About  Ph.Ds papers and more ... aminer <aminer@toto.net> - 2014-04-26 20:15 -0700
    Re: About  Ph.Ds papers and more ... aminer <aminer@toto.net> - 2014-04-26 21:44 -0700
    Re: About  Ph.Ds papers and more ... aminer <aminer@toto.net> - 2014-04-26 22:16 -0700

#2268 — About Ph.Ds papers and more ...

Hello,

I was thinking more and more about scalable algorithms...

And what i want to say today is something very important,
first i have looked at many Ph.Ds papers and what i have
noticed that there is a kind of weakness on them, scalable algorithms
must be viewed from many point of views , like from the "correctness" 
view point and from the "performance" view point, but what i have 
noticed on many papers that speak about scalable algorithms is that 
there is kinf of weakness on there treatment of the "performance" point 
of view, i explain: when the papers speak about the "performance" of 
there algorithms they don't do it efficiently , and you will notice that 
the very big part in there papers is given to the proof of the 
"correctness" of there algorithms and ro the empirical testing, but they 
don't reason and speak about the all variables that generates 
data-movements between the caches and there expensiveness and the 
contention that they generate on the computer "Bus" , what i mean is 
that they must also reason and make clear there algorithms by speaking 
about all the variables in there algorithms that generate data movements 
between the caches and there interractions, cause that's how they can 
proof why there empirical testing is giving them there results..

To understand me better , let's give an example by analyzing my
new algorithm of a fast concurrent FIFO queue compared to
the Chriss Thomasson algorithm that uses the bakery algorithm...


We begin by a first question:


I have tested my algorithms against the Chriss Thomasson algorithm
and i have found that the Chriss Thomasson concurrent FIFO queue
gives empirically on my testing 4.8 millions of pop transactions
per second on my 2.4 GHz Quadcore, but my concurrent FIFO queue
gives 3.2 millions of pop transactions per second on on my 2.4 GHz 
Quadcore, so this is the empirical results, but the question
is how can we explain that ? as i have told you just before we
have to look at those algorithms from the "performance" point of view
but when we do it like that we have to not be satisfied by just
the empirical results , we have to analyse the algorithm from
the point of view the data movements between caches that are expensive 
and that that also generate more contention on the Bus system...


So let's look at my algorithm in the pop() side:

===

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;

===


As you can notice if we want analyse the performance of
this algorithm from the "performance" point of view,
we have to spot all the variables that generate data movements
between caches or from the memory subsystem to the
local caches and there interractions... the difference between the 
Chriss Thomasson algorithm and my algorithms is that my algorithm 
generates more data movements between caches.

Here is the variables that generate data movements that are expensive
and that generates also contention on the "Bus" subsystem"

Fist there a  "temp" variable in "LockedIncLong(temp)"  that generates 
data movement  beteen caches  and can cause contention on the "Bus"...

The "tail" variable in "tail1:=tail" generates data movement between 
caches on the "Tail" and can cause contention on the "Bus"...

Also the tail variable in "tail=lasttail" generates data movement
between caches and can cause contention on the "Bus"...

But more about the contention on the "Bus" i will say that as you have 
noticed i have used a proportional backoff that reduces the contention 
on the "Bus", cause the contention on the computer Bus is serialized and 
it can incur more waiting time...

But notice with me that the Chriss Thomasson algorithm there is only
two variables that generates data movements between caches and can cause 
contention on the "Bus"...

Look at the pop() function of the Chriss Thomasson algorithm
that uses the bakery 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;

===

Notice with me that there is only two variables that
generates data movements and can cause contention
on the "Bus"...

First variable is  "tail" on the "ATOMIC_XADD(@tail, 1)" that generates 
data movements beween caches and can cause contention on the "Bus"...

The second variable is on ATOMIC_LOAD(@c^.ver) <> ver + 1
but this is efficient cause it incurs only one data movement
and doesn't cause contention on the "Bus"...

So this why the Chriss Thomasson algorithm has scored more throughput
on the pop() side , cause on my pop() method there is more variables
that generate data movements between caches and can cause contention.



Thank you,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#2269

Question:

Amine, you have said this:

 > So this why the Chriss Thomasson algorithm has scored more throughput
 > on the pop() side , cause on my pop() method there is more variables
 > that generate data movements between caches and can cause contention.


How can you say this and you know that his algorithm has the same number 
of variables than your algorithm, so where is the problem ?


Answer:

I have to be more clearer and precise, what i wanted to say is this:

His "@c^.ver" variable do not generate lots of contention, cause
when the poping threads will pop one after the other in parallel
they will touch less number of time "@c^.ver" than my algorithm,
when the thread will enter the pop() method in the Chriss Thomasson 
algorithm it will incur one data movement and cache-line transfer
on "@c^.ver" on the pop() side,  and that's optimal and efficient , but 
in my algorithm i am using a Ticket mechanism that incur more data 
movements between caches and this also cause contention on the "Bus" 
system, 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.



Thank you,
Amine Moulay Ramdane.




















On 4/26/2014 8:15 PM, aminer wrote:
>
> Hello,
>
> I was thinking more and more about scalable algorithms...
>
> And what i want to say today is something very important,
> first i have looked at many Ph.Ds papers and what i have
> noticed that there is a kind of weakness on them, scalable algorithms
> must be viewed from many point of views , like from the "correctness"
> view point and from the "performance" view point, but what i have
> noticed on many papers that speak about scalable algorithms is that
> there is kinf of weakness on there treatment of the "performance" point
> of view, i explain: when the papers speak about the "performance" of
> there algorithms they don't do it efficiently , and you will notice that
> the very big part in there papers is given to the proof of the
> "correctness" of there algorithms and ro the empirical testing, but they
> don't reason and speak about the all variables that generates
> data-movements between the caches and there expensiveness and the
> contention that they generate on the computer "Bus" , what i mean is
> that they must also reason and make clear there algorithms by speaking
> about all the variables in there algorithms that generate data movements
> between the caches and there interractions, cause that's how they can
> proof why there empirical testing is giving them there results..
>
> To understand me better , let's give an example by analyzing my
> new algorithm of a fast concurrent FIFO queue compared to
> the Chriss Thomasson algorithm that uses the bakery algorithm...
>
>
> We begin by a first question:
>
>
> I have tested my algorithms against the Chriss Thomasson algorithm
> and i have found that the Chriss Thomasson concurrent FIFO queue
> gives empirically on my testing 4.8 millions of pop transactions
> per second on my 2.4 GHz Quadcore, but my concurrent FIFO queue
> gives 3.2 millions of pop transactions per second on on my 2.4 GHz
> Quadcore, so this is the empirical results, but the question
> is how can we explain that ? as i have told you just before we
> have to look at those algorithms from the "performance" point of view
> but when we do it like that we have to not be satisfied by just
> the empirical results , we have to analyse the algorithm from
> the point of view the data movements between caches that are expensive
> and that that also generate more contention on the Bus system...
>
>
> So let's look at my algorithm in the pop() side:
>
> ===
>
> 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;
>
> ===
>
>
> As you can notice if we want analyse the performance of
> this algorithm from the "performance" point of view,
> we have to spot all the variables that generate data movements
> between caches or from the memory subsystem to the
> local caches and there interractions... the difference between the
> Chriss Thomasson algorithm and my algorithms is that my algorithm
> generates more data movements between caches.
>
> Here is the variables that generate data movements that are expensive
> and that generates also contention on the "Bus" subsystem"
>
> Fist there a  "temp" variable in "LockedIncLong(temp)"  that generates
> data movement  beteen caches  and can cause contention on the "Bus"...
>
> The "tail" variable in "tail1:=tail" generates data movement between
> caches on the "Tail" and can cause contention on the "Bus"...
>
> Also the tail variable in "tail=lasttail" generates data movement
> between caches and can cause contention on the "Bus"...
>
> But more about the contention on the "Bus" i will say that as you have
> noticed i have used a proportional backoff that reduces the contention
> on the "Bus", cause the contention on the computer Bus is serialized and
> it can incur more waiting time...
>
> But notice with me that the Chriss Thomasson algorithm there is only
> two variables that generates data movements between caches and can cause
> contention on the "Bus"...
>
> Look at the pop() function of the Chriss Thomasson algorithm
> that uses the bakery 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;
>
> ===
>
> Notice with me that there is only two variables that
> generates data movements and can cause contention
> on the "Bus"...
>
> First variable is  "tail" on the "ATOMIC_XADD(@tail, 1)" that generates
> data movements beween caches and can cause contention on the "Bus"...
>
> The second variable is on ATOMIC_LOAD(@c^.ver) <> ver + 1
> but this is efficient cause it incurs only one data movement
> and doesn't cause contention on the "Bus"...
>
> So this why the Chriss Thomasson algorithm has scored more throughput
> on the pop() side , cause on my pop() method there is more variables
> that generate data movements between caches and can cause contention.
>
>
>
> Thank you,
> Amine Moulay Ramdane.
>
>
>
>
>
>

[toc] | [prev] | [next] | [standalone]

#2272

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.

[toc] | [prev] | [standalone]

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

csiph-web