[LLVMdev] Speculative Loop Parallelization on LLVM IR

[Tobias Grosser]

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