llvm dev - Jul 2007 - [LLVMdev] Time to think about a concurrency-aware LLVM memory model?

Hi,

looking at the discussions about atomic operations, we could also (and 
perhaps we should) discuss how a concurrency-aware memory model for LLVM 
should look like.

One could draw the analogy that the mapping between algorithm-level 
concurrent algorithms and the HW atomic operations is like compiling to a 
specific architecture. There are several optimizations possible that are 
directly driven or constrained by inter-thread communication etc.
Examples are of course traditional concurrent algorithms with CAS, 
reordering constraints etc, but there are much more advanced optimizations 
and possibilities for features if you really look at HPC stuff, parallel 
programs, or reliability.

Are there any plans yet, people actively working on that, or are just 
interested in this area? If so, do you have anything that you could share?

Perhaps it's too early for thinking about that, but it is an important 
problem.


torvald

I agree this is an important problem, but the goals here need to be  
defined carefully.

Defining a single memory model (or a set of models) for the LLVM IR  
would be a long and complex process and probably only worthwhile for  
projects that use LLVM to build a complete persistent bytecode  
language (with parallel features) and virtual machine.  Note that the  
LLVM infrastructure has features, like the IR definition and the JIT,  
to build such a language and VM, but many projects don't use those  
and of the ones that do (like the MacOS LLLVM JIT), I don't know if  
any are parallel.

For correctly compiling and optimizing multithreaded programs in  
static compilers, the IR somehow needs to capture the *source  
language* and *target* memory models and ensure that the former is  
correctly mapped to the latter.  That can be much more flexible (and  
hopefully easier in the short term, at least for C/C++) than defining  
a single intermediate memory model for the IR.

This is also partly complicated by the fact that the language-level  
memory models are both complex and still evolving.  Both C++ and C#  
have working groups defining (or redefining) the memory models for  
those languages, similar to what was done recently for Java.  The  
Java model is described in a POPL 2005 paper:
http://portal.acm.org/citation.cfm? 
id=1040305.1040336&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618

Just my 2 cents...

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.org


On Jul 13, 2007, at 10:27 AM, Torvald Riegel wrote:
> Hi,
>
> looking at the discussions about atomic operations, we could also (and
> perhaps we should) discuss how a concurrency-aware memory model for  
> LLVM
> should look like.
>
> One could draw the analogy that the mapping between algorithm-level
> concurrent algorithms and the HW atomic operations is like  
> compiling to a
> specific architecture. There are several optimizations possible  
> that are
> directly driven or constrained by inter-thread communication etc.
> Examples are of course traditional concurrent algorithms with CAS,
> reordering constraints etc, but there are much more advanced  
> optimizations
> and possibilities for features if you really look at HPC stuff,  
> parallel
> programs, or reliability.
>
> Are there any plans yet, people actively working on that, or are just
> interested in this area? If so, do you have anything that you could  
> share?
>
> Perhaps it's too early for thinking about that, but it is an important
> problem.
>
>
> torvald
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Friday 13 July 2007 18:46, Vikram S. Adve wrote:
> Defining a single memory model (or a set of models) for the LLVM IR
> would be a long and complex process and probably only worthwhile for
> projects that use LLVM to build a complete persistent bytecode
> language (with parallel features) and virtual machine.  Note that the
> LLVM infrastructure has features, like the IR definition and the JIT,
> to build such a language and VM, but many projects don't use those
> and of the ones that do (like the MacOS LLLVM JIT), I don't know if
> any are parallel.
>
> For correctly compiling and optimizing multithreaded programs in
> static compilers, the IR somehow needs to capture the *source
> language* and *target* memory models and ensure that the former is
> correctly mapped to the latter.  That can be much more flexible (and
> hopefully easier in the short term, at least for C/C++) than defining
> a single intermediate memory model for the IR.
If the IR would have to capture at least all the source language models, 
then it seems as if we still would get a single memory model for the IR. 
This of course only applies if we want the IR to really be a unification of 
all the source languages (which might not be a sensible goal).
So, IMHO, we would at least need a meta-model if we want the IR to be 
universal w.r.t. concurrency (i.e., provide more than architecture-specific 
mechanisms). This should be even more the case if hardware supports more 
than CAS etc. in the future.


Torvald