llvm dev - Mar 2009 - [LLVMdev] GSoC 2009: Extending LLVM IR to aid multi-core code generation

Hi,

I would like to extend LLVM IR with two new intrinsic: spawn and join. The
spawn intrinsic will indicate that the call it modifies can safely run in
parallel, while join intrinsic will indicate that the execution of the
current call cannot continue until all previously spawned calls in the
list/array passed as argument to join intrinsic have completed and returned
their results to it. This extension would allow us to express strict
multi-thread computations and introduce possibility of new optimisations
passes for parallel computations (see below for some of them).

Once this extension is added I plan to demonstrate its usability and how
expressible it is in two ways. Firstly, I will implement randomized
work-stealing algorithm in VMKit. This will effectively find an execution
schedule that obeys constraints imposed by the multi-thread computation.
Secondly, I will extend back-end of a multi-threaded processor (such as
XCore) to create threads when call is modified with spawn intrinsic and sync
them when join intrinsic is encountered. We can run generated code using a
scheduler that implements randomized work-stealing algorithm or when
generating code we can pass it through optimisation passes such as copy
elimination (to remove unnecessary copy operations), fusion (if parallelism
slackness is high, i.e. number of spawned calls is greater then number of
available cores we would need to group them) and fission (if parallelism
slackness is low than we would need to increase throughput by multiplying
work). Please note if generating code for single-threaded processor and we
encounter spawn intrinsic we simply ignore it and generate code for a call,
while join intrinsic becomes no-op.

Would the above proposal be of interest to LLVM community and Google Summer
of Code? If you have any questions/suggestions/ideas please let me know.

Thanks,
Milos.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090330/d28ae003/attachment.html>

Hi Milos,

Milos Puzovic wrote:
> Hi,
>
> I would like to extend LLVM IR with two new intrinsic: spawn and join. 
> The spawn intrinsic will indicate that the call it modifies can safely 
> run in parallel, while join intrinsic will indicate that the execution 
> of the current call cannot continue until all previously spawned calls 
> in the list/array passed as argument to join intrinsic have completed 
> and returned their results to it. This extension would allow us to 
> express strict multi-thread computations and introduce possibility of 
> new optimisations passes for parallel computations (see below for some 
> of them).
>
> Once this extension is added I plan to demonstrate its usability and 
> how expressible it is in two ways. Firstly, I will implement 
> randomized work-stealing algorithm in VMKit. 
Can you be more verbose on this? Are you planning to implement some JVM 
or .Net extension for supporting your new intrinsics? Or are you just 
looking for a runtime with a GC?
> This will effectively find an execution schedule that obeys 
> constraints imposed by the multi-thread computation. Secondly, I will 
> extend back-end of a multi-threaded processor (such as XCore) to 
> create threads when call is modified with spawn intrinsic and sync 
> them when join intrinsic is encountered. 
Why do you need to hack on a processor backend for such purpose? Aren't 
your OS primitives sufficient?

Nicolas

Hi Nicolas,

2009/3/30 Nicolas Geoffray <nicolas.geoffray at lip6.fr>
> Can you be more verbose on this? Are you planning to implement some JVM
> or .Net extension for supporting your new intrinsics? Or are you just
> looking for a runtime with a GC?
At the moment I am not looking to add any new extensions to JVM or .NET. I
would need a runtime with a GC to demonstrate and test building execution
schedules using the randomized work-stealing algorithm. I thought that I
could factor out some code from VMKit that would help me to get there?
Otherwise I would look at working with LLVM interpreter to support multi-
and many-core execution with new intrinsic. Once I am happy with the
performance I will look into adding extensions to JVM and .NET.

Why do you need to hack on a processor backend for such purpose?
Aren't
> your OS primitives sufficient?
Yes they are, but I also want to exploit any specific instructions from the
multi-thread processors for creating and distributing threads. For examples,
XCore ISA has an instruction TSTART to start and a group of instructions
starting with TINIT for initialising different aspects of thread states. It
would then be interesting to compare how would that generated code handle
load balancing compared to work-stealing algorithm and if they can work
together.

Milos.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090330/11ad7f7d/attachment.html>