<div>Hi Tobias: </div>
<div> </div>
<div>Thanks for replying . So if I understand correctly,  in LLVM currently, the Polyhedral model is being built ( LLVM IR -------> Poly Model ----------> LLVM IR ). </div>
<div>This is for compile-time optimizations of loop-nests [e.g. loop-transformations to expose parallelism or improve locality etc]. Yes, thats great for optimizing loop-nests. </div>
<div> </div>
<div>As an additional, since the real value of LLVM to me is run-time optimizations possibilities, some loop-nest optimizations "needs" to be done at run-time. </div>
<div>I say "needs" because many loops have unresolvable data-dependencies at compile-time</div>
<div>[for example</div>
<div> </div>
<div>FOR i = 1 to N</div>
<div>A[ B[i]  ]  = A [ i ] + func (....)</div>
<div>END </div>
<div> </div>
<div>Can the iterations of this loop be run in parallel?</div>
<div>]</div>
<div> </div>
<div>There are two approaches for with the above kind of problems. One is inspector/executor, other is speculation. </div>
<div>To keep the story short - basically, you run the loop-iterations  in parallel and verify in the end if data-dependencies were violated. If yes, you rewind and run the loop sequentially. </div>
<div>If for that particular case there was no data-dependencies violated, you have gained in execution time [yes, there is cost involved in verifying and nett gain is not always +ve ]. </div>
<div> </div>
<div>OK, so whats my point? To be able to do at least some loop-transformations at run-time to expose parallelism etc, perhaps some kind of LLVM IR --> Poly ---> LLVM IR </div>
<div>support at run-time may be required. Definitely a scaled down version, since polyhedral transformations need a lot of processing in my opinion. </div>
<div>So if i understand, we are not there yet .... and may be i can come back with some proposal/ideas and cross-check it with you guys. </div>
<div> </div>
<div>Thanks </div>
<div>Javed </div>
<div> </div>
<div> </div>
<div><br> </div>
<div class="gmail_quote">On 18 June 2010 19:33, Tobias Grosser <span dir="ltr"><<a href="mailto:grosser@fim.uni-passau.de">grosser@fim.uni-passau.de</a>></span> wrote:<br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">Hi Javed, 
<div class="im"><br><br><br>On 06/18/10 14:07, Javed Absar wrote:<br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">Hi:<br>I worked on loop-optimizations techniques previously using ORC.<br>Currently i see lots of research on speculative parallelization of<br>
loops ... specially because multicores [for embedded systems] is<br>becoming popular. In other words, because you have<br>multiple cores, you can start some loops [Fast-Track] as if there is no<br>or low data-dependence [Partial Parallel Loop-Nest].<br>
The normal part is to check later if there was some violation and then<br>rollback etc. [something like that ... I dont think people want to hear the<br>full story here].<br>What do you guys think about the feasibility of "speculative run-time<br>
loop optimization' using LLVM IR as base.<br>I know there are lots of issues to it -<br>1. Loop transformation requires tools like PolyLib (Polyhedral<br>analysis). They are too computationally expensive for<br>run-time optimization.<br>
</blockquote></div>There is Polly (still in development)<br><a href="http://wiki.llvm.org/Polyhedral_optimization_framework" target="_blank">http://wiki.llvm.org/Polyhedral_optimization_framework</a><br><br>And to say this. The current problem is not very often the computationally complexity. However it might be that we have not yet reached the point, when this gets relevant. 
<div class="im"><br><br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">2. I am not clear how to launch threads at LLVM IR level (you do need to<br>create new threads for some of these RT speculative loop parallelization<br>
techniques).<br></blockquote></div>You could add calls to the posix functions that create a thread to the LLVM-IR or you could use some higher level libraries that support thread creation.<br><br>The OpenMP runtime libraries e.g. can help you with this. Here a link to the GNU libaries that could be used to try this approach.<br>
<a href="http://gcc.gnu.org/onlinedocs/libgomp/" target="_blank">http://gcc.gnu.org/onlinedocs/libgomp/</a> 
<div class="im"><br><br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">Is somebody already doing something like this? Does this proposal make<br>sense even to start...<br></blockquote>
</div>I do not yet understand what you want to do.<br><br>You just want to execute some loops in parallel without knowing if they have data dependencies. And than afterwords you would like to check if there where dependencies.<br>
<br>How would you check for violated dependencies?<br><br>Can you give an example of a loop, that would have no dependencies and that you would like to improve?<br><br>Tobi<br></blockquote></div><br><br clear="all"><br>-- <br>
my homepage: <a href="http://www.javedabsar.com">http://www.javedabsar.com</a><br>