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

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

More about scalable algorithms

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

Contents

  More about scalable algorithms aminer <aminer@toto.net> - 2014-04-28 12:05 -0700
    Re: More about scalable algorithms aminer <aminer@toto.net> - 2014-04-28 12:11 -0700
      Re: More about scalable algorithms aminer <aminer@toto.net> - 2014-04-28 12:29 -0700

#2287 — More about scalable algorithms

Hello,

You have to understand that the Chriss Thomasson concurrent FIFO queue
that uses the bakery algorithm, here it is:


https://groups.google.com/d/topic/lock-free/acjQ3-89abE/discussion


Look at the producer() source code:

void producer(double state) {
     uint32_t ver = XADD(&head, 1);
     cell& c = cells[ver & (N - 1)];
     while (LOAD(&c.ver) != ver) backoff();
     c.state = state;
     STORE(&c.ver, ver + 1);
}



Since the algorithm is more parralelized so the "c.state = state;"
will be wrote in parallel by many threads to the cache or write-back 
cache,  so this will higher the throughput of the pop() side, but
even if the push() side is faster , notice that under contention the 
throughtput islimited by the throughput of the pop() side.


But look at the consumer() function:

double consumer() {
     uint32_t ver = XADD(&tail, 1);
     cell& c = cells[ver & (N - 1)];
     while (LOAD(&c.ver) != ver + 1) backoff();
     double state = c.state;
     STORE(&c.ver, ver + N);
     return state;
}



So as you have noticed the "double state = c.state" is serialized
cause the "Bus" serializes the data movements between the caches and the 
mmemory subsystem and the caches... but notice how many variables
causes data movements between caches and between memory and caches on
the Chriss Thomasson algorithm on consumer() side,
There is the "tail" variable right on "XADD(&tail, 1);", there
is the "&c.ver" variable right on  the "while (LOAD(&c.ver) != ver + 1)" 
and there is  "c.state"variable right on  "double state = c.state;"
but since those variables generate data movements between the caches
and between the memory and the caches, they will cause contention
on the Bus as i have explained it to you in my previous posts, cause 
those data movements are serialized on the "Bus" subsystem , so this 
contention will cause more waiting time and more waiting time means less 
throughput... but notice with me that in my concurrent FIFO queue that 
uses the two lock algorithm  since almost all the variable are located 
inside the critial section, that means they will generate less 
contention , hence the two locks algorithm is more efficient than the 
Chriss Thomasson algorithm cause it lowers the contention efficently, 
this is why even if my two locks algorithm uses more variables (4 in 
total) than the Chriss Thomasson algorithm that is using 3 variables,
the two locks algorithm is scoring the same throughput on the
pop() side than the Chriss Thomasson algorithm , that means
that the two locks algorithm is more efficient when it comes
to "contention" than the Chriss Thomasson algorithm.


Hope you have undertstood what i want you to understand in this post.



Thank you,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#2288

I correct some typos please read again...


Hello...

You have to understand that the Chriss Thomasson concurrent FIFO queue
that uses the bakery algorithm, here it is:


https://groups.google.com/d/topic/lock-free/acjQ3-89abE/discussion


Look at the producer() source code:

void producer(double state) {
     uint32_t ver = XADD(&head, 1);
     cell& c = cells[ver & (N - 1)];
     while (LOAD(&c.ver) != ver) backoff();
     c.state = state;
     STORE(&c.ver, ver + 1);
}



Since the algorithm is more parralelized so the "c.state = state;"
will be wrote in parallel by many threads to the cache or write-back 
cache,  so this will higher the throughput of the push() side, but
even if the push() side is faster , notice that under contention the 
throughtput is limited by the throughput of the pop() side.


But look at the consumer() function:

double consumer() {
     uint32_t ver = XADD(&tail, 1);
     cell& c = cells[ver & (N - 1)];
     while (LOAD(&c.ver) != ver + 1) backoff();
     double state = c.state;
     STORE(&c.ver, ver + N);
     return state;
}



So as you have noticed the "double state = c.state" is serialized
cause the "Bus" serializes the data movements between the caches and the 
mmemory subsystem and the caches... but notice how many variables
causes data movements between caches and between memory and caches on
the Chriss Thomasson algorithm on consumer() side,
There is the "tail" variable right on "XADD(&tail, 1);", there
is the "&c.ver" variable right on  the "while (LOAD(&c.ver) != ver + 1)" 
and there is  "c.state"variable right on  "double state = c.state;"
but since those variables generate data movements between the caches
and between the memory and the caches, they will cause contention
on the Bus as i have explained it to you in my previous posts, cause 
those data movements are serialized on the "Bus" subsystem , so this 
contention will cause more waiting time and more waiting time means less 
throughput... but notice with me that in my concurrent FIFO queue that 
uses the two lock algorithm  since almost all the variable are located 
inside the critial section, that means they will generate less 
contention , hence the two locks algorithm is more efficient than the 
Chriss Thomasson algorithm cause it lowers the contention efficently, 
this is why even if my two locks algorithm uses more variables (4 in 
total) than the Chriss Thomasson algorithm that is using 3 variables,
the two locks algorithm is scoring the same throughput on the
pop() side than the Chriss Thomasson algorithm , that means
that the two locks algorithm is more efficient when it comes
to "contention" than the Chriss Thomasson algorithm.


Hope you have undertstood what i want you to understand in this post.



Thank you,
Amine Moulay Ramdane.

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

#2291

On 4/28/2014 12:11 PM, aminer wrote:
>
> I correct some typos please read again...
>
>
> Hello...
>
> You have to understand that the Chriss Thomasson concurrent FIFO queue
> that uses the bakery algorithm, here it is:
>
>
> https://groups.google.com/d/topic/lock-free/acjQ3-89abE/discussion
>
>
> Look at the producer() source code:
>
> void producer(double state) {
>      uint32_t ver = XADD(&head, 1);
>      cell& c = cells[ver & (N - 1)];
>      while (LOAD(&c.ver) != ver) backoff();
>      c.state = state;
>      STORE(&c.ver, ver + 1);
> }
>
>
>
> Since the algorithm is more parralelized so the "c.state = state;"
> will be wrote in parallel by many threads to the cache or write-back
> cache,  so this will higher the throughput of the push() side, but
> even if the push() side is faster , notice that under contention the
> throughtput is limited by the throughput of the pop() side.
>
>
> But look at the consumer() function:
>
> double consumer() {
>      uint32_t ver = XADD(&tail, 1);
>      cell& c = cells[ver & (N - 1)];
>      while (LOAD(&c.ver) != ver + 1) backoff();
>      double state = c.state;
>      STORE(&c.ver, ver + N);
>      return state;
> }
>
>
>
> So as you have noticed the "double state = c.state" is serialized
> cause the "Bus" serializes the data movements between the caches and the
> mmemory subsystem and the caches... but notice how many variables
> causes data movements between caches and between memory and caches on
> the Chriss Thomasson algorithm on consumer() side,
> There is the "tail" variable right on "XADD(&tail, 1);", there
> is the "&c.ver" variable right on  the "while (LOAD(&c.ver) != ver + 1)"
> and there is  "c.state"variable right on  "double state = c.state;"
> but since those variables generate data movements between the caches
> and between the memory and the caches, they will cause contention
> on the Bus as i have explained it to you in my previous posts, cause
> those data movements are serialized on the "Bus" subsystem , so this
> contention will cause more waiting time and more waiting time means less
> throughput... but notice with me that in my concurrent FIFO queue that
> uses the two lock algorithm  since almost all the variable are located
> inside the critial section, that means they will generate less
> contention , hence the two locks algorithm is more efficient than the
> Chriss Thomasson algorithm cause it lowers the contention efficently,
> this is why even if my two locks algorithm uses more variables (4 in
> total) than the Chriss Thomasson algorithm that is using 3 variables,

I was speaking about the variables that generate data movements between 
caches or between the memory subsystem and the caches, hope you have
understood.


> the two locks algorithm is scoring the same throughput on the
> pop() side than the Chriss Thomasson algorithm , that means
> that the two locks algorithm is more efficient when it comes
> to "contention" than the Chriss Thomasson algorithm.
>
>
> Hope you have undertstood what i want you to understand in this post.
>
>
>
> Thank you,
> Amine Moulay Ramdane.
>
>

[toc] | [prev] | [standalone]

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

csiph-web