[concurrency-interest] visibility vs. cache coherency

Jaroslav Sevcik J.Sevcik at sms.ed.ac.uk
Wed Mar 12 06:47:44 EDT 2008


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
>   



More information about the Concurrency-interest mailing list