[LLVMdev] GSoC 2009 application

[Kshitiz Garg]

Here is my formal proposal i have submitted in gsoc. Comments invited.

  About me:

I am a final semester Dual Degree( B.Tech. M.Tech.) student from Indian
Institute of Technology, Kanpur. I was looking forward to participate in
this year's GSoC 2009.Starting Fall 2009 i shall be pursuing a Phd in
compilers. I am having a good background in compilers. My current masters
thesis is aimed at automatic parallel code from c programs target for the
Cell Processor using speculative and runtime parallelization techniques. As
a part of this I am taking a profile driven approach to figure out the
program access paterns to accurately model the same.

Relevant Skills:

I have been using the LLVm system for some time so am somewhat familiar with
the system. I have strong C/C++ skills acquired by working on several
projects including my thesis. Besides my thesis I have previously taken
classes on Compilers, compilers optimizations, parallel programming and
multicore architectures. As part of compilers class project I had to
implemented a compiler for the Oberon programming language from scratch.

Project Proposal:

Since several people are working on loop static loop dependence analysis, I
wish to extend this into the profile driven paradigm. The profile driven
approach can be useful in the following cases:-

1. Rarely occuring dependeccies.

2. Silent depencecies (harmless dependecies) eg. writing the same value a
before.

The program can be profiled to obtain this information. Based on this
information the optimiser can selectively exercise the dependecy, making
checks in case of a wrong prediction. This will be particularly useful when
try to parallelize the code. The profile information can also be used to
obtain the actual desnsity of the loop to figure out the best
parallelization technique.

For achieving the above I propose to add the following passes to the LLVm
System..-

a. A profiling pass to record the timing, access and value information. This
shall be a 2 stage pass. Access / Value profiling is costly so shall be
applied only on the HOT code regions.

b.A loop transformation pass to use this information to speculatively
parallelize the loop. I aim to use the copy or discrad model [1] for
speculative paralleliztion.

c.a loop transformation pass to use profile information to performa strip
mining and loop peeling.

Maybes:

a. Partial dead code ellimination,partial redundancy ellimination ,
conditional branch ellimination [2]

Roadmap:

April 20 - May 23 -- Familiasing with the LLVM system and the cuurent Loop
passes implemented., reading the papers and forming a prelimnary coding plan

May 23 - June 7 -- profiling passes coded ,improved and tested. Passes
optimised to incorporate statically available information like loop
iterations,known aliases nd estimated parallelism

June 7 - June 21 -- Loop transformation pass converting the loop into a
speculative one using the copy or dicard model[1].

June 21 - July 7 - Loop peeling and strip mining passes.

July 7 - August 10 -- Maybes + Complete testing and documentation.



References:

[1]Copy or Discard execution model for speculative parallelization on
multicoresChen Tian<http://ieeexplore.ieee.org/search/searchresult.jsp?disp=cit&queryText=%28chen%20tian%3CIN%3Eau%29&valnm=Chen+Tian&reqloc%20=others&history=yes>
Min Feng<http://ieeexplore.ieee.org/search/searchresult.jsp?disp=cit&queryText=%28%20min%20feng%3CIN%3Eau%29&valnm=+Min+Feng&reqloc%20=others&history=yes>
Nagarajan, V.<http://ieeexplore.ieee.org/search/searchresult.jsp?disp=cit&queryText=%28%20nagarajan%20%20v.%3CIN%3Eau%29&valnm=+Nagarajan%2C+V.&reqloc%20=others&history=yes>
Gupta, R.<http://ieeexplore.ieee.org/search/searchresult.jsp?disp=cit&queryText=%28%20gupta%20%20r.%3CIN%3Eau%29&valnm=+Gupta%2C+R.&reqloc%20=others&history=yes>
*Microarchitecture, 2008. MICRO-41. 2008 41st IEEE/ACM International
Symposium *330-341<http://ieeexplore.ieee.org/xpl/RecentCon.jsp?punumber=4757685>

[2]The Compiler Design Handbook Y. N. Srikant, Priti Shankar 143 - 171


On Fri, Mar 27, 2009 at 6:43 PM, Anton Korobeynikov <anton at korobeynikov.info
> wrote:

> Hello, Kshitiz
>
> >    I was interested in taking up the project ideas on adding profile
> driven
> > optimization passes and improving alias analysis as this would give me a
> > chance to carry forward and improve my current work and also contribute
> > significantly in terms of tangibles.
> This sounds like a great idea. LLVM definitely lacks some
> profile-driven optimizations.
>
> --
> With best regards, Anton Korobeynikov
> Faculty of Mathematics and Mechanics, Saint Petersburg State University
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>



-- 
Kshitiz Garg
Graduate Student
Department of Computer Science & Engineering
IIT Kanpur
http://home.iitk.ac.in/~kshitizg
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090403/e65d8967/attachment.html>