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

Groups > comp.arch > #4323

Re: LL/SC (load-linked/store-conditional)

Show all headers | View raw

On 10/20/2011 3:25 PM, Brett Davis wrote:
> In article<4E87DB97.4050607@SPAM.comp-arch.net>,
>   "Andy \"Krazy\" Glew"<andy@SPAM.comp-arch.net>  wrote:
>
>> http://semipublic.comp-arch.net/wiki/Load-linked/store-conditional_(LL/SC)
>>
>> === The best of both worlds? ===
>>
>> Let me end this section by describing a hybrid implementation of the
>> CISC atomic RMWs that combines the best of both worlds wrt [[local and
>> remote atomic RMWs]].
>>
>>       [[LOCK FETCH-AND-OP mem]]
>>            oldval := [[load-locked/fetch-and-op]] M[addr]
>>            newtmp := oldval OP src1
>>            [[store-unlock/fetch-and-op]] M[addr] := newtmp
>>            return oldval
>>
>> If M[addr] is exclusive in the locak cache, then the
>> [[load-locked/fetch-and-op]] and [[store-unlock/fetch-and-op]]
>> are equivalent to ordinary [[load-locked]] and [[store-unlock]].
>>
>> If M[addr]] is not present in the local cache, then
>> [[load-locked/fetch-and-op]] is equivalent to sending a remote atomic
>> RMW fetch-and-op command to the external network. The
>> [[store-unlock/fetch-and-op]] may then become a NOP (although it may be
>> used for bookkeeping purposes).
>>
>> If M[addr] is present in the local cache in a shared state, then we
>> *COULD* perform the atomic RMW both locally and remotely. The remote
>> version might invalidate or update other copies.  However, if the
>> operation is supposed to be [[serializing]], then the local update
>> cannot proceed without coordinating with the remote.
>
> I am kind of perplexed that you spent so much time on what seems to
> be completely obsolete lock primitives.

(1) comp-arch.net is not just supposed to be new ideas. It is also 
supposed to be a collection of important old ideas. Especially since the 
wheel of reincarnation turns around and around in our business.

One of the big reasons I am trying to write comp-arch.net (which is now 
on hold) is that I got tired of seeing old ideas be recycled, and 
claimed to be new.  This happens particularly for ideas that went a bit 
beyond the state of the art at the last turn of the wheel of 
reincarnation, so that they never got into textbooks, and might not have 
been patented, which get reinvented 20 years later.

(2) Although I am not so sure as you are that plain old locking is now 
obsolete.

Background: my MS thesis contained a survey of synchronization 
primitives back in 1985. People back then told me that RMWs were 
obsolete - that LL/SC, and the multiple location versions of LLn/SCn, 
and transactional memory like the IBM 801 original RISC memory system, 
would eliminate locking.

Didn't happen then.  If it's going to happen now, my question is "What's 
changed? Why will this technology that failed to take off in the past 
take off now?  What's different."

And, oh, yes, I have been defined at least one transactional memory 
protocol that was under serious consideration for implementation.  As 
well as several that were further away from consideration. And I have 
been involved in supercomputing projects at massive scale.

I.e. I have a lot of experience in synchronization.  But most of my 
experience has been that sexy academic ideas are proposed - and then fail.

E.g. I once had an interesting long discussion with one of the original 
IBM database people who described why the old IBM 801 processor version
of implicitly locked memory failed.  As he put it, it was a dumb 
programmer play.  Any good programmer with locks could beat 801 memory. 
  I fear the same thing may happen again with transactional memory.   So 
what has changed?  Perhaps the number of dumb programmers writing 
parallel code has changed.

By the way, the most promising sign of interest for TM is IBM's placing 
it in BlueGene/Q.

It would be even more promising if Oracle(Sun) implemented TM. That 
would be real world.

> AMD has proposed (implemented?) a page locking system that is far
> more efficient. In the real world to get work done you will need
> several locks (each in its own page often?) and then you need to
> access the data that is locked, in yet another page of memory.

I am not sure what you are talking about.

ASF? - the Advanced Synchronization Facility" Mitch has discussed here? 
Or something else?

ASF is not page locked. ASF amounts to transactional memory, with a 
small number of cache lines.

--

By the way, one of the things I observed in my MS thesis survey was that 
there were a lot of proposals for "lock pages" and/or special pages 
where a lot of locks would live, with optimized memory/cache protocols. 
   I am not aware of anyone proposing this now, but perhaps I missed 
something.

These proposals failed, both back in the 1980s, but also in more recent 
studies, because people like being able to colocate the locks with the 
data.  Heck, they don't like the locks being in separate cache lines, 
which is pretty much required for performance, let alone in separate pages.

The other thing is that locks often cover complex datastructures.  They 
don't cover just a few contiguous memory locations.

But, like I said, I am not aware of any "lock pages" proposal, or even 
any "page locking" proposal, so I won't continue to discuss this.  Ccahe 
line granularity transactional memory, on the other hand, is popular, or 
at least was a few years ago.

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

Thread

LL/SC (load-linked/store-conditional) "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-01 20:33 -0700
  Re: LL/SC (load-linked/store-conditional) Brett Davis <ggtgp@yahoo.com> - 2011-10-20 17:25 -0500
    Re: LL/SC (load-linked/store-conditional) "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-21 22:50 -0700
      Re: LL/SC (load-linked/store-conditional) Brett Davis <ggtgp@yahoo.com> - 2011-10-22 18:22 -0500
        Re: LL/SC (load-linked/store-conditional) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-23 13:53 +0200
      Re: LL/SC (load-linked/store-conditional) George Neuner <gneuner2@comcast.net> - 2011-10-24 11:34 -0400
        Re: LL/SC (load-linked/store-conditional) Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-24 17:47 +0200
      Re: LL/SC (load-linked/store-conditional) MitchAlsup <MitchAlsup@aol.com> - 2011-10-26 18:10 -0700
  Re: LL/SC (load-linked/store-conditional) jacko <jackokring@gmail.com> - 2011-10-27 07:57 -0700

csiph-web