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

Groups > comp.arch > #1497 > unrolled thread

Re: What are the various alternate uses for the PC's LSB ?

Back to article view | Back to comp.arch

Contents

  Re: What are the various alternate uses for the PC's LSB ? "Paul A. Clayton" <paaronclayton@gmail.com> - 2011-05-12 08:49 -0700
    Re: What are the various alternate uses for the PC's LSB ? whygee <yg@yg.yg> - 2011-05-13 02:01 +0200
      Re: What are the various alternate uses for the PC's LSB ? "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-05-12 20:32 -0700
        Re: What are the various alternate uses for the PC's LSB ? Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-05-13 12:47 +0200
          Re: What are the various alternate uses for the PC's LSB ? Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2011-05-13 08:44 -0700
            Re: What are the various alternate uses for the PC's LSB ? Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-05-13 19:53 +0200
              Re: What are the various alternate uses for the PC's LSB ? Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2011-05-13 11:36 -0700
                Re: What are the various alternate uses for the PC's LSB ? Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-05-13 22:26 +0200
              Re: What are the various alternate uses for the PC's LSB ? "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-05-14 17:17 -0700
                Re: What are the various alternate uses for the PC's LSB ? Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-05-16 14:22 +0200
                  Re: What are the various alternate uses for the PC's LSB ? "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-05-16 07:38 -0700
            Re: What are the various alternate uses for the PC's LSB ? "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-05-14 17:14 -0700
        Re: What are the various alternate uses for the PC's LSB ? rpw3@rpw3.org (Rob Warnock) - 2011-05-13 07:45 -0500

#1497 — Re: What are the various alternate uses for the PC's LSB ?

On Wednesday, May 11, 2011 8:45:59 PM UTC-4, whygee wrote:
[snip] 
> What's interesting in the MIPS flavor is that (IIRC) there
> is a status bit that is updated so the SW knows if the
> sequence was interrupted so it can rerun it. Here, the
> "critical" sequence is not meant to be interrupted (unless
> it traps because of a fault, too bad) so no need to get
> the status.

Linked Load/Store Conditional (with different names) are 
also used by Alpha (as you surmised), ARM, and Power(PC).
It has the additional semantic of failing if there is 
interference with another thread (it is a very limited 
form of transactional memory).

Blocking interrupts could also be useful modifying special 
purpose registers that require separate read and write 
operations.  

[toc] | [next] | [standalone]

#1512

Paul A. Clayton wrote:
> Linked Load/Store Conditional (with different names) are 
> also used by Alpha (as you surmised), ARM, and Power(PC).
> It has the additional semantic of failing if there is 
> interference with another thread (it is a very limited 
> form of transactional memory).
Yes, it's definitely a RISC technique worth digging.
Simple, elegant, flexible, inspiring.

yg
-- 
http://ygdes.com / http://yasep.org

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

#1522

On 5/12/2011 5:01 PM, whygee wrote:
> Paul A. Clayton wrote:
>> Linked Load/Store Conditional (with different names) are also used by
>> Alpha (as you surmised), ARM, and Power(PC).
>> It has the additional semantic of failing if there is interference
>> with another thread (it is a very limited form of transactional memory).
> Yes, it's definitely a RISC technique worth digging.
> Simple, elegant, flexible, inspiring.
>
> yg

And really only works properly on a snoopy bus.

And even on a snoopy bus can have problems with fairness.  If you aren't 
careful with how you do bus arbitration, one thread can block forever. 
Note: don't assume all processors are running at the same clock speed.

If you want to guarantee fairness forward progress on a machine that 
doesn't have a snoopy bus, you have to implement more mechanisms.  So, 
in the end, LL/SC isn't very RISCy at all.

Let alone a machine where you want to export the atomic RMW to the 
interconnect, so that you can do NYU Ultracomputer style fetch and op 
combining.  Or, heck, even the simple form of RMW coalescing that most 
GPUs provide.

However, LL/SC is a mechanism that allows a lot of different instruction 
sequences to be made atomic.  You want atomic-increment-with-saturation 
at [0,255] ... ?  LL/SC can do that for you.

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

#1532

Andy "Krazy" Glew wrote:
> However, LL/SC is a mechanism that allows a lot of different
> instruction sequences to be made atomic. You want
> atomic-increment-with-saturation at [0,255] ... ? LL/SC can do that
> for you.

_Most_ of these can be handled equally well with traditional CAS
(CMPXCHG*) semantics, it is only the ABA problem which is obviously
easier to avoid with LL/SC.

(earlier you wrote:)
> Let alone a machine where you want to export the atomic RMW to the
> interconnect, so that you can do NYU Ultracomputer style fetch and op
> combining.  Or, heck, even the simple form of RMW coalescing that
> most GPUs provide.

Personally I prefer algorithms which can use XADD, i.e. atomic
fetch_and_add(), specifically because they can provide guaranteed
forward progress, with minimum bus uglyness.

It should also be relatively easy (for hw) to propagate an XADD
operation across a mesh and handle it at the location of the target memory.

It does mean that you have to allow the XADD - updated counter to wrap 
at whatever the natural size is, and handle any masking/special 
processing in the surrounding code. Saturation does not work in this 
scenario, since there's no easy way to get immediately back out of 
saturation:

  253+, 254+, 255+, 255+, 255+, 255-, 254-, 253

(A workaround would be to detect that the current increment caused an 
overflow, then immediately decrement by that amount, but this can 
quickly get into race conditions against other threads. Having one or 
two secondary counters to record the amount of over/underflow could 
work, but that would make it much more complicated to read the current 
value. :-()

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

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

#1543

On 5/13/2011 3:47 AM, Terje Mathisen wrote:

snip

> Personally I prefer algorithms which can use XADD, i.e. atomic
> fetch_and_add(), specifically because they can provide guaranteed
> forward progress, with minimum bus uglyness.

I agree with your preference and would add another reason.  There are 
applications where a system wide unique, guaranteed increasing number is 
exactly what is needed.  Think transaction numbers in some transaction 
systems.  XADD provides this with minimal cost.


> It should also be relatively easy (for hw) to propagate an XADD
> operation across a mesh and handle it at the location of the target memory.

Yes.  Although test and set is perhaps easier to do this with.  But see 
below


> It does mean that you have to allow the XADD - updated counter to wrap
> at whatever the natural size is, and handle any masking/special
> processing in the surrounding code. Saturation does not work in this
> scenario, since there's no easy way to get immediately back out of
> saturation:
>
> 253+, 254+, 255+, 255+, 255+, 255-, 254-, 253
>
> (A workaround would be to detect that the current increment caused an
> overflow, then immediately decrement by that amount, but this can
> quickly get into race conditions against other threads. Having one or
> two secondary counters to record the amount of over/underflow could
> work, but that would make it much more complicated to read the current
> value. :-()

Not having to handle this is the advantage of test and set.  It could 
relatively easily be implemented entirely within the memory chip itself. 
  However, at the cost of that elegance, perhaps a reasonable compromise 
would be to handle the addition within the memory controller chip (or 
part of chip) instead of the RAM chips.  This still avoids the need for 
bus locks/snoops.  It would cost a second transfer at the RAM chips 
themselves, but since many/most RAM to controller interfaces are 64 bits 
wide, it makes the overflow problem small enough that you might be able 
to not implement anything special for it.


-- 
  - Stephen Fuld
(e-mail address disguised to prevent spam)

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

#1547

Stephen Fuld wrote:
> On 5/13/2011 3:47 AM, Terje Mathisen wrote:
>
> snip
>
>> Personally I prefer algorithms which can use XADD, i.e. atomic
>> fetch_and_add(), specifically because they can provide guaranteed
>> forward progress, with minimum bus uglyness.
>
> I agree with your preference and would add another reason. There are
>  applications where a system wide unique, guaranteed increasing
> number is exactly what is needed. Think transaction numbers in some
> transaction systems. XADD provides this with minimal cost.

I know that such numbers are very useful, but I would really prefer to 
avoid the need for them, because they do end up as a global bottleneck.
>
>
>> It should also be relatively easy (for hw) to propagate an XADD
>> operation across a mesh and handle it at the location of the target
>>  memory.
>
> Yes. Although test and set is perhaps easier to do this with. But see
> below

Test&Set, in the form XCHG reg,[mem] is the original x86 sync primitive, 
the main problem is that it only provides a boolean gate, not something 
which can be used as-is.

[snip]
> itself. However, at the cost of that elegance, perhaps a reasonable
> compromise would be to handle the addition within the memory
> controller chip (or part of chip) instead of the RAM chips. This
> still avoids the need for bus locks/snoops. It would cost a second
> transfer at the RAM chips themselves, but since many/most RAM to
> controller interfaces are 64 bits wide, it makes the overflow problem
> small enough that you might be able to not implement anything special
> for it.

I'm currently assuming that any distributed RMW facility has to be 
implemented in the memory controllers...

Terje

-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

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

#1548

On 5/13/2011 10:53 AM, Terje Mathisen wrote:
> Stephen Fuld wrote:
>> On 5/13/2011 3:47 AM, Terje Mathisen wrote:
>>
>> snip
>>
>>> Personally I prefer algorithms which can use XADD, i.e. atomic
>>> fetch_and_add(), specifically because they can provide guaranteed
>>> forward progress, with minimum bus uglyness.
>>
>> I agree with your preference and would add another reason. There are
>> applications where a system wide unique, guaranteed increasing
>> number is exactly what is needed. Think transaction numbers in some
>> transaction systems. XADD provides this with minimal cost.
>
> I know that such numbers are very useful, but I would really prefer to
> avoid the need for them, because they do end up as a global bottleneck.

Absolutely.  But if you can't avoid it, having the lower contention 
(because it is faster and not distributed) of XADD implemented close to 
the memory is a useful advantage.  And in the range of many of today's 
high performance transaction systems (that is in the tens to hundreds of 
thousands of transactions per second), the distributed 
lock-load-add-store-unlock sequence is is getting close to being 
significant, but a single distributed XADD would still be very comfortable.

>>> It should also be relatively easy (for hw) to propagate an XADD
>>> operation across a mesh and handle it at the location of the target
>>> memory.
>>
>> Yes. Although test and set is perhaps easier to do this with. But see
>> below
>
> Test&Set, in the form XCHG reg,[mem] is the original x86 sync primitive,
> the main problem is that it only provides a boolean gate, not something
> which can be used as-is.

Agreed.  I only mentioned it as it is something that could be 
implemented within the memory chips without overflow problems.

> [snip]
>> itself. However, at the cost of that elegance, perhaps a reasonable
>> compromise would be to handle the addition within the memory
>> controller chip (or part of chip) instead of the RAM chips. This
>> still avoids the need for bus locks/snoops. It would cost a second
>> transfer at the RAM chips themselves, but since many/most RAM to
>> controller interfaces are 64 bits wide, it makes the overflow problem
>> small enough that you might be able to not implement anything special
>> for it.
>
> I'm currently assuming that any distributed RMW facility has to be
> implemented in the memory controllers...

As I said above, test and set could be implemented within the memory 
chips, but I agree with you that the advantages of XADD are worth the 
somewhat lower performance than a within RAM chip implementation of test 
and set.

-- 
  - Stephen Fuld
(e-mail address disguised to prevent spam)

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

#1552

Stephen Fuld wrote:
> On 5/13/2011 10:53 AM, Terje Mathisen wrote:
>> I'm currently assuming that any distributed RMW facility has to be
>> implemented in the memory controllers...
>
> As I said above, test and set could be implemented within the memory
> chips, but I agree with you that the advantages of XADD are worth the
> somewhat lower performance than a within RAM chip implementation of test
> and set.

I'm more pragmatic:

I really don't think there's any chance at all to get mass-market priced 
ram modules with built-in RMW support.

Ergo: It has to be in the controller. :-(

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

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

#1581

On 5/13/2011 10:53 AM, Terje Mathisen wrote:
> Stephen Fuld wrote:
>> On 5/13/2011 3:47 AM, Terje Mathisen wrote:
>>
>> snip
>>
>>> Personally I prefer algorithms which can use XADD, i.e. atomic
>>> fetch_and_add(), specifically because they can provide guaranteed
>>> forward progress, with minimum bus uglyness.
>>
>> I agree with your preference and would add another reason. There are
>> applications where a system wide unique, guaranteed increasing
>> number is exactly what is needed. Think transaction numbers in some
>> transaction systems. XADD provides this with minimal cost.
>
> I know that such numbers are very useful, but I would really prefer to
> avoid the need for them, because they do end up as a global bottleneck.
>>
>>
>>> It should also be relatively easy (for hw) to propagate an XADD
>>> operation across a mesh and handle it at the location of the target
>>> memory.
>>
>> Yes. Although test and set is perhaps easier to do this with. But see
>> below
>
> Test&Set, in the form XCHG reg,[mem] is the original x86 sync primitive,
> the main problem is that it only provides a boolean gate, not something
> which can be used as-is.

Nit-pocking:

XCHG is atomic exchange, not test-and-set.

test-and-set is something more primitive.

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

#1614

Andy "Krazy" Glew wrote:
> On 5/13/2011 10:53 AM, Terje Mathisen wrote:
>> Test&Set, in the form XCHG reg,[mem] is the original x86 sync primitive,
>> the main problem is that it only provides a boolean gate, not something
>> which can be used as-is.
>
> Nit-pocking:
>
> XCHG is atomic exchange, not test-and-set.
>
> test-and-set is something more primitive.

Nit-picking indeed:

IMHO xchg is the more primitive, since you need to wrap it in a loop to 
aquire an access token or similar:

   mov ax,1
   ;; lea bx,[flag_variable]
spinloop:
   xchg ax,[bx]
   test ax,ax
    jnz spinloop

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

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

#1617

On 5/16/2011 5:22 AM, Terje Mathisen wrote:
> Andy "Krazy" Glew wrote:
>> On 5/13/2011 10:53 AM, Terje Mathisen wrote:
>>> Test&Set, in the form XCHG reg,[mem] is the original x86 sync primitive,
>>> the main problem is that it only provides a boolean gate, not something
>>> which can be used as-is.
>>
>> Nit-pocking:
>>
>> XCHG is atomic exchange, not test-and-set.
>>
>> test-and-set is something more primitive.
>
> Nit-picking indeed:
>
> IMHO xchg is the more primitive, since you need to wrap it in a loop to
> aquire an access token or similar:
>
> mov ax,1
> ;; lea bx,[flag_variable]
> spinloop:
> xchg ax,[bx]
> test ax,ax
> jnz spinloop
>
> Terje


Terminology check:

dst_or_flag := bit-oriented-test-and-set(location,bitnum) ::
     <atomic>
         tmp := load( location ) ; old value
	dest_or_flag := (tmp >> bitnum) & 1;  old value of bit
         tmp |= 1<<bitnum;
         store( location, tmp )
     </atomic>

dst_or_flag := int-oriented-test-and-set(location) ::
     <atomic>
         tmp := load( location ) ; old value
	dest_or_flag := tmp;  old value of int, or maybe compare to zero
         tmp = 1;
         store( location, tmp )
     </atomic>

dst := xchg(regnew,location)
     <atomic>
         dest := load( location ) ; old value
         store( location, regnew )
     </atomic>

dst := cmpxchg(cmpval,regnew,location)
     <atomic>
         tmp := load( location ) ; old value
         dest := temp
         if( dest == cmpval )
             tmp = regnew
         else
             tmp = tmp
         store( location, tmp )
     </atomic>

The test-and-sets always need to be wrapped in a spinloop to acquire an 
access token or similar.  Called a test-and-set spinloop.

XCHG can be treated as a test-and-set, and wrapped in a spinloop.
Or you can use a Graunke Thakkar lock, and insert onto a queue, no spinloop.

Ditto CMPXCHG, except the non-spinloop queue insert for CMPXCHG is 
better known.

This is why I call test-and-set more primitive: because it typically 
only sets a single bit, or sets an integer to a fixed value, it cannot 
be used for queue insertion.  But is easier to implement externally.

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

#1580

On 5/13/2011 8:44 AM, Stephen Fuld wrote:
> On 5/13/2011 3:47 AM, Terje Mathisen wrote:

> Not having to handle this is the advantage of test and set. It could
> relatively easily be implemented entirely within the memory chip itself.
> However, at the cost of that elegance, perhaps a reasonable compromise
> would be to handle the addition within the memory controller chip (or
> part of chip) instead of the RAM chips. This still avoids the need for
> bus locks/snoops. It would cost a second transfer at the RAM chips
> themselves, but since many/most RAM to controller interfaces are 64 bits
> wide, it makes the overflow problem small enough that you might be able
> to not implement anything special for it.

Long ago ago I described, on this newsgroup, how to generalize any RMW, 
and perform it locally in cache if possible, else in the L2, ... else in 
the memory controller, else in ...

Basically, instead of read/write and the ability to lock a cache line or 
delay snoops, you define an operation RMW(address,size,operation,operand)
at every level of the cache hierarchy that you care too.
I.e. ideally every level.


At the N-th level
RMW(address,size,operation,operand)
    if( !properly_aliged(address,size) ) ...
    if( address is in M or E state ) {
         tmp := read(address,size)
         tmp op= operand
         write(address,size)
    }
    else {
         send to the N+1st level
    }


you can do this all the way out to the memory chip, assuming all 
intervening levels support.

you get the benefit of local caching for synchronization variables if 
they are private to your cache, remote fetch and op if not.


etc.

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

#1538

Andy \"Krazy\" Glew <andy@SPAM.comp-arch.net> wrote:
+---------------
| whygee wrote:
| > Paul A. Clayton wrote:
| >> Linked Load/Store Conditional (with different names) are also used by
| >> Alpha (as you surmised), ARM, and Power(PC).
...
| > Yes, it's definitely a RISC technique worth digging.
| > Simple, elegant, flexible, inspiring.
| 
| And really only works properly on a snoopy bus.
+---------------

Hunh?!? It worked (still works) just fine on SGI's "NUMAlink"
cache-directory-based ccNUMA system, which is certainly *not*
a snoopy bus.

+---------------
| And even on a snoopy bus can have problems with fairness. If you aren't 
| careful with how you do bus arbitration, one thread can block forever. 
+---------------

Well, yes, one has the same fairness issue with LL/SC on SGI's NUMAlink.

+---------------
| However, LL/SC is a mechanism that allows a lot of different instruction 
| sequences to be made atomic.  You want atomic-increment-with-saturation 
| at [0,255] ... ?  LL/SC can do that for you.
+---------------

Yup.


-Rob

-----
Rob Warnock		<rpw3@rpw3.org>
627 26th Avenue		<http://rpw3.org/>
San Mateo, CA 94403

[toc] | [prev] | [standalone]

Back to top | Article view | comp.arch

csiph-web