On 09/12/2011 04:28 PM, Sebastian Pop wrote:> Hi Alexandra, > > On Thu, Sep 8, 2011 at 13:53, Jimborean Alexandra<xinfinity_a at yahoo.com> wrote: >> I had a look at the CodeGeneration from Polly. Is it possible to use it >> without creating the Scops, by transforming it into a LoopPass? > > Yes. If you don't want to use the autopar of Polly and just rely on > the pragmas inserted by the programmer, you don't need SCoPs. > You can have the parallel code generation part of Polly working as > a LoopPass.Are you sure about this? In CodeGeneration we basically translate a CLooG AST into LLVM-IR. Without a CLooG AST this does not work.> If you want to use the auto-parallelization part of Polly, you have to > to restrict the form of the code on which data dependences can be > computed: this is done by using SCoPs (Static Control Parts).In Polly we just generate OpenMP calls, if we need them. We do not provide a generic OpenMP infrastructure (Something nice to have in LLVM and where I would love to contribute). However, such a generic infrastructure has a broader SCoP than the single specific OpenMP pattern we implemented in Polly. Cheers Tobi
On Mon, Sep 12, 2011 at 10:44, Tobias Grosser <tobias at grosser.es> wrote:>> You can have the parallel code generation part of Polly working as >> a LoopPass. > > Are you sure about this? In CodeGeneration we basically translate a CLooG > AST into LLVM-IR. Without a CLooG AST this does not work.I mean you could rewrite that code to work on a per loop basis, like graphite does: flag the parallel loops in the code generation of polly and then independently of polly, as a LoopPass, iterate over all the loops and code generate the parallel ones. Sebastian
On 09/12/2011 04:56 PM, Sebastian Pop wrote:> On Mon, Sep 12, 2011 at 10:44, Tobias Grosser<tobias at grosser.es> wrote: >>> You can have the parallel code generation part of Polly working as >>> a LoopPass. >> >> Are you sure about this? In CodeGeneration we basically translate a CLooG >> AST into LLVM-IR. Without a CLooG AST this does not work. > > I mean you could rewrite that code to work on a per loop basis, like > graphite does: flag the parallel loops in the code generation of polly > and then independently of polly, as a LoopPass, iterate over all the > loops and code generate the parallel ones.Yes, that's true and probably a good idea. It is more work as generating it directly in Polly, but it facilitates reuse of code. We can probably reuse quite a bit of the code in the existing OpenMP code generation. We (or actually someone) may work on three things: 1) The high level OpenMP intrinsics that can be lowered to actual library calls This can be reused by an clang OpenMP extensions as well as by polly directly. 2) An OpenMP builder, that allows to build OpenMP loops from scratch 3) The actual parallelizer, that takes an LLVM-IR loop and parallelizes it with OpenMP intrinsics. Cheers Tobi
Thanks for your ideas. Polly looked interesting as it seems it has already introduced the basic support for OpenMP that I need. But indeed, it seems difficult to apply the same code on a regular LLVM loop, instead of a SCoP. What I am working on is speculative parallelism, so I cannot provide the SCoPs required by Polly. I analyze the loops and try to parallelize them speculatively at the LLVM IR level. So I am searching for the easiest (and possibly fastest) way to create parallel code. I was not planning to reimplement the OpenMP support you provide, as I was hoping to reuse it. Maybe we can further discuss which solution is better and how difficult it is to adapt the parallel code generation from Polly for regular loops. What I am looking for is a pass that can automatically build the structure of parameters required for the thread creation and execution, and modify the loop code accordingly. Namely, to load the parameters necessary for the thread into a structure and replace the use of these values inside the loop with the corresponding field in the structure. Similarly, once the threads finish the execution to update the values of the variables with the correct values from the structure. Also, the loop code has to be modified to execute only the slice allocated to the thread. I did not go yet into further details on the private and shared variables between the threads and other OpenMP features. As far as I know this code is not yet available in LLVM. Do you think the parallel code generation of Polly can be adapted to perform this? My work is not focused on adding OpenMP support in LLVM, but I was looking for codes that already enable parallelism in the LLVM IR. Surely, if necessary I will work on building the code and inserting calls to the gomp library, to parallelize regular loops. In that case, we can discuss the best approach to stay general and to meet all our requirements. Alexandra ________________________________ From: Tobias Grosser <tobias at grosser.es> To: Sebastian Pop <sebpop at gmail.com> Cc: Jimborean Alexandra <xinfinity_a at yahoo.com>; "llvmdev at cs.uiuc.edu" <llvmdev at cs.uiuc.edu>; polly-dev at googlegroups.com Sent: Monday, September 12, 2011 5:44 PM Subject: Re: [LLVMdev] multi-threading in llvm On 09/12/2011 04:28 PM, Sebastian Pop wrote:> Hi Alexandra, > > On Thu, Sep 8, 2011 at 13:53, Jimborean Alexandra<xinfinity_a at yahoo.com> wrote: >> I had a look at the CodeGeneration from Polly. Is it possible to use it >> without creating the Scops, by transforming it into a LoopPass? > > Yes. If you don't want to use the autopar of Polly and just rely on > the pragmas inserted by the programmer, you don't need SCoPs. > You can have the parallel code generation part of Polly working as > a LoopPass.Are you sure about this? In CodeGeneration we basically translate a CLooG AST into LLVM-IR. Without a CLooG AST this does not work.> If you want to use the auto-parallelization part of Polly, you have to > to restrict the form of the code on which data dependences can be > computed: this is done by using SCoPs (Static Control Parts).In Polly we just generate OpenMP calls, if we need them. We do not provide a generic OpenMP infrastructure (Something nice to have in LLVM and where I would love to contribute). However, such a generic infrastructure has a broader SCoP than the single specific OpenMP pattern we implemented in Polly. Cheers Tobi -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110912/3ed4a2c8/attachment.html>
On 09/12/2011 05:28 PM, Jimborean Alexandra wrote:> Thanks for your ideas. > > Polly looked interesting as it seems it has already introduced the basic > support for OpenMP that I need. But indeed, it seems difficult to apply > the same code on a regular LLVM loop, instead of a SCoP. > > What I am working on is speculative parallelism, so I cannot provide the > SCoPs required by Polly. I analyze the loops and try to parallelize them > speculatively at the LLVM IR level. So I am searching for the easiest > (and possibly fastest) way to create parallel code. I was not planning > to reimplement the OpenMP support you provide, as I was hoping to reuse > it. Maybe we can further discuss which solution is better and how > difficult it is to adapt the parallel code generation from Polly for > regular loops.Sure, let's do this. We can also have a chat this Friday on Euro-LLVM.> What I am looking for is a pass that can automatically build the > structure of parameters required for the thread creation and execution, > and modify the loop code accordingly. Namely, to load the parameters > necessary for the thread into a structure and replace the use of these > values inside the loop with the corresponding field in the structure. > Similarly, once the threads finish the execution to update the values of > the variables with the correct values from the structure. Also, the loop > code has to be modified to execute only the slice allocated to the > thread. I did not go yet into further details on the private and shared > variables between the threads and other OpenMP features.I would also like to have such a pass. It is more complicated as the code in Polly right now, but most probably worth the effort.> As far as I know this code is not yet available in LLVM. Do you think > the parallel code generation of Polly can be adapted to perform this?Yes and No. I think we should be able to extract the generic functions to build the new OpenMP loop structure, the parameter structures and the function calls. With those we could create an OpenMPBuilder as we today have an LLVM-IR builder. Based on this, building a pass that translates a regular LLVM-IR loop into a OpenMP parallelized one should not be too difficult. (Especially, as you perform speculative parallelization and you do not need any dependency analysis) > My> work is not focused on adding OpenMP support in LLVM, but I was looking > for codes that already enable parallelism in the LLVM IR. Surely, if > necessary I will work on building the code and inserting calls to the > gomp library, to parallelize regular loops. In that case, we can discuss > the best approach to stay general and to meet all our requirements.Yes, I assume there is no finished solution available. Though, I am interested in work to get one. Cheers Tobi