[concurrency-interest] visibility vs. cache coherency

Boehm, Hans hans.boehm at hp.com
Wed Mar 12 15:25:44 EDT 2008


At the hardware level, my understanding is that a big issue is the presence of write buffers, which may delay making stores visible to the cache that participates in the coherency protocol.  The 1995 tutorial by Adve and Gharachorloo ("Shared Memory Consistency Models: A Tutorial") is another good starting place.

Hans

> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu
> [mailto:concurrency-interest-bounces at cs.oswego.edu] On Behalf
> Of Jaroslav Sevcik
> Sent: Wednesday, March 12, 2008 3:48 AM
> To: rsk at moocat.org
> Cc: Concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] visibility vs. cache coherency
>
> Hi Samuel,
>
> it depends on what you mean by 'visibility problems'. If you
> just mean something that is not sequentially consistent, here
> is a classical example (which is not completely artificial,
> just think of x as some 'data' pointer and of y as a 'ready' flag):
>
> Initially, x=y=0,
> Thread 1: x = 1; y = 1
> Thread 2: r1 = y; r2 = x
>
> The result in question is r1 == 1 && r2 == 0.
>
> Sequential consistency does not allow this. No interleaving
> leads to this result.
>
> On the other hand, cache coherency does not prohibit this
> result in general. Note that processors often implement
> something stronger than cache coherence, so I believe that
> some (many?) cache coherent processors actually prohibit this
> outcome in their memory models. Here is a very short,
> incomplete, but hopefully correct overview (all processors
> below are cache coherent, Java Memory Model is not):
>
> Intel Itanium: Allowed, see "A Formal Specification of Intel
> Itanium Processor Family Memory Ordering",
> http://www.intel.com/design/itanium/downloads/25142901.pdf,
> page 20, Table 4.
>
> Intel 64 (x86), AMD: Prohibited, see  "Intel 64 Architecture
> Memory Ordering White Paper",
> http://www.intel.com/products/processor/manuals/318147.pdf,
> page  8, Table 2.1.
>
> Sparc TSO: Prohibited,  see "The SPARC Architecture Manual,
> Version v9", http://www.sparc.org/standards/SPARCV9.pdf,
> Appendix D. TSO should be strictly stronger  than Intel 64.
>
> Java Memory Model: Allowed. Just commit all the writes first,
> and then all the reads. "Java Language Specification, Third
> Edition", chapter 17
> (http://java.sun.com/docs/books/jls/third_edition/html/memory.html).
>
> Another good source for Intel 64 is Richard Hudson's talk on
> "IA memory ordering", http://www.youtube.com/watch?v=WUfvvFD5tAA.
>
> And of course, there is Doug Lea's cookbook
> (http://g.oswego.edu/dl/jmm/cookbook.html), which contains
> some more links to architecture specifications.
>
> For more in-depth  discussion of cache coherency and its
> difference from other memory models I would recommend the PhD
> dissertation of Jalal
> Kawash: "Limitations and Capabilities of Weak Memory
> Consistency Systems",
> http://pages.cpsc.ucalgary.ca/~kawash/papers/dissertation.pdf.
>
> I hope this helps.
>
> Jaroslav
>
> R Samuel Klatchko wrote:
> >
> > David-
> >
> > Sorry, I didn't explain myself well.  It's not that I don't
> care about
> > ordering and latency; rather, I am just trying to understand why
> > things happen and believe I already understand what causes
> > ordering/latency issues.  But I was always baffled by why
> visibility
> > problems could occur (other then visibility problems caused by
> > compiler/VM optimizations) with cache coherency (everything I have
> > found and read so far on cache coherency not only focus on hardware
> > based, but don't even mention software directed coherency).
> >
> > Thanks for all your help.
> >
> > samuel
> >
> >
> > On Wed, Mar 12, 2008 at 12:49 PM, David Holmes
> > <dcholmes at optusnet.com.au <mailto:dcholmes at optusnet.com.au>> wrote:
> >
> >     Samuel,
> >
> >     If you don't care about latency or ordering issues
> (which tend to
> >     be exactly the things we do care about!) then visibility on a
> >     hardware cache coherent system is not an issue - a write to a
> >     variable will become visible within a bounded time.
> >
> >     I'm not sure which architectures mandate hardware cache
> coherency,
> >     vs. implementations of those architectures that happen
> to provide
> >     them. The Alpha architecture is the main example I know of a
> >     system that supports software coherency. If you need
> more details
> >     I'd suggest visiting a computer architecture forum/newsgroup; or
> >     else go grab the relevant architecture specifications if you can
> >     (IA32, IA64, PPC are readily available online - not sure about
> > SPARC.)
> >
> >     Cheers,
> >     David Holmes
> >
> >         -----Original Message-----
> >         *From:* concurrency-interest-bounces at cs.oswego.edu
> >         <mailto:concurrency-interest-bounces at cs.oswego.edu>
> >         [mailto:concurrency-interest-bounces at cs.oswego.edu
> >
> <mailto:concurrency-interest-bounces at cs.oswego.edu>]*On Behalf
> >         Of *R Samuel Klatchko
> >         *Sent:* Wednesday, 12 March 2008 4:54 PM
> >         *To:* Concurrency-interest at cs.oswego.edu
> >         <mailto:Concurrency-interest at cs.oswego.edu>
> >         *Cc:* dholmes at ieee.org <mailto:dholmes at ieee.org>
> >         *Subject:* Re: [concurrency-interest] visibility vs. cache
> >         coherency
> >
> >
> >         David-
> >
> >         Thanks for the info.
> >
> >         While I know this discussion group prefers to focus on the
> >         JMM/JSR-133, I am looking to understand what is going on at
> >         the hardware level (both because I like to learn how things
> >         work and because I still continue to work in C/C++
> so until it
> >         has a better memory model, how hardware works will
> help me there).
> >
> >         It sounds to me like it is fair to say that if the hardware
> >         you are running on supports hardware cache coherency and if
> >         data is written to memory, there should not be visibility
> >         problems.  What I am wondering about is whether thread 1 can
> >         change memory location L from V to V' yet thread 2 continues
> >         to read the value V from L for an unbounded time.
> >
> >         I am not thinking about short delays due to memory latency
> >         issues or ordering problems.  I am also not thinking about
> >         issues where thread 2 never sees the value from thread 1
> >         because thread 3 also wrote the same memory location around
> >         the same time and thread 2 sees that value.
> >
> >         Finally, does anyone know how prevalent hardware cache
> >         coherent systems are as compared to software directed cache
> >         coherent systems?
> >
> >         Thanks,
> >         samuel
> >
> >
> >         On Wed, Mar 12, 2008 at 5:23 AM, David Holmes
> >         <dcholmes at optusnet.com.au <mailto:dcholmes at optusnet.com.au>>
> >         wrote:
> >
> >             Also you'll find more details/discussion on the Java
> >             Memory Model list:
> >
> >
> >
> http://mailman.cs.umd.edu/mailman/listinfo/javamemorymodel-discussion
> >
> >             The simple (and therefore potentially misleading) answer
> >             is that hardware
> >             cache coherent systems don't introduce
> visibility problems
> >             related to the
> >             operation of memory at the hardware level. Systems that
> >             require software
> >             directed cache coherency (the alpha architecture is an
> >             example) can have
> >             visibility problems if the compiler doesn't
> generate those
> >             coherency
> >             instructions where they are needed.
> >
> >             But aside from the hardware level, visibility
> arises from
> >             the actions of the
> >             VM and in particular the code generated by the JIT. For
> >             example, without
> >             something forcing it to do otherwise (i.e. a
> >             happens-before ordering) the
> >             JIT might cache a read of a field in a register and not
> >             reload it, thereby
> >             missing concurrent updates to that field.
> >
> >             Cheers,
> >             David Holmes
> >
> >             > -----Original Message-----
> >             > From: concurrency-interest-bounces at cs.oswego.edu
> >             <mailto:concurrency-interest-bounces at cs.oswego.edu>
> >             > [mailto:concurrency-interest-bounces at cs.oswego.edu
> >             <mailto:concurrency-interest-bounces at cs.oswego.edu>]On
> >             Behalf Of Larry
> >             > Riedel
> >             > Sent: Wednesday, 12 March 2008 2:03 AM
> >             > To: Concurrency-interest at cs.oswego.edu
> >             <mailto:Concurrency-interest at cs.oswego.edu>
> >             > Cc: R Samuel Klatchko
> >             > Subject: Re: [concurrency-interest]
> visibility vs. cache
> >             coherency
> >             >
> >             >
> >             >
> >             > > there does not appear to be a way to search
> >             > > the list archives.  I also did some googling
> >             >
> >             > I think adding this to the google search may help
> >             >     concurrency-interest site:cs.oswego.edu
> >             <http://cs.oswego.edu>
> >             >
> >             >
> >             > Larry
> >             >
> >             > _______________________________________________
> >             > Concurrency-interest mailing list
> >             > Concurrency-interest at altair.cs.oswego.edu
> >             <mailto:Concurrency-interest at altair.cs.oswego.edu>
> >             >
> >
> > http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
> >
> >
> >
> >
> ----------------------------------------------------------------------
> > --
> >
> > _______________________________________________
> > Concurrency-interest mailing list
> > Concurrency-interest at altair.cs.oswego.edu
> > http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
> >
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>



More information about the Concurrency-interest mailing list