[LLVMdev] Speculative Loop Parallelization on LLVM IR

Javed Absar javed.absar at gmail.com
Sun Jun 20 22:12:09 PDT 2010

Hi Tobias:

Thanks for replying . So if I understand correctly,  in LLVM currently, the
Polyhedral model is being built ( LLVM IR -------> Poly Model ---------->
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.

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.
I say "needs" because many loops have unresolvable data-dependencies at
[for example

FOR i = 1 to N
A[ B[i]  ]  = A [ i ] + func (....)

Can the iterations of this loop be run in parallel?

There are two approaches for with the above kind of problems. One is
inspector/executor, other is speculation.
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.
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 ].

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
support at run-time may be required. Definitely a scaled down version, since
polyhedral transformations need a lot of processing in my opinion.
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.


On 18 June 2010 19:33, Tobias Grosser <grosser at fim.uni-passau.de> wrote:

> Hi Javed,
> On 06/18/10 14:07, Javed Absar wrote:
>> Hi:
>> I worked on loop-optimizations techniques previously using ORC.
>> Currently i see lots of research on speculative parallelization of
>> loops ... specially because multicores [for embedded systems] is
>> becoming popular. In other words, because you have
>> multiple cores, you can start some loops [Fast-Track] as if there is no
>> or low data-dependence [Partial Parallel Loop-Nest].
>> The normal part is to check later if there was some violation and then
>> rollback etc. [something like that ... I dont think people want to hear
>> the
>> full story here].
>> What do you guys think about the feasibility of "speculative run-time
>> loop optimization' using LLVM IR as base.
>> I know there are lots of issues to it -
>> 1. Loop transformation requires tools like PolyLib (Polyhedral
>> analysis). They are too computationally expensive for
>> run-time optimization.
> There is Polly (still in development)
> http://wiki.llvm.org/Polyhedral_optimization_framework
> 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.
> 2. I am not clear how to launch threads at LLVM IR level (you do need to
>> create new threads for some of these RT speculative loop parallelization
>> techniques).
> 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.
> 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.
> http://gcc.gnu.org/onlinedocs/libgomp/
> Is somebody already doing something like this? Does this proposal make
>> sense even to start...
> I do not yet understand what you want to do.
> 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.
> How would you check for violated dependencies?
> Can you give an example of a loop, that would have no dependencies and that
> you would like to improve?
> Tobi

my homepage: http://www.javedabsar.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100621/0d67fb5e/attachment.html>

More information about the llvm-dev mailing list