<p>Here is my formal proposal i have submitted in gsoc. Comments invited.<br></p>
<p> About me:</p>
<p>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.</p>
<p>Relevant Skills:</p>
<p>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.</p>
<p>Project Proposal:</p>
<p>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:-</p>
<p>1. Rarely occuring dependeccies.</p>
<p>2. Silent depencecies (harmless dependecies) eg. writing the same value a before.</p>
<p>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.</p>
<p>For achieving the above I propose to add the following passes to the LLVm System..-</p>
<p>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.</p>
<p>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.</p>
<p>c.a loop transformation pass to use profile information to performa strip mining and loop peeling.</p>
<p>Maybes:</p>
<p>a. Partial dead code ellimination,partial redundancy ellimination , conditional branch ellimination [2]</p>
<p>Roadmap:</p>
<p>April 20 - May 23 -- Familiasing with the LLVM system and the
cuurent Loop passes implemented., reading the papers and forming a
prelimnary coding plan</p>
<p>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</p>
<p>June 7 - June 21 -- Loop transformation pass converting the loop into a speculative one using the copy or dicard model[1].</p>
<p>June 21 - July 7 - Loop peeling and strip mining passes.</p>
<p>July 7 - August 10 -- Maybes + Complete testing and documentation.</p>
<p> </p>
<p>References:</p>
<p>[1]<span class="headNavBlueXLarge2">Copy or Discard execution model for speculative parallelization on multicores</span><span class="bodyCopyBlackLargeSpaced"><a class="bodyCopy" href="http://ieeexplore.ieee.org/search/searchresult.jsp?disp=cit&queryText=%28chen%20tian%3CIN%3Eau%29&valnm=Chen+Tian&reqloc%20=others&history=yes">Chen Tian</a> <a class="bodyCopy" href="http://ieeexplore.ieee.org/search/searchresult.jsp?disp=cit&queryText=%28%20min%20feng%3CIN%3Eau%29&valnm=+Min+Feng&reqloc%20=others&history=yes"> Min Feng</a> <a class="bodyCopy" href="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"> Nagarajan, V.</a> <a class="bodyCopy" href="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"> Gupta, R.</a> </span><a href="http://ieeexplore.ieee.org/xpl/RecentCon.jsp?punumber=4757685"><strong>Microarchitecture, 2008. MICRO-41. 2008 41st IEEE/ACM International Symposium </strong>330-341</a></p>
<p>[2]The Compiler Design Handbook<span class="addmd"> Y. N. Srikant, Priti Shankar 143 - 171</span></p>
<br><br><div class="gmail_quote">On Fri, Mar 27, 2009 at 6:43 PM, Anton Korobeynikov <span dir="ltr"><<a href="mailto:anton@korobeynikov.info">anton@korobeynikov.info</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hello, Kshitiz<br>
<div class="im"><br>
> I was interested in taking up the project ideas on adding profile driven<br>
> optimization passes and improving alias analysis as this would give me a<br>
> chance to carry forward and improve my current work and also contribute<br>
> significantly in terms of tangibles.<br>
</div>This sounds like a great idea. LLVM definitely lacks some<br>
profile-driven optimizations.<br>
<font color="#888888"><br>
--<br>
With best regards, Anton Korobeynikov<br>
Faculty of Mathematics and Mechanics, Saint Petersburg State University<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</font></blockquote></div><br><br clear="all"><br>-- <br>Kshitiz Garg<br>Graduate Student<br>Department of Computer Science & Engineering<br>IIT Kanpur<br><a href="http://home.iitk.ac.in/~kshitizg">http://home.iitk.ac.in/~kshitizg</a><br>