November 2011 - petsc-dev - mailman3.cels.anl.gov

Re: [petsc-dev] Generality of VecScatter
by Jed Brown 29 Nov '11

29 Nov '11

On Tue, Nov 29, 2011 at 12:53, Dmitry Karpeev <karpeev(a)mcs.anl.gov> wrote: > I understand that any solution requires serialization: atomic reads by the > spinning loop would serialize on that read, > while pthread_cond_wait requires mutex serialization. sigwait serializes > since it clears the signal atomically. > Ultimately, all three rely on atomicity of some sort, but mutexes > apparently have higher overhead for it? > At least the stackoverflow page that suggests the sigwait solution reports > a 40x improvement over the pthread_cond_wait > solution (admittedly, I don't know the details of the sigwait stuff). > I wouldn't consider that stackoverflow post to be authoritative, but there is a large body of literature on lock-free synchronization. Unless there is resource contention, spinning is always the lowest latency choice. All multi-threaded cores have some sort of pause instruction because it's necessary to make that design useful. For this purpose, we should just spin. Note that with sequential consistency, you can also provide information about the next work unit when you activate a thread. For example, you can pass a function pointer.

1 0

Re: [petsc-dev] Generality of VecScatter
by Dmitry Karpeev 29 Nov '11

29 Nov '11

I understand that any solution requires serialization: atomic reads by the spinning loop would serialize on that read, while pthread_cond_wait requires mutex serialization. sigwait serializes since it clears the signal atomically. Ultimately, all three rely on atomicity of some sort, but mutexes apparently have higher overhead for it? At least the stackoverflow page that suggests the sigwait solution reports a 40x improvement over the pthread_cond_wait solution (admittedly, I don't know the details of the sigwait stuff). Dmitry. On Tue, Nov 29, 2011 at 12:40 PM, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > On Nov 29, 2011, at 10:41 AM, Jed Brown wrote: > > > On Tue, Nov 29, 2011 at 10:35, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > > Synchronization between threads frequently involves the use of spin-wait > loops. These loops should make use of the PAUSE instruction to maximize > performance and minimize power consumption. The PAUSE instruction can be > added to application code now, as it is ignored on all known existing Intel > architectures. > > > > Where are going getting this from? > > The very first google hit for "pause instruction spin loop"; looks like > they have the same web maintenance issues PETSc has :-) > > > > > > > > So for Q all I need do is > > > > #define PAUSE > > > > and then use PAUSE in the spin-wait to get similar performance to the > Intel? > > > > > http://software.intel.com/sites/products/documentation/hpc/compilerpro/en-u… > > > > > http://software.intel.com/en-us/articles/introduction-to-hyper-threading-te… > > > > Use the PAUSE Instruction to Optimize Code > > Intel recommends that software developers always use the PAUSE > instruction in spin-wait loops. > > > > Starting with the Intel® Pentium® 4 processor, this recommendation was > made for the benefit of power savings. Executing a PAUSE in a spin-wait > loop forces the spin-wait to finish one iteration of the loop before > starting the next iteration. Halting the spin-wait loop reduces consumption > of non-productive resources - and thus power. > > > > With a Hyper-Threading Technology supported processor, using the PAUSE > instruction optimizes processing of two threads. Pausing the spin-wait loop > frees more resources for the other processor, allowing faster completion of > its thread. > > > > Use OS Synchronization Techniques on Long Waits > > When a thread suspects a thread will take longer than an OS quantum of > time before a lock is released, use OS synchronization techniques to idle > the processor until the lock is released. Idling the Hyper-Threading > Technology supported processor frees the locked processor to use all > resources available to complete its execution. Use OS primitives to release > the lock when thread execution has completed. > > > > If a thread suspects a thread will release a lock within an OS quantum, > use a spin-wait. > >

1 0

Re: [petsc-dev] Generality of VecScatter
by Jed Brown 29 Nov '11

29 Nov '11

On Tue, Nov 29, 2011 at 12:40, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > The very first google hit for "pause instruction spin loop" This is documentation for the first chip to use it. They are asserting that it does not cause illegal-opcode exceptions for prior chips, so it is valid to use unconditionally, even in software that needs to run on older chips. I think this is clear from context (certainly if you had been reading the documented instead of skipping to the end), but it could have been more explicit.

1 0

Re: [petsc-dev] Generality of VecScatter
by Barry Smith 29 Nov '11

29 Nov '11

On Nov 29, 2011, at 10:41 AM, Jed Brown wrote: > On Tue, Nov 29, 2011 at 10:35, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > Synchronization between threads frequently involves the use of spin-wait loops. These loops should make use of the PAUSE instruction to maximize performance and minimize power consumption. The PAUSE instruction can be added to application code now, as it is ignored on all known existing Intel architectures. > > Where are going getting this from? The very first google hit for "pause instruction spin loop"; looks like they have the same web maintenance issues PETSc has :-) > > > So for Q all I need do is > > #define PAUSE > > and then use PAUSE in the spin-wait to get similar performance to the Intel? > > http://software.intel.com/sites/products/documentation/hpc/compilerpro/en-u… > > http://software.intel.com/en-us/articles/introduction-to-hyper-threading-te… > > Use the PAUSE Instruction to Optimize Code > Intel recommends that software developers always use the PAUSE instruction in spin-wait loops. > > Starting with the Intel® Pentium® 4 processor, this recommendation was made for the benefit of power savings. Executing a PAUSE in a spin-wait loop forces the spin-wait to finish one iteration of the loop before starting the next iteration. Halting the spin-wait loop reduces consumption of non-productive resources - and thus power. > > With a Hyper-Threading Technology supported processor, using the PAUSE instruction optimizes processing of two threads. Pausing the spin-wait loop frees more resources for the other processor, allowing faster completion of its thread. > > Use OS Synchronization Techniques on Long Waits > When a thread suspects a thread will take longer than an OS quantum of time before a lock is released, use OS synchronization techniques to idle the processor until the lock is released. Idling the Hyper-Threading Technology supported processor frees the locked processor to use all resources available to complete its execution. Use OS primitives to release the lock when thread execution has completed. > > If a thread suspects a thread will release a lock within an OS quantum, use a spin-wait.

1 0

Re: [petsc-dev] Generality of VecScatter
by Jed Brown 29 Nov '11

29 Nov '11

On Tue, Nov 29, 2011 at 10:35, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > Synchronization between threads frequently involves the use of spin-wait > loops. These loops should make use of the PAUSE instruction to maximize > performance and minimize power consumption. The PAUSE instruction can be > added to application code now, as it is ignored on all known existing Intel > architectures. > Where are going getting this from? > > So for Q all I need do is > > #define PAUSE > > and then use PAUSE in the spin-wait to get similar performance to the > Intel? > http://software.intel.com/sites/products/documentation/hpc/compilerpro/en-u… http://software.intel.com/en-us/articles/introduction-to-hyper-threading-te… *Use the PAUSE Instruction to Optimize Code* Intel recommends that software developers always use the PAUSE instruction in spin-wait loops. Starting with the Intel® Pentium® 4 processor, this recommendation was made for the benefit of power savings. Executing a PAUSE in a spin-wait loop forces the spin-wait to finish one iteration of the loop before starting the next iteration. Halting the spin-wait loop reduces consumption of non-productive resources - and thus power. With a Hyper-Threading Technology supported processor, using the PAUSE instruction optimizes processing of two threads. Pausing the spin-wait loop frees more resources for the other processor, allowing faster completion of its thread. *Use OS Synchronization Techniques on Long Waits* When a thread suspects a thread will take longer than an OS quantum of time before a lock is released, use OS synchronization techniques to idle the processor until the lock is released. Idling the Hyper-Threading Technology supported processor frees the locked processor to use all resources available to complete its execution. Use OS primitives to release the lock when thread execution has completed. If a thread suspects a thread will release a lock within an OS quantum, use a spin-wait.

1 0

Re: [petsc-dev] Generality of VecScatter
by Barry Smith 29 Nov '11

29 Nov '11

On Nov 29, 2011, at 10:31 AM, Jed Brown wrote: > On Tue, Nov 29, 2011 at 10:14, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > In the world Intel is pushing us toward they want us to have SEVERAL threads per core (and IBM BlueGene Q also I think) how is the spinning going to work in that situation. > > This is what the "pause" instruction is for. I don't have docs for the /Q instruction set, but it must have an equivalent. Synchronization between threads frequently involves the use of spin-wait loops. These loops should make use of the PAUSE instruction to maximize performance and minimize power consumption. The PAUSE instruction can be added to application code now, as it is ignored on all known existing Intel architectures. So for Q all I need do is #define PAUSE and then use PAUSE in the spin-wait to get similar performance to the Intel? Barry

1 0

Re: [petsc-dev] Generality of VecScatter
by Jed Brown 29 Nov '11

29 Nov '11

On Tue, Nov 29, 2011 at 10:14, Barry Smith <bsmith(a)mcs.anl.gov> wrote: > In the world Intel is pushing us toward they want us to have SEVERAL > threads per core (and IBM BlueGene Q also I think) how is the spinning > going to work in that situation. This is what the "pause" instruction is for. I don't have docs for the /Q instruction set, but it must have an equivalent.

1 0

Re: [petsc-dev] Generality of VecScatter
by Barry Smith 29 Nov '11

29 Nov '11

On Nov 29, 2011, at 9:08 AM, Jed Brown wrote: > On Tue, Nov 29, 2011 at 08:52, Dmitry Karpeev <karpeev(a)mcs.anl.gov> wrote: > >From what I understand Barry doesn't want the threads to spin. > > Lots of MPI calls spin because it's MUCH lower latency. Unless we have more threads than cores, what is the problem? > > Also, synchronizing through an unguarded memory location seems to create a race conditions. > > Not if writes are atomic. There is always a way to do atomic writes (usually machine-word) because otherwise the operating system could not implement synchronization primitives. > > Isn't cmpxchg instruction-set specific? > > All instruction sets have some analogue of cmpxchg because it's the building block for all other primitives. Shri, I think we need to investigate both the method Dmitry suggested and what Jed suggests. Barry Generally I think of sigs as being pretty slow so I am surprised by the result on the website but hey In the world Intel is pushing us toward they want us to have SEVERAL threads per core (and IBM BlueGene Q also I think) how is the spinning going to work in that situation.

1 0

Re: [petsc-dev] Generality of VecScatter
by Jed Brown 29 Nov '11

29 Nov '11

On Tue, Nov 29, 2011 at 08:52, Dmitry Karpeev <karpeev(a)mcs.anl.gov> wrote: > >From what I understand Barry doesn't want the threads to spin. > Lots of MPI calls spin because it's MUCH lower latency. Unless we have more threads than cores, what is the problem? > Also, synchronizing through an unguarded memory location seems to create a > race conditions. > Not if writes are atomic. There is always a way to do atomic writes (usually machine-word) because otherwise the operating system could not implement synchronization primitives. Isn't cmpxchg instruction-set specific? > All instruction sets have some analogue of cmpxchg because it's the building block for all other primitives.

1 0

Re: [petsc-dev] Generality of VecScatter
by Dmitry Karpeev 29 Nov '11

29 Nov '11

>From what I understand Barry doesn't want the threads to spin. Also, synchronizing through an unguarded memory location seems to create a race conditions. Isn't cmpxchg instruction-set specific? Dmitry. On Tue, Nov 29, 2011 at 8:50 AM, Jed Brown <jedbrown(a)mcs.anl.gov> wrote: > You don't need any of this unless your threads need to actually sleep > instead of spin. I think we can afford to have them spin, so we don't need > any locking. You let the threads continue by doing an ordinary write to a > memory location. (You can do more sophisticated things with cmpxchg, which > you likely need at synchronization points.) > On Nov 29, 2011 8:41 AM, "Dmitry Karpeev" <karpeev(a)mcs.anl.gov> wrote: > >> Barry, >> >> You might want to take a look at this: >> http://stackoverflow.com/questions/2994216/linux-pthread-suspend >> The solution suggested there (Answer 1) is to use sigwait(). Answer 3, >> although not the actual solution, >> explains why the pthread_suspend/pthread_continue-based solution is >> racy. I think this may be a general issue >> with the problem, which requires the use of mutexes. >> >> What example do you use to test this? I'd like to take a look. >> >> Thanks. >> Dmitry. >> >> On Thu, Nov 24, 2011 at 4:10 PM, Jed Brown <jedbrown(a)mcs.anl.gov> wrote: >> >>> On Thu, Nov 24, 2011 at 16:01, Barry Smith <bsmith(a)mcs.anl.gov> wrote: >>> >>>> Yes, but they can only get access to that shared variable one at a >>>> time: first get's it, then second get's it, then third gets, .... Ok for a >>>> couple of cores but not for dozens. >>>> >>>> Take a look at src/sys/objects/pthread.c for the various ways we have >>>> coded for "waking" the threads. Maybe I am missing something but this is >>>> the best Kerry and I could figure out. >>>> >>> >>> What exactly should I be looking at? Can't you have all the threads spin >>> on a normal shared variable (not a mutex) that is only written by the >>> thread that needs to spark them? Or use a fetch-and-add atomic if you want >>> to keep track of how many are running or limit the number? The latter could >>> use a tree to get logarithmic cost, but if they are stored next to each >>> other, you would still have O(P) cache invalidations. >>> >> >>

1 0