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

Groups > comp.programming.threads > #2269

Re: About Ph.Ds papers and more ...

Cross-posted to 2 groups.

Show all headers | View raw

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.
>
>
>
>
>
>

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

Thread

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

csiph-web