<h3 align="center"> Google Summer of Code Application 2011</h3>
<h3 align="center"> Sad Al Abdullah </h3>
<h3 align="center">  Department of Computer Science and Engineering</h3>
<h3 align="center">  Bangladesh University of Engineering and Technology</h3>

--------------------------
  <b>1.Contact Details:</b>

     <b>Name:</b> Sad Al Abdullah<br />
     <b>Email Address:</b><font color="blue"> siam9090@gmail.com,siam9090@yahoo.com  </font><br />                 
     <b>Cell Phone:</b> +880 1915999955<br />
----------------------------
  <b>2.My Proposed  Project:</b>
        <p> As a student of Computer Science and Engineering, I am personally very interested to work in C, C++   or Java. I am interested in Array Bounds Check Elimination Project.  The aim of this project is to eliminate redundant array bound check. To eliminate array bound check Theoretically SciMark benchmark and SPECjvm98 speed up 40% and 2% respectively. I am very enthusiastic to read this and want to work in this project.</p>
 ---------------------------
 <b>3. Relevant Skills for the Project:</b>

    <p> Right now I am in my 4th year / 1st Semester of my undergraduate in Computer Science and Engineering in Bangladesh University of Engineering and Technology. I have attended both theoretical and practical courses in C, C++, Java, Algorithm, Data Structure, Automata Theory, Operating System and Compiler and believe that I have basic theoretical knowledge for this project. My relevant skills are -</p>
<p>
  <b>Related to this project:</b>  C/C++, Java, C#, Shell Script, Lex, Yacc.</p>
  <p><b>Operating Systems:</b> Windows XP, Windows Vista, Windows 7, Different platforms of Linux
 </p>
   <b>Relevant Skills projects:</b>
  *  Pc^2 (Online programming contest software)
        <b>Platform:</b> Java (multi-thread, socket programming, database)
  * Ad Network simulation
       <b> Platform:</b> Java  
  * NACHOS Operating System Implementation : – multi-programming ,Processes Management,FileSystem, Memory Management & Console  Management.
         <b> Platform:</b> C++
  *  Compiler  Converting C code to 8086 Assembly code
       <b>Platform:</b> Lex, YACC, C
  * Link State Routing Simulation
       <b> Platform:</b>  Java
  * Content Server Implementation
      	- Weather Sensor and Broadcaster
       <b> Platform:</b>  Java 
   	     	
  My CV is available <a href="http://www.box.net/shared/rlstv0xd0q">box.net.</a>
   <p> I think my past project experience and my motivation, enthusiasm will enough for doing this project perfectly.</p>
---------------------------
 <b>4. Design Description:</b>
     <p>Jato currently does not support Single Static Form (SSA) so I have to choose a non-SSA algorithm for “Array  Bound Check Elimination”. The algorithm base on Control Flow Graph(CFG). In control flow graph(CFG) each node in the graph represents a basic block. The basic blocks of the CFG contain a sequence of source level statements rather than intermediate code statements.  To optimize the array bound check at first Minimal Control Flow Graph(MCFG) is construct. It helps to perform the range check optimization and global range check optimization with efficiently.</p>
 
 
 <b>Minimal Control Flow Graph (MCFG):</b>
    <p> Eliminating empty node and optimize the CFG , minimal control flow graph(MCFG) is construct. The MCFG is unique by <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.5471&rep=rep1&type=pdf">Claim</a>. The nodes contained in the MCFG are the non-empty  set of nodes which is unique. It  will help to implement of range checking efficiently.</p>
    <p>Array Bound Check Elimination :  
        # Local Elimination
        # Global Elimination
        # Propagation of Checks Out of Loops
        # Combination of Range Checks
   </p>         	
 
 <b> Local & Global Elimination :</b>
      <p> The checks killed by a basic block are computed differently from available expressions since a check may not, be killed if an identifier used in the expression is redefined by a monotonic definition.  The definition of identifier kills a range check if it is Monotonically Increasing or Monotonically Decreasing. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.5471&rep=rep1&type=pdf">  (Algorithm )</a></p>
          
 <b>Propagation of Checks Out of Loops :</b>
    <p>  The goal of propagation is to reduce the number of times the checks are executed by moving them out of loops. In this section an algorithm to propagate additional range checks out of a loop is presented.</p>
 <b>Combination of Range Checks :</b>
   <p>The combination optimizations are local optimizations that combine multiple checks into a single check. Basically we can tell grouping check optimization.</p>
 	
 <b> Interprocedural Optimizations :</b>
    <p>The techniques described above are applied to a single procedure. It is also possible to perform interprocedural range check optimizations. Interprocedural propagation can be performed by moving checks from the start of a procedure to each of the call sites. In other words, the checks are propagated from a called procedure to the caller.</p> 
  <p> The Ordering the Optimizations is very important because redundant checks will not be considered as Candidates for propagation. The local, global, and interprocedural elimination of range checks should be performed prior to propagation of checks.</p>
  <p> Algorithm :<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.5471&rep=rep1&type=pdf"> A Fresh Look at Optimizing Array Bound Checking - Rajiv Gupta</a></p>
<p><b>References :</b> 
 # <a href="">Optimization of Range Checking - Victoria Markstein</a>
 # <a href="http://en.wikipedia.org/wiki/Control_flow_graph">Control Flow Graph</a>
</p>
 
<b> What is the benefits ?</b>
    <p> The main benefits of array check elimination is speed up the execution of a program. The speed up depends on types of application.   e.g. The best results are achieved for the LU benchmark. The theoretically possible speedup is 201%. Because our algorithm eliminates 99% of all bounds checks. </p>
-------------------------------------------------------
<b>5. Work Plan</b>
 <b>Community Bonding Period:</b>
      * Discussing different aspects of the algorithm with the mentors
          #  Understanding the current Control Flow  Process
          #  Understanding any relevant source code

  <b>May 23 -June 5:</b>
          *  Construct Minimal Control Flow graph from CFG.

  <b>June 6- June 12:</b> 
         *  Testing and bug analyzing

  <b>June 13 - June 30:</b>
          * Implement the local and Global Elimination array bound check

  <b>July 1  – July7:</b>
          * Testing and Bug analyzing
          <b>Deliverable:</b> A fully functional  local and global array bound check elimination in Jato VM.

  <b>July 8– July 14:</b>
          *  Propagation of Checks Out of Loops

  <b> July 15 - Midterm Evaluation</b>

  <b>July 16 – July 22:</b>
          *  Testing and Bug analyzing
         <b> Deliverable:</b> A fully  functional working code.
 
   <b>July 23 – July 31:</b>
          *  Combination of Range Checks implementation

  <b>August 1– August 7:</b>
          *  Testing and Bug analyzing
        <b> Deliverable:</b> A fully  functional working code.

  <b>August 8 – August 15:</b>
         *   Checking Ordering the Optimizations .
         *   Bug testing and clean up
         <b> Deliverable:</b> Finished Product

  <b>August 15 – August 25:</b>
         * Pencils down
         * Only reserved for any emergency situation
---------------------------------------------
 
 <b>  6. My Summer Plans:</b>
   <p>  I am going to spend my summer in Dhaka, Bangladesh. My classes coincide with the project timeline but I can do extra hours in the weekends to make the project successful. I am willing to work 26-28 hours per week for this project. Although I have classes in summer but I do not have any major examinations, which can create obstacles for the project. I will be available for the whole summer to work on this project.<p>
-------------------------------
  <b>  7.Conclusion :</b>
     <p> I’d like to thank all the developers of Jato VM for putting up such a great effort. I’d also like to thank Google for organizing Google Summer of Code and flourishing Open Source community.</p>