[LLVMdev] GSoC 2009 application

Fri Apr 3 13:14:53 PDT 2009

On Fri, Apr 3, 2009 at 9:36 PM, Chris Lattner <clattner at apple.com> wrote:

> On Apr 3, 2009, at 12:52 AM, Kshitiz Garg wrote:
>
> Here is my formal proposal i have submitted in gsoc. Comments invited.
>
> This sounds like a very interesting proposal.    Many compilers clone loops
> and use dynamic checks to enforce invariants in one copy of the loop.  Is
> this intended to be similar to that style of approach?
>

There are 2 different  approaches possible for this online and offline. In
the online approach[3],  compilers clone the loops and insert code to keep a
real time check on invariants and profile information and switch from one
loop execution to another. Another possible approach  is to have a  run to
collect all the information and use it offline to compile into the optimised
code.
 The first approach is better when one can obtain results from static
profiling about the dependencies. So that the compiler can easily figure out
the target locations.and appropriately monitor those during the program run
phase. I am planning to take the second approach to compile offline. The
better knowledge of access patterns will be useful in deciding the variables
for prediction and stores for suppression. For better results machine
learning techniques can be applied to predict dependence.[4] The loop still
will have runtime checks.

A simple example of this could be.

Original code ..                                  Modified Code

a = 3;                                               if(a!=3) a=3;

This transformation will replace a store with a load for most cases where
silent dependencies exits. This is desirable specially when running on
several cores to avoid frequent invalidation of caches due to useless
updates.

Kshitiz

[3]*An Online Profile Guided Optimization Approach for Speculative Parallel
Threading*
* Yuan Liu, Hong An, Bo Liang, and Li Wang ACSAC 2007*
[4]Towards a Holistic Approach to Auto-Parallelization Integrating
Profile-Driven Parallelism Detection and Machine-Learning Based  Mapping,
Georgios Tournavitis ,Zheng Wang, Bj ̈ rn Frankeo,Michael F.P. O’Boyle, to
appear in PLDI 2009
http://homepages.inf.ed.ac.uk/bfranke/Publications/pldi121-tournavitis.pdf

> -Chris
>
>
>   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 <http://home.iitk.ac.in/%7Ekshitizg>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090404/c3af1006/attachment.html>