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

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

CAS operations and scalability...

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

Contents

  CAS operations and scalability... "aminer" <aminer@videotron.ca> - 2012-08-26 12:28 -0500
    Re: CAS operations and scalability... "aminer" <aminer@videotron.ca> - 2012-08-26 12:56 -0500
    Re: CAS operations and scalability... Patricia Shanahan <pats@acm.org> - 2012-08-26 10:36 -0700
      Re: CAS operations and scalability... "aminer" <aminer@videotron.ca> - 2012-08-26 14:08 -0500
    Re: CAS operations and scalability... "aminer" <aminer@videotron.ca> - 2012-09-13 19:13 -0500

#1033 — CAS operations and scalability...

Hello,


When the CAS operation "goes on the bus", use of CAS can impair scalability.
but CAS can be accomplished locally -- that is, with no bus transactions --
and then it can scale.

If we then change the CAS operation that goes on the bus to a normal store
you'll also see a similar slow-down in terms of coherency bus traffic, CAS
isn't appreciably different than a normal store. Also the lock: prefix 
caused
the LOCK# signal to be asserted, acquiring exclusive access to the bus.
This doesn't scale of course

As you have noticed i  have wrote parallelhashlist (a parallel hashtable),
you can find parallelhashlist here:

http://pages.videotron.com/aminer/

It's a parallel Hashtable with O(1) best case and O(log(n)) worst case
access that uses lock striping and lightweight MREWs(multiple-readers
-exclusive-writer) , this allows multiple threads to write and read
concurently. also parallelhashlist maintains an independant counter , that
counts the number of entries , for each segment of the hashtable and uses
a lock for each counter, this is also for better scalability. and 
parallelhashlist
is scaling very well,  but since it is a parallel hashtable so the 
possibility of
contention is low so why doi need the distributed reader-writer lock of
Dmitry Vyukov inside my parallel hashlist ?

Other than that I have done some tests with the lightweight MREW that i am
using inside my parallelhashlist and i have done also some tests with my
lockfree mpmc fifo queue and what i think is that the CAS is generating
a lot of contention this is is why the lightweight MREW and my lockfree_mpmc
are not scaling , but parallelhashlist is scaling very well cause i am using
lock-striping that is lowering contention.

What are doing Dmitry Vyukov in his distributed rwlock is lowering
the contention using the same method as lock striping that i am using inside
parallelhashlist it is why it is scaling, but there is still a possibility
of contention in his distributed rwlock that can cause a problem to the
scalability if there is too many threads and not a sufficient number of
rwlocks in the Dmitry distributed rwlock to be able to lower the contention.

I have tested parallelhashlist(a parallel hashtable that i have implemented)
with four threads on a quad core and it's giving a very well scaling on both
reads and writes.

Also i have done some scalability tests on my parallelsort library and i 
have
come
to the conclusion that parallel heapsort is better on scalability than
parallel quicksort
cause the P part (of the Amdahl equation) is bigger in parallel heapsort
than in parallel
quicksort, the parallel heapsort is doing more on the parallel part, it's
why it scales better than parallel quicksort, but parallel quicksort is
still
faster than parallel heapsort and parallel merge sort on my tests on a
quad core processor.

And about lockfree_mpmc( a lockfree fifo queue), i have done some tests
and it's not scaling cause when you are using a single thread some variables
are updated locally on the L1 cache but using multiple threads those 
variables are
loaded from the L2 cache and it's more expensive to load them from the L2
cache.and this does generate much more contention

But even though lockfree_mpmc is not scalable, you can increase
the P (parallel) part by doing more of the same: Increase the volume of
data processed by the P part (and therefore the percentage p of time spent
in computing). This is Gustafson's Law and you will get more scalability.

For example i have used the IntToStr() function on each of the four threads
(on
a quad core) on my lockfree_mpmc test programs to convert from and integer
to a string, so i have increased the P (parallel) part and i have got more
scalability,
this is Gustafson's Law, and you have to remember Gustafson's Law ,
this is very important.


You can download my parallel libraries from

http://pages.videotron.com/aminer/




Sincerely,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#1034

 wrote:

"When the CAS operation "goes on the bus", use of CAS can impair 
scalability.
but CAS can be accomplished locally -- that is, with no bus transactions --
and then it can scale.

If we then change the CAS operation that goes on the bus to a normal store
you'll also see a similar slow-down in terms of coherency bus traffic, CAS
isn't appreciably different than a normal store. Also the lock: prefix
caused
the LOCK# signal to be asserted, acquiring exclusive access to the bus.
This doesn't scale of course"


If you take a look at my threadpool engine

http://pages.videotron.com/aminer/

in the TThreadPool.execute() method i am using a
local_balance:=LockedIncLong(balance1) mod FThreadCount;
and this instruction is going on the bus and it can generate a lot of 
contention, so
it does not scale if there is a high arrival rate and a lot of contention on 
it.
But even though it does not scale , in the majority of real world 
applications
the processing rate of the worker threads is lower than the arrival rate to
the TThreadPool.execute(),  so this is not a problem i think.


Thank you,

Amine Moulay Ramdne



"aminer" <aminer@videotron.ca> wrote in message 
news:k1dira$jt9$1@dont-email.me...
>
> Hello,
>
>
> When the CAS operation "goes on the bus", use of CAS can impair 
> scalability.
> but CAS can be accomplished locally -- that is, with no bus 
> transactions --
> and then it can scale.
>
> If we then change the CAS operation that goes on the bus to a normal store
> you'll also see a similar slow-down in terms of coherency bus traffic, CAS
> isn't appreciably different than a normal store. Also the lock: prefix 
> caused
> the LOCK# signal to be asserted, acquiring exclusive access to the bus.
> This doesn't scale of course
>
> As you have noticed i  have wrote parallelhashlist (a parallel hashtable),
> you can find parallelhashlist here:
>
> http://pages.videotron.com/aminer/
>
> It's a parallel Hashtable with O(1) best case and O(log(n)) worst case
> access that uses lock striping and lightweight MREWs(multiple-readers
> -exclusive-writer) , this allows multiple threads to write and read
> concurently. also parallelhashlist maintains an independant counter , that
> counts the number of entries , for each segment of the hashtable and uses
> a lock for each counter, this is also for better scalability. and 
> parallelhashlist
> is scaling very well,  but since it is a parallel hashtable so the 
> possibility of
> contention is low so why doi need the distributed reader-writer lock of
> Dmitry Vyukov inside my parallel hashlist ?
>
> Other than that I have done some tests with the lightweight MREW that i am
> using inside my parallelhashlist and i have done also some tests with my
> lockfree mpmc fifo queue and what i think is that the CAS is generating
> a lot of contention this is is why the lightweight MREW and my 
> lockfree_mpmc
> are not scaling , but parallelhashlist is scaling very well cause i am 
> using
> lock-striping that is lowering contention.
>
> What are doing Dmitry Vyukov in his distributed rwlock is lowering
> the contention using the same method as lock striping that i am using 
> inside
> parallelhashlist it is why it is scaling, but there is still a possibility
> of contention in his distributed rwlock that can cause a problem to the
> scalability if there is too many threads and not a sufficient number of
> rwlocks in the Dmitry distributed rwlock to be able to lower the 
> contention.
>
> I have tested parallelhashlist(a parallel hashtable that i have 
> implemented)
> with four threads on a quad core and it's giving a very well scaling on 
> both
> reads and writes.
>
> Also i have done some scalability tests on my parallelsort library and i 
> have
> come
> to the conclusion that parallel heapsort is better on scalability than
> parallel quicksort
> cause the P part (of the Amdahl equation) is bigger in parallel heapsort
> than in parallel
> quicksort, the parallel heapsort is doing more on the parallel part, it's
> why it scales better than parallel quicksort, but parallel quicksort is
> still
> faster than parallel heapsort and parallel merge sort on my tests on a
> quad core processor.
>
> And about lockfree_mpmc( a lockfree fifo queue), i have done some tests
> and it's not scaling cause when you are using a single thread some 
> variables
> are updated locally on the L1 cache but using multiple threads those 
> variables are
> loaded from the L2 cache and it's more expensive to load them from the L2
> cache.and this does generate much more contention
>
> But even though lockfree_mpmc is not scalable, you can increase
> the P (parallel) part by doing more of the same: Increase the volume of
> data processed by the P part (and therefore the percentage p of time spent
> in computing). This is Gustafson's Law and you will get more scalability.
>
> For example i have used the IntToStr() function on each of the four 
> threads
> (on
> a quad core) on my lockfree_mpmc test programs to convert from and integer
> to a string, so i have increased the P (parallel) part and i have got more
> scalability,
> this is Gustafson's Law, and you have to remember Gustafson's Law ,
> this is very important.
>
>
> You can download my parallel libraries from
>
> http://pages.videotron.com/aminer/
>
>
>
>
> Sincerely,
> Amine Moulay Ramdane.
>
>
>
> 

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

#1037

On 8/26/2012 10:28 AM, aminer wrote:
...
> When the CAS operation "goes on the bus", use of CAS can impair scalability.
> but CAS can be accomplished locally -- that is, with no bus transactions --
> and then it can scale.
...

The problem the hardware faces doing CAS in-cache is that it must make
sure that no other processor can write to the cache line containing the
CAS target during the critical period of the cache.

If multiple processors are attempting CAS operations on the same target
at about the same time there are two costs:

1. The bus traffic to ensure that only one processor is writing to the
cache line at any time, and that processor has the latest value of the
cache line.

2. Repeated CAS operations, due to changes to the CAS target between
doing whatever reads select the value and doing the CAS itself.

You can do a couple of things to limit these costs. One is to make sure
each CAS target is by itself in a cache line. That will reduce the risk
of unnecessary bus traffic due to access to other fields in the same
line. The other is to structure your code to minimize contention for any
one CAS target, so that a CAS has a very high probability of the compare
matching. You can instrument your CAS-using code to see how many CAS
attempts you are making per successful CAS.

Patricia

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

#1038

Hello,


You are right Patricia.



Thank you,
Amine Moulay Ramdane.



"Patricia Shanahan" <pats@acm.org> wrote in message 
news:FsqdncaQ9pkkw6fNnZ2dnUVZ_sGdnZ2d@earthlink.com...
> On 8/26/2012 10:28 AM, aminer wrote:
> ...
>> When the CAS operation "goes on the bus", use of CAS can impair 
>> scalability.
>> but CAS can be accomplished locally -- that is, with no bus 
>> transactions --
>> and then it can scale.
> ...
>
> The problem the hardware faces doing CAS in-cache is that it must make
> sure that no other processor can write to the cache line containing the
> CAS target during the critical period of the cache.
>
> If multiple processors are attempting CAS operations on the same target
> at about the same time there are two costs:
>
> 1. The bus traffic to ensure that only one processor is writing to the
> cache line at any time, and that processor has the latest value of the
> cache line.
>
> 2. Repeated CAS operations, due to changes to the CAS target between
> doing whatever reads select the value and doing the CAS itself.
>
> You can do a couple of things to limit these costs. One is to make sure
> each CAS target is by itself in a cache line. That will reduce the risk
> of unnecessary bus traffic due to access to other fields in the same
> line. The other is to structure your code to minimize contention for any
> one CAS target, so that a CAS has a very high probability of the compare
> matching. You can instrument your CAS-using code to see how many CAS
> attempts you are making per successful CAS.
>
> Patricia 

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

#1071

I wrote:
> And about lockfree_mpmc( a lockfree fifo queue), i have done some tests
> and it's not scaling cause when you are using a single thread some 
> variables
> are updated locally on the L1 cache but using multiple threads those
> variables are
> loaded from the L2 cache and it's more expensive to load them from the L2
> cache.and this does generate much more contention

I mean that it's more expensive to load them from the L2 cache than the L1
cache.

And i wrote: "it does generate a lot of contention", i mean the CAS is a
single point
of access that can generate a lot of contention, in parallelhashlist i am
using
lock striping and distributing the access to many points(ea: many rwlocks,
many CASes)
and this is lowering the contention and this is better for scalability.

What are doing Dmitry Vyukov in his distributed rwlock is also distributing
thje access to many rwlocks using the same method as lock-striping and this
is
lowering the contention and this is better for scalability , it's why my
parallelhashlist
and the Distributed Reader-Writer Mutex 1.03 are scaling very well.

And if you have noticed , there is still a weakness with the Dmitry Vyukov
C++ Distributed Reader-Writer Mutex, cause since he is using
GetCurrentProcessorNumber() he is limiting the array of rwlocks to the
number of avaiblable cores and this is not good i think , cause if you have
many more threads than the avaiblable cores and there is high contention
this will cause the performance to degrade, so i have decided to change
that in my implementation of the Distributed Reader-Writer Mutex 1.03
and i have used a  variable number of rwlocks/MREWs so that you can lower
more the contention and this is better for scalability.



Thank you,
Amine Moulay Ramdane.


"aminer" <aminer@videotron.ca> wrote in message 
news:k1dira$jt9$1@dont-email.me...
>
> Hello,
>
>
> When the CAS operation "goes on the bus", use of CAS can impair 
> scalability.
> but CAS can be accomplished locally -- that is, with no bus 
> transactions --
> and then it can scale.
>
> If we then change the CAS operation that goes on the bus to a normal store
> you'll also see a similar slow-down in terms of coherency bus traffic, CAS
> isn't appreciably different than a normal store. Also the lock: prefix 
> caused
> the LOCK# signal to be asserted, acquiring exclusive access to the bus.
> This doesn't scale of course
>
> As you have noticed i  have wrote parallelhashlist (a parallel hashtable),
> you can find parallelhashlist here:
>
> http://pages.videotron.com/aminer/
>
> It's a parallel Hashtable with O(1) best case and O(log(n)) worst case
> access that uses lock striping and lightweight MREWs(multiple-readers
> -exclusive-writer) , this allows multiple threads to write and read
> concurently. also parallelhashlist maintains an independant counter , that
> counts the number of entries , for each segment of the hashtable and uses
> a lock for each counter, this is also for better scalability. and 
> parallelhashlist
> is scaling very well,  but since it is a parallel hashtable so the 
> possibility of
> contention is low so why doi need the distributed reader-writer lock of
> Dmitry Vyukov inside my parallel hashlist ?
>
> Other than that I have done some tests with the lightweight MREW that i am
> using inside my parallelhashlist and i have done also some tests with my
> lockfree mpmc fifo queue and what i think is that the CAS is generating
> a lot of contention this is is why the lightweight MREW and my 
> lockfree_mpmc
> are not scaling , but parallelhashlist is scaling very well cause i am 
> using
> lock-striping that is lowering contention.
>
> What are doing Dmitry Vyukov in his distributed rwlock is lowering
> the contention using the same method as lock striping that i am using 
> inside
> parallelhashlist it is why it is scaling, but there is still a possibility
> of contention in his distributed rwlock that can cause a problem to the
> scalability if there is too many threads and not a sufficient number of
> rwlocks in the Dmitry distributed rwlock to be able to lower the 
> contention.
>
> I have tested parallelhashlist(a parallel hashtable that i have 
> implemented)
> with four threads on a quad core and it's giving a very well scaling on 
> both
> reads and writes.
>
> Also i have done some scalability tests on my parallelsort library and i 
> have
> come
> to the conclusion that parallel heapsort is better on scalability than
> parallel quicksort
> cause the P part (of the Amdahl equation) is bigger in parallel heapsort
> than in parallel
> quicksort, the parallel heapsort is doing more on the parallel part, it's
> why it scales better than parallel quicksort, but parallel quicksort is
> still
> faster than parallel heapsort and parallel merge sort on my tests on a
> quad core processor.
>
> And about lockfree_mpmc( a lockfree fifo queue), i have done some tests
> and it's not scaling cause when you are using a single thread some 
> variables
> are updated locally on the L1 cache but using multiple threads those 
> variables are
> loaded from the L2 cache and it's more expensive to load them from the L2
> cache.and this does generate much more contention
>
> But even though lockfree_mpmc is not scalable, you can increase
> the P (parallel) part by doing more of the same: Increase the volume of
> data processed by the P part (and therefore the percentage p of time spent
> in computing). This is Gustafson's Law and you will get more scalability.
>
> For example i have used the IntToStr() function on each of the four 
> threads
> (on
> a quad core) on my lockfree_mpmc test programs to convert from and integer
> to a string, so i have increased the P (parallel) part and i have got more
> scalability,
> this is Gustafson's Law, and you have to remember Gustafson's Law ,
> this is very important.
>
>
> You can download my parallel libraries from
>
> http://pages.videotron.com/aminer/
>
>
>
>
> Sincerely,
> Amine Moulay Ramdane.
>
>
>
> 

[toc] | [prev] | [standalone]

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

csiph-web