Tsingray Liu
2012-Mar-24 13:47 UTC
[LLVMdev] GSoC2012 proposal -- A new Back-end for polyhedral Optimization framework for LLVM (Polly)
Hi all,
My name is Qingrui Liu, a student at Sun Yat-sen University, China. I
have been working on high level synthesis project which is implemented as a
back-end of LLVM, in the last two years.When I want to use Polly to
generate parallel LLVM-IR from Polly-IR for me as input to my high level
synthesis tools at the begining of this year, I found that Polly's back-end
is not flexible and modular enough to allow user adding new platform
support. So I am going to improve the existing back-end to an adaptive and
modular back-end which will unleash the power of Polly to other projects.
To be short, I plan to implement my proposal in steps as follows:
1. refactor the existing back-end to a preliminary modular back-end.
2. Add A CodeGen adapter, abstract away the detail of CLAst.
3. Implementation of Specific code generation class to the new back-end. In
this phase, I am going to implement a SIMD code generation class.
An ultimate construction of the new backend will be like the figure below:
[Original Polly codegeneration pass] [Click codegeneration[1]] [whole
function vectorize codegeneration[2]], ....
\
| /
\
| /
\
| /
\
| /
\
| /
CodeGen
adapter
/
\
/
\
/
\
Cloog AST infrastructure
XXX AST infrastructure ...
\
/
\
/
\
/
SCOP
(Polly IR)
After the new backend is done, I think it will easy for other developers to
implement a code generation pass which will meet the requirements of their
platforms or LLVM back-ends. So the optimized LLVM-IR could be passed to
the ordinary LLVM back-ends, such as the high level synthesis back-end I
mentioned above. It will be a great help to both the developers and LLVM.
Tobias Grosser and Ether, who are the contributors of Polly, have assented
to be my mentor, If my proposal is approved. Is this idea good enough for
the Google summer of code? If it is, I am going to write a proposal for it.
Any suggestion is appreciated.
Sincerely,
Qingrui Liu
[1]http://supertech.csail.mit.edu/cilk/
[2]http://www.cdl.uni-saarland.de/projects/wfv/
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120324/c9b81731/attachment.html>
Tobias Grosser
2012-Mar-29 21:52 UTC
[LLVMdev] GSoC2012 proposal -- A new Back-end for polyhedral Optimization framework for LLVM (Polly)
Hi Qingrui Liu, sorry for replying slowly. Here some comments: On 03/24/2012 02:47 PM, Tsingray Liu wrote:> Hi all, > My name is Qingrui Liu, a student at Sun Yat-sen University, China. > I have been working on high level synthesis project which is implemented > as a back-end of LLVM, in the last two years. When I want to use Polly to > generate parallel LLVM-IR from Polly-IR for me as input to my high level > synthesis too ls at the begining of this year, I found that Polly's > back-end is not flexible and modular enough to allow user adding new > platform support.You are right adding new platforms is probably not as straightforward as it could be and especially two months ago the Polly SIMD/OpenMP/Scalar code generation was strongly coupled. That made the code difficult to understand and to adapt. In the last weeks I restructured the code generation to remove the strong connection between those three. The situation should now be a lot better, even though there may still be possibilities to improve it.> So I am going to improve the existing back-end to an > adaptive and modular back-end which will unleash the power of Polly to > other projects.This sentence sounds very nice, but it is actually not very descriptive. The problem here is that it stands in the empty space. There are a many ways to modularize code. Some of them may be helpful and good as they can improve the structure of the code and can simplify the addition of new features. However, modularization can also be counterproductive as it may add unnecessary overhead that complicates the understanding of the code (See first answer here [1]). Making the back end structure easier to extend is a good thing. However, we should make sure we understand the needs of possible back ends such that we can choose a modularization that matches these needs. This means simple to understand, but still flexible and well structured.> To be short, I plan to implement my proposal in steps as follows: > 1. refactor the exis ting back-end to a preliminary modular back-end.I think here and later in your proposal you should explain: - What are the problems with the current code? I do not say there are no problems, but to judge your proposal it is necessary to understand what you want to improve. - What changes you want to perform here? Do you want to move classes, define new interfaces, split some functionality into new classes, ...? (You do not even propose the perfect solution. Feel free to say there are several solutions, which benefits they have and what still needs to be investigated to decide which is best. You can even state you have no solution for a problem, but you plan a week to think about it. For such a proposal it is more important that people see you understood the problems and that you have an idea of how to approach them. In case you are unsure about something, it is better to say this and give a plan how you will proceed to find a solution than to propose a solution you are not yet sure about)> 2. Add A CodeGen adapter, abstract away the detail of CLAst.How would this look like? What would be the difference to the clast? Again, I do not say we don't need this, but it would be helpful if you can express why this is needed and what features it should have. In general I prefer to have as little code as possible. That means for every code we add there needs to be an obvious benefit. A solution without a CodeGen adapter may be to extract all the functionality within the clast into helper classes, create a very simple clast walker and call the helper classes there. We can do exactly the same for another new_codegen_ast, without having to define an CodeGen adapter. This does not need to be the better solution, but this is a possible alternative.> 3. Implementation of Specific code generation class to the new back-end. > In this phase, I am going to implement a SIMD code generation class.It would be great if you could make sure that your plan consists of gradual improvements. This means to build up as little parallel infrastructure as possible. At best, you add your improvements directly the current code generation. This will ensure it is properly tested and it matches the needs we have. I especially want to be sure we do not end up in a situation where the OpenMP code generation still works in the old infrastructure and SIMD is done in the new one. Better make the old infrastructure gradually become the new one.> An ultimate construction of the new backend will be like the figure below: > > [Original Polly codegeneration pass] [Click codegeneration[1]] [whole > function vectorize codegeneration[2]], .... > \ > | / > \ > | / > \ > | / > \ > | / > \ > | / > > CodeGen adapter > > / \ > / > \ > / > \ > Cloog AST infrastructure > XXX AST infrastructure ... > \ > / > \ > / > \ > / > > SCOP (Polly IR)I have currently no idea how your CodeGen adapter will look like. And I have especially no idea how you plan to perform whole function vectorization and click code generation based on Polly. Some examples would definitely help.> After the new backend is done, I think it will easy for other developers > to implement a code generation pass which will meet the requirements of > their platforms or LLVM back-ends. So the optimized LLVM-IR could be > passed to the ordinary LLVM back-ends, such as the high level synthesis > back-end I mentioned above. It will be a great help to both the > developers and LLVM.In general I would rather emphasize in your proposal the individual steps necessary, than to build everything around a currently not yet described 'CodeGen adapter'.> Tobias Grosser and Ether, who are the contributors of Polly, have > assented to be my mentor, If my proposal is approved. Is this idea good > enough for the Google summer of code? If it is, I am going to write a > proposal for it. Any suggestion is appreciated.I think working on the back end of Polly is a good idea. There is still a lot of stuff that needs to be done there and I am sure a good proposal can be written for this. However, the best thing you can do is to start to write your proposal. Because only by doing this you will start to get into Polly and to understand what kind of problems exist and how you could solve them. Listing the problems, finding examples, possible solutions and creating some timeline to implement this will help here a lot. I am glad to give feedback (and promise to be reactive the days up to the deadline). Besides your own ideas, you may also consider the following points: - Extract the clast logic in a simple helper class (as proposed by ether and you) [4] - Removing the independent blocks pass [5] - Integrate a new code generator We are planning to work on a new code generator that will solve several issues. Using your modularization to integrate this code generator would be a perfect use case. To have an idea what I think a proposal might look like you can have a look at my proposal a couple of years ago [2]. Ether should also have his old proposal. As it was accepted it was apparently good enough. ;-) Another hint. It is in general very good if you already contributed some code. Fixing one of the existing Polly bugs would be a good start. This one might not be too difficult [3]. (Let me know if you need help). Cheers Tobi [1] http://stackoverflow.com/questions/2338656/when-is-abstraction-and-modularization-a-bad-practice-in-programming [2] http://students.fim.uni-passau.de/~grosser/gcc_soc/ [3] http://llvm.org/bugs/show_bug.cgi?id=12311 [4] http://llvm.org/bugs/show_bug.cgi?id=12406 [5] http://llvm.org/bugs/show_bug.cgi?id=12398
Tsingray Liu
2012-Apr-04 12:21 UTC
[LLVMdev] GSoC2012 proposal -- A new Back-end for polyhedral Optimization framework for LLVM (Polly)
Hi Tobi, Thank you very much for the elaborate advises and sorry for the long delay. I have kept thinking your advises and investigate more detail of the existing code of Polly. Now, I re-evaluate my proposal and something interesting is added to the new one. ：） On Fri, Mar 30, 2012 at 5:52 AM, Tobias Grosser <tobias at grosser.es> wrote:> Hi Qingrui Liu, > > sorry for replying slowly. > > Here some comments: > > > On 03/24/2012 02:47 PM, Tsingray Liu wrote: > >> Hi all, >> My name is Qingrui Liu, a student at Sun Yat-sen University, China. >> I have been working on high level synthesis project which is implemented >> as a back-end of LLVM, in the last two years. When I want to use Polly to >> >> generate parallel LLVM-IR from Polly-IR for me as input to my high level >> synthesis too ls at the begining of this year, I found that Polly's >> >> back-end is not flexible and modular enough to allow user adding new >> platform support. >> > > You are right adding new platforms is probably not as straightforward as > it could be and especially two months ago the Polly SIMD/OpenMP/Scalar code > generation was strongly coupled. That made the code difficult to understand > and to adapt. In the last weeks I restructured the code generation to > remove the strong connection between those three. The situation should now > be a lot better, even though there may still be possibilities to improve it. > > Yes, I see the appreciable improvement you did. That's great.> > So I am going to improve the existing back-end to an >> adaptive and modular back-end which will unleash the power of Polly to >> other projects. >> > > This sentence sounds very nice, but it is actually not very descriptive. > The problem here is that it stands in the empty space. There are a many > ways to modularize code. Some of them may be helpful and good as they > can improve the structure of the code and can simplify the addition of new > features. However, modularization can also be counterproductive as it may > add unnecessary overhead that complicates the understanding of the code > (See first answer here [1]). > > Making the back end structure easier to extend is a good thing. However, > we should make sure we understand the needs of possible back ends such that > we can choose a modularization that matches these needs. > This means simple to understand, but still flexible and well structured. > >Sorry, maybe it is too abstract for people to understand what is the power underlying the Polly. Now, Polly do optimization on the Loop in LLVM and generate a optimized loop back to LLVM. However, something like CodeGenForOpenMP should be independent from Polly which means, even without Polly, CodegenForOpenMP could applied individually in LLVM as a Pass which only accept the basic elements in LLVM,e.g. Loop, BasicBlock and Module etc.. The situation is the same to the PTX back-end which only accept basic elements in LLVM e.g. Loop, BasicBlock and module etc.. This is the way Polly should go and the power it should unleash. But how to achieve this goal? It is absolutely an impasse with the existing back-end. So an adaptive and robust backend with an adapter is proposed to provide the LLVM basic element i.e. Loop in Polly to various back-ends in LLVM such as PTX back-end and OpenCL etc. So It is the most pressing problem for Polly to provide an adaptive and robust backend for various back-end in LLVM. I will elaborate the adapter below.> > To be short, I plan to implement my proposal in steps as follows: >> 1. refactor the exis ting back-end to a preliminary modular back-end. >> > > I think here and later in your proposal you should explain: > > - What are the problems with the current code? > > I do not say there are no problems, but to judge your proposal it is > necessary to understand what you want to improve. > > - What changes you want to perform here? > > Do you want to move classes, define new interfaces, split some > functionality into new classes, ...? > > (You do not even propose the perfect solution. Feel free to say there are > several solutions, which benefits they have and what still needs > to be investigated to decide which is best. You can even state you have no > solution for a problem, but you plan a week to think about it. For such a > proposal it is more important that people see you understood the problems > and that you have an idea of how to approach them. In case you are unsure > about something, it is better to say this and give a plan how you will > proceed to find a solution than to propose a solution you are not yet sure > about) > >The propose of the first step is as I mentioned above that some code like codegenForSequential, codegenForVector and codegenForOpenMP should be independent form the current Polly which mean they can be an individual pass applied in LLVM without Polly. Also, some code refactor could be done by the way. such as addressing the bugs in polly while refatoring the existing backend into a modular one. such as: 1. we can extract more independent functionality in the existing back-end into the helper classes in different files rather than assemble them in a single file (this will take time to do so and need to be well tested), I have made the first step of it in patch[1]. More steps will be done in the coming summer of code. 2. as you have post in the Todo list, the existing Polly back-end is currently centered on the CLAST. This will be another challenge to this project. 3. Another problem come up to me while I was fixing the bug of Polly[2]. The existing back-end use i64 everywhere to ensure a temporal correct result. Other project which may use date type larger than i64 may cause failure in Polly. So in the new code generator, we should be able to calculate the minimal type that is always large enough to ensure the correctness of the program.> 2. Add A CodeGen adapter, abstract away the detail of CLAst. >> > > How would this look like? What would be the difference to the clast? > > Again, I do not say we don't need this, but it would be helpful if you can > express why this is needed and what features it should have. In general I > prefer to have as little code as possible. That means for every code we add > there needs to be an obvious benefit. > > A solution without a CodeGen adapter may be to extract all the > functionality within the clast into helper classes, create a very simple > clast walker and call the helper classes there. We can do exactly the same > for another new_codegen_ast, without having to define an CodeGen adapter. > This does not need to be the better solution, but this is a possible > alternative. > >Here, we come the most controversial part of this proposal. As I mentioned above, the adapter proposed here could provide user-friendly interfaces to various back-ends in LLVM to get the Loop optimized by Polly. Also, some basic interfaces which can be a virtual method to be inherited by the back-ends and passes in LLVM could be established such as doAPIDefinition,doInitializationLoop, doFinalizationLoop, runOnLoop, doInitializationStmt, doFinalizationStmt and runOnStmt, etc.. these methods (interfaces) provide back-ends or passes in LLVM to implement their platform-specifc requirement. Take the recently hot topic on PTX back-end for example, the PTX back-end coiuld call the doAPIDefinition method to applied their specific API to the Loop in Polly. It is greatly benefit developers who would like to make use of Polly and their parallel computing platforms.> > 3. Implementation of Specific code generation class to the new back-end. >> In this phase, I am going to implement a SIMD code generation class. >> > > It would be great if you could make sure that your plan consists of > gradual improvements. This means to build up as little parallel > infrastructure as possible. At best, you add your improvements directly the > current code generation. This will ensure it is properly tested and > it matches the needs we have. I especially want to be sure we do not end > up in a situation where the OpenMP code generation still works in the old > infrastructure and SIMD is done in the new one. Better make the old > infrastructure gradually become the new one. > > > An ultimate construction of the new backend will be like the figure below: >> >> [Original Polly codegeneration pass] [Click codegeneration[1]] [whole >> function vectorize codegeneration[2]], .... >> \ >> | / >> \ >> | / >> \ >> | / >> \ >> | / >> \ >> | / >> >> CodeGen adapter >> >> / \ >> / >> \ >> / >> \ >> Cloog AST infrastructure >> XXX AST infrastructure ... >> \ >> / >> \ >> / >> \ >> / >> >> SCOP (Polly IR) >> > > I have currently no idea how your CodeGen adapter will look like. And I > have especially no idea how you plan to perform whole function > vectorization and click code generation based on Polly. > > Some examples would definitely help. > > > After the new backend is done, I think it will easy for other developers >> to implement a code generation pass which will meet the requirements of >> their platforms or LLVM back-ends. So the optimized LLVM-IR could be >> passed to the ordinary LLVM back-ends, such as the high level synthesis >> back-end I mentioned above. It will be a great help to both the >> developers and LLVM. >> > > In general I would rather emphasize in your proposal the individual steps > necessary, than to build everything around a currently not yet described > 'CodeGen adapter'. > > > Tobias Grosser and Ether, who are the contributors of Polly, have >> assented to be my mentor, If my proposal is approved. Is this idea good >> enough for the Google summer of code? If it is, I am going to write a >> proposal for it. Any suggestion is appreciated. >> > > I think working on the back end of Polly is a good idea. There is still a > lot of stuff that needs to be done there and I am sure a good proposal can > be written for this. However, the best thing you can do is to start to > write your proposal. Because only by doing this you will start to get into > Polly and to understand what kind of problems exist and how you could solve > them. Listing the problems, finding examples, possible solutions and > creating some timeline to implement this will help here a lot. I am glad to > give feedback (and promise to be reactive the days up to the deadline). > > Besides your own ideas, you may also consider the following points: > > - Extract the clast logic in a simple helper class (as proposed by ether > and you) [4] > > - Removing the independent blocks pass [5] > > - Integrate a new code generator > > We are planning to work on a new code generator that will solve several > issues. Using your modularization to integrate this code generator would > be a perfect use case. > > Thank you for these valuable advises. My proposal will be much better withyour advises.> To have an idea what I think a proposal might look like you can have a > look at my proposal a couple of years ago [2]. Ether should also have his > old proposal. As it was accepted it was apparently good enough. ;-) > > Another hint. It is in general very good if you already contributed some > code. Fixing one of the existing Polly bugs would be a good start. > This one might not be too difficult [3]. (Let me know if you need help). > > Cheers > Tobi >In conclusion, Polly with a adaptive and robust back-end would greatly help developers who would like to use Polly with their parallel computing platfroms and it is the most pressing problem for Polly to make such a back-end.：） Sincerely, Tsingray PS. We have come to an agreement that all these should be done patch by patch upon the current back-end.> > [1] http://stackoverflow.com/**questions/2338656/when-is-** > abstraction-and-**modularization-a-bad-practice-**in-programming<http://stackoverflow.com/questions/2338656/when-is-abstraction-and-modularization-a-bad-practice-in-programming> > [2] http://students.fim.uni-**passau.de/~grosser/gcc_soc/<http://students.fim.uni-passau.de/~grosser/gcc_soc/> > [3] http://llvm.org/bugs/show_bug.**cgi?id=12311<http://llvm.org/bugs/show_bug.cgi?id=12311> > [4] http://llvm.org/bugs/show_bug.**cgi?id=12406<http://llvm.org/bugs/show_bug.cgi?id=12406> > [5] http://llvm.org/bugs/show_bug.**cgi?id=12398<http://llvm.org/bugs/show_bug.cgi?id=12398> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120404/c2274b22/attachment.html>
Apparently Analagous Threads
- [LLVMdev] GSoC2012 proposal -- A new Back-end for polyhedral Optimization framework for LLVM (Polly)
- [LLVMdev] GSoC2012 proposal -- A new Back-end for polyhedral Optimization framework for LLVM (Polly)
- [LLVMdev] Proposal: Generic auto-vectorization and parallelization approach for LLVM and Polly
- [GSoC 2016] Introduction - "Enabling Polyhedral Optimizations in Julia"
- [GSoC 2016] Enabling Polyhedral Optimizations in Julia - Midterm Report