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

[Milos Puzovic]

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>