Hi Sebastian, Sure! The bulk of LMDA was written by Aparna Kotha (CCd). It computes dependences between all instructions, computes the resulting direction vectors in the function, then associates them all with loops. At a high level, the dependence analysis consults with AliasAnalysis, and ScalarEvolution before resorting to attempting to understand the effective affine expressions and performing dependence tests (e.g., Banerjee). If it cannot rule out a dependence, then it will additionally consult with an ArrayPrivatization analysis to see if an involved memory object can be made thread private. It is probably also worth mentioning that the LMDA has been written not only to function well with IR from source code, but also with low level IR from a binary to IR translator in a separate project. This has required new techniques specific to this problem. Aparna can provide more information on techniques used in our LMDA. -Tim On Sun, Mar 03, 2013 at 09:18:47AM +0100, Sebastian Dreßler wrote:> Hi, > > On 03/03/2013 07:09 AM, Timothy Mattausch Creech wrote: > > [...] > > The main components of the released implementation are loop memory > > dependence analysis and parallel code generation using calls to POSIX > > threads. > > The loop memory dependence analysis sounds very interesting to me. Could > you provide some more information regarding its capabilities? > > > Cheers, > Sebastian > > > -- > Mit freundlichen Grüßen / Kind regards > > Sebastian Dreßler > > Zuse Institute Berlin (ZIB) > Takustraße 7 > D-14195 Berlin-Dahlem > Germany > > dressler at zib.de > Phone: +49 30 84185-261 > > http://www.zib.de/
Hi Tim, On 03/03/2013 06:32 PM, Timothy Mattausch Creech wrote:> [...] > At a high level, the dependence analysis consults with AliasAnalysis, > and ScalarEvolution before resorting to attempting to understand the > effective affine expressions and performing dependence tests (e.g., > Banerjee). If it cannot rule out a dependence, then it will > additionally consult with an ArrayPrivatization analysis to see if an > involved memory object can be made thread private. It is probably > also worth mentioning that the LMDA has been written not only to > function well with IR from source code, but also with low level IR > from a binary to IR translator in a separate project. This has > required new techniques specific to this problem. Aparna can provide > more information on techniques used in our LMDA. >This sounds pretty neat. I was asking, because we currently research methods to model the performance of task execution and loop analysis is rather hard. So maybe we could benefit from this part of AESOP. Anyway, the whole compiler is very interesting for us! Cheers, Sebastian -- Mit freundlichen Grüßen / Kind regards Sebastian Dreßler Zuse Institute Berlin (ZIB) Takustraße 7 D-14195 Berlin-Dahlem Germany dressler at zib.de Phone: +49 30 84185-261 http://www.zib.de/
----- Original Message -----> From: "Timothy Mattausch Creech" <tcreech at umd.edu> > To: "Sebastian Dreßler" <dressler at zib.de> > Cc: "Aparna Kotha" <akotha at umd.edu>, llvmdev at cs.uiuc.edu > Sent: Sunday, March 3, 2013 11:32:49 AM > Subject: Re: [LLVMdev] AESOP autoparallelizing compiler > > Hi Sebastian, > Sure! The bulk of LMDA was written by Aparna Kotha (CCd). It > computes dependences between all instructions, computes the > resulting direction vectors in the function, then associates them > all with loops. > > At a high level, the dependence analysis consults with AliasAnalysis, > and ScalarEvolution before resorting to attempting to understand the > effective affine expressions and performing dependence tests (e.g., > Banerjee). If it cannot rule out a dependence, then it will > additionally consult with an ArrayPrivatization analysis to see if > an involved memory object can be made thread private. It is probably > also worth mentioning that the LMDA has been written not only to > function well with IR from source code, but also with low level IR > from a binary to IR translator in a separate project. This has > required new techniques specific to this problem. Aparna can provide > more information on techniques used in our LMDA.This sounds very interesting; thanks for sharing this with the community. I'd also like to know more about this. Also, out of curiosity, two quick questions: 1. Why are you using the old induction-variable simplification? 2. Are you generating OpenMP runtime calls (I see some omp references in the CodeGenerationPass); if so, for what runtime? Sincerely, Hal> > -Tim > > On Sun, Mar 03, 2013 at 09:18:47AM +0100, Sebastian Dreßler wrote: > > Hi, > > > > On 03/03/2013 07:09 AM, Timothy Mattausch Creech wrote: > > > [...] > > > The main components of the released implementation are loop > > > memory > > > dependence analysis and parallel code generation using calls to > > > POSIX > > > threads. > > > > The loop memory dependence analysis sounds very interesting to me. > > Could > > you provide some more information regarding its capabilities? > > > > > > Cheers, > > Sebastian > > > > > > -- > > Mit freundlichen Grüßen / Kind regards > > > > Sebastian Dreßler > > > > Zuse Institute Berlin (ZIB) > > Takustraße 7 > > D-14195 Berlin-Dahlem > > Germany > > > > dressler at zib.de > > Phone: +49 30 84185-261 > > > > http://www.zib.de/ > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
On Sun, Mar 03, 2013 at 02:06:44PM -0600, Hal Finkel wrote:> ----- Original Message ----- > > From: "Timothy Mattausch Creech" <tcreech at umd.edu> > > To: "Sebastian Dreßler" <dressler at zib.de> > > Cc: "Aparna Kotha" <akotha at umd.edu>, llvmdev at cs.uiuc.edu > > Sent: Sunday, March 3, 2013 11:32:49 AM > > Subject: Re: [LLVMdev] AESOP autoparallelizing compiler > > > > Hi Sebastian, > > Sure! The bulk of LMDA was written by Aparna Kotha (CCd). It > > computes dependences between all instructions, computes the > > resulting direction vectors in the function, then associates them > > all with loops. > > > > At a high level, the dependence analysis consults with AliasAnalysis, > > and ScalarEvolution before resorting to attempting to understand the > > effective affine expressions and performing dependence tests (e.g., > > Banerjee). If it cannot rule out a dependence, then it will > > additionally consult with an ArrayPrivatization analysis to see if > > an involved memory object can be made thread private. It is probably > > also worth mentioning that the LMDA has been written not only to > > function well with IR from source code, but also with low level IR > > from a binary to IR translator in a separate project. This has > > required new techniques specific to this problem. Aparna can provide > > more information on techniques used in our LMDA. > > This sounds very interesting; thanks for sharing this with the community. I'd also like to know more about this. > > Also, out of curiosity, two quick questions: > > 1. Why are you using the old induction-variable simplification? > > 2. Are you generating OpenMP runtime calls (I see some omp references in the CodeGenerationPass); if so, for what runtime? > > Sincerely, > HalHi Hal, 1. We are still using the old indvars simplifcation because we were depending on "-enable-iv-rewrite" and canonical induction variables. I think "-enable-iv-rewrite" is still there in 3.0, but was behaving differently from in 2.9, so we just kept using the 2.9 implementation. 2. We only link to OpenMP (any implementation should be fine) to get the number of threads to use (omp_get_max_threads()). This makes our binaries obey the OMP_NUM_THREADS environment variable, if present. OpenMP is _not_ used for parallelization: AESOP generates pthreads calls and does very lightweight static scheduling of loop iterations at the IR level. One thing to note is that we do not use pthreads' barriers. We still link to a (spinning) barrier implementation which was part of a now-defunct sister project. We should eventually do away with this dependence, but haven't had time yet. Thanks, Tim> > > > > -Tim > > > > On Sun, Mar 03, 2013 at 09:18:47AM +0100, Sebastian Dreßler wrote: > > > Hi, > > > > > > On 03/03/2013 07:09 AM, Timothy Mattausch Creech wrote: > > > > [...] > > > > The main components of the released implementation are loop > > > > memory > > > > dependence analysis and parallel code generation using calls to > > > > POSIX > > > > threads. > > > > > > The loop memory dependence analysis sounds very interesting to me. > > > Could > > > you provide some more information regarding its capabilities? > > > > > > > > > Cheers, > > > Sebastian > > > > > > > > > -- > > > Mit freundlichen Grüßen / Kind regards > > > > > > Sebastian Dreßler > > > > > > Zuse Institute Berlin (ZIB) > > > Takustraße 7 > > > D-14195 Berlin-Dahlem > > > Germany > > > > > > dressler at zib.de > > > Phone: +49 30 84185-261 > > > > > > http://www.zib.de/ > > _______________________________________________ > > LLVM Developers mailing list > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >