[LLVMdev] Speculative Loop Parallelization on LLVM IR

[Javed Absar]

Hi Tobias:

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

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

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.

Thanks
Javed




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>