Project for CSC 255/455, Spring 2010

Introduction

We have one warm-up project based on GCC, and four URCC-based projects which mainly focus on implementing automatic parallelization step by step. In the project, you will add your own passes in your ruby C Compiler, URCC. You have to know the basic framework of URCC and how to manipulate the intermediate form, for program analysis and transformation. This page includes many suggestions that will help you in the process. Please read the entire page before you start.

Install GCC

You have to work on GCC for your first project. Here we use GCC-4.2.2. It is not the most recent GCC, but should be sufficient for our project. Check out the code from GCC read-only repository, following the commands below. For more information about GCC debugging and data structure, please click here.

**step #1 Check out gcc source code

    cd  /localdisk
        // change to your work directory, such as /localdisk
    mkdir gcc
    cd gcc
    svn co svn://gcc.gnu.org/svn/gcc/tags/gcc_4_2_2_release gcc-4.2.2

**step #2 Check out padding files using mercurial. Run "which hg" to see whether there is mercurial version control on your machine. If not, download one from here. Then Create .hg/hgrc file and put the following line in it.

    [paths]
    default = ssh://cs255@node1x4a.cs.rochester.edu//localdisk/xiang/cs255/
    default-push = ssh://cs255@node1x4a.cs.rochester.edu//localdisk/xiang/cs255/

Now run the following commands step by step. The password for account cs255 is cs455.

    hg pull -u
    cd padding
    bash padding.sh
    cd ..

**step #3 Install GCC

    mkdir obj
    cd obj
    ../gcc-4.2.2/configure --prefix=$INSTALL_DIR 
        // $INSTALL_DIR is the directory you want to install your compiler, such as $HOME/gcc-build
        // If you encounter the error "error: Building GCC requires GMP 4.1+ and MPFR 2.3.0+", 
        // please download gmp or mpfr from ftp://gcc.gnu.org/pub/gcc/infrastructure 
        // and put the extracted directory under $HOME/gcc/gcc-4.2.2/
    make
    make install

* Use either our desktop or personal machine or one of the public use machines in the CS department. When using department machines, due to the shortage of space for the /home directory, it is better to put your code under /localdisk .

**step #4 Use make for your testing. Makefile is in the directory test_cases.

About turn in

You need to turn in the file containing source code (only cs255.c for project #1), along with the README document describing the design, implementation and testing results when applicable. README is a very important part of your project, so lease take it seriously. To submit your work, make a new folder, put cs255.c and README into it, and then call /u/cs455/TURN_IN . in the folder (Don't forget the "."). If you have problem with the submit script, feel free to send the two files to me by email.

* To prevent the problem of hardware incompatibility, you'd better build your compiler and use it and run the compiled executables on the same kind of machines.

* If you are not familiar with subversion, take a look at the VersionStuff page.

* Gnu's wiki page on the generic installation procedure for GCC.

Part 1: Trivial (5%)(Individual Project) (Due: Feb. 21 11:59pm)

In this part, you will add a pass that will insert code into a program to count and output the number of executed statements when the program executes. You need to first add a call at the beginning of the main function, which has a global counter initialized to 0; then add a call before each gimple statement, which increments the counter; and finally add a call at the exit, which reports the run-time instruction counts. The three functions are provided in cs255-lib.c and cs255-lib.h. These two files are already included in test_cases directory when you check out padding files.

* Put your own code into gcc-4.2.2/gcc/cs255.c

* Initialization: you'll need to add it at the entry of the main function

* Increment: to be added before each real gimple statements (all except for labels)

* Report: to be added at all possible exits of the program

* Remember to add #include "cs255-lib.h" in your own testing programs.

* Invoke your pass: use -O2 -fcs255

This part should take at most tens of lines of code and no more than a day (including half an hour compiling the compiler for the first time). The purpose is to get you familiar with GCC and the basic GCC functions that you'll need for adding your optimization passes. Reading the relevant, existing code (in gcc-4.2.2/gcc/cs255.c) is the best way to help you writing your new code in an existing system. For instance, the code for counting the number of basic blocks and statements statically is already in the file. The code for getting the dynamic count of the basic blocks is also given.

For testing, there are some test case in directory test_cases. You may use the results from them to check your code with your classmates. And they are very useful in following parts and final competition.

Part 2: Loop representation (20%)(Individual Project) (Due: Mar. 24 11:59pm)

Using the provided URCC compiler, recognize loops in programs written in a simplified C language. CSC 455 compilers are required to handle nested loops, while CSC 255 ones do not need to deal with nesting. All the transformation and analysis should be done on the URCC intermediate representation, between the front-end and the back-end. All your code should be in cs255.rb, which is already in the urcc directory. There are several steps you should follow to complete the project.

Step #1: set up URCC compiler

* Use the code you checked out in part 1 and change to your working directory, for example /localdisk/gcc/urcc. There is a How_To_Install file which provides instructions for installation. Basically, in order to use urcc from directories other than urcc, you need to add the bin directory into your environment variable PATH, and add the ast directory into your RUBYLIB, which the Ruby interpreter uses to search for needed modules. For instance, you have the top directory, urcc, under /localdisk/gcc/urcc. If you are using C Shell, you can do so by adding the following lines into your .cshrc file

       setenv PATH "$PATH":"$HOME/urcc/bin"
       setenv RUBYLIB "$HOME/urcc/ast"

* Change urcc/ast/driver.rb file (the 22nd line) to specify your own GCC 4.2.2 directory (what you built in Project Part 1). For example, if the gcc you built last time is under /localdisk/gcc/gcc-build/bin/gcc, then change that line to:

      yourgcc = "/localdisk/gcc/gcc-build/bin/gcc"

* Run URCC, just type urcc following with your file name, e.g. urcc ab.c. By default, it will generate a ab.c.*.gimple file, the c file generated by urcc ab_urcc.c, and the binary file ab.

See CS255Spring09ProjectRubyTrack for more information about URCC compiler and see RochesterCCompiler for the class hierarchy of the URCC intermediate form. If this is your first time to write code in Ruby, you may also have a look at Programming Ruby by Thomas and Hunt (free on-line access for 1st edition).

Step #2: build control flow gragh

* In order to recognize loops, you may have to build control flow graph of the parsed program first. Just follow the algorithm given in the Cooper & Torczon book.

Step #3: recognize loops

* Your pass should output basic information of the loops you find. Each loop should have at least the following infomation.

       // use the following loop as an example
      for (i=0; i<10; i++){
         sum+=i;
      }
      // your pass should outputs:
      index variable: i
      lower bound: 0
      uppper bound: 9
      increment: 1
      body: sum+=i;

* Feel free to use any algorithm you prefer. If you have no idea what to do, you may try Tarjan's SCC algorithm to find strongly connected components in your control flow gragh, which corresponds to loops in original program.

* CSC 455 compilers are required to handle nested loops, while CSC 255 ones do not need to deal with nesting (extra credit for CSC 255).

Step #4: test your compiler

* You are encouraged to create your own test cases. For simplicity, in this project you are only required to deal with for-loops whichdo not have early exits. So your test cases could be as simple as a list of statements and (nested) for-loops.

* The ones who submit their own test cases will get extra credits (additional 10% of this project's grade) .

Step #5: turn in

You need to turn in the file containing source code (cs255.rb and any files you have modified), along with the README document describing the design, implementation and testing results when applicable. README is a very important part of your project, so please take it seriously. To submit your work, make a new folder, put all the files into it, and then call /u/cs455/TURN_IN . in the folder (Don't forget the "."). If you have problem with the submit script, feel free to send the your directory to me by email.

Part 3: Dependence checking (20%)(Individual Project) (Due: Mar. 31 11:59pm)

In this assignment ,you are required to produce a dependence graph for each loop, labeling each dependence with the direction and distance vectors and the scalar and array variables that cause the dependence. Make use of the loop information generated and control flow graph built in your previous project. Two example loops and the expected outputs of your dependence checking are as below.

Example #1:

       // use the following loop as an example
      for (i=0; i<10; i++){
        for (j=0; j<10; j++){
          a[i][j] = b[i][j] + a[i-1][j+1];
        }
      }
      // your pass should outputs:
      loop body:
      s1: a[i][j] = b[i][j] + a[i-1][j+1]         //you should index the statements within the same loop
      dependence:
      from s1 to s1 caused by a_1: (1, -1) (<, >)       // (1, -1) is the distance vector and (<, >) is the direction vector
                                                                               // a_1 means the dependence is caused by first index of a

Example #2:

       // use the following loop as an example
      for (i=0; i<10; i++){
        for (j=0; j<10; j++){
          a[i][j] = a[i-1][j] + a[i+1][j] + a[i][j-1] + a[i][j+1];
        }
      }
      // your pass should outputs:
      loop body:
      s1: a[i][j] = a[i-1][j] + a[i+1][j] + a[i][j-1] + a[i][j+1];      //you should index the statements within the same loop
      dependence:
      from s1 to s1 caused by a_1: (1, 0) (<, =)       //(1, -1) is the distance vector and (<, >) is the direction vector    
      from s1 to s1 caused by a_2: (0, 1) (=, <)       //a_1 means the dependence is caused by second index of a
      anti-dependence
      from s1 to s1 caused by a_1: (1, 0) (<, =)
      from s1 to s1 caused by a_2: (0, 1) (=, <)

* For simplicity, in this project you are only required to deal with for-loops which do not have early exits. So your test cases could be as simple as a list of statements and (nested) for-loops.

* It's strongly recommended that doing some exercise of dependence checking by hand before you start coding. You cannot make your code correct unless you understand dependence theory quite well.

* You are encouraged to create your own test script using Rake in this project. The ones who submit their own rake test script will get extra credits (additional 10% of this project's grade) .

* Turn in the file containing source code (cs255.rb and any files you have modified), along with the README document describing the design, implementation and testing results when applicable. README is a very important part of your project, so please take it seriously. To submit your work, make a new folder, put all the files into it, and then call /u/cs455/TURN_IN . in the folder (Don't forget the "."). If you have problem with the submit script, feel free to send the your directory to me by email.

Part4: Group Competition (55%) (Due: Apr. 16 11:59pm)

In this project, you are required to work together in teams to extend your compiler to parallelize a sequential program using OpenMP directives, including parallel sections/loops and private or other types of variables. There are several steps you should follow to complete the project.

step #1. Build your group repository

You need a version control system for group software development. We recommend using the distributed version control system called Mecurial. One of the team members creates a project repository from which each member makes a copy. Send the location of the project repository to the instructor and the TA. Add the shared files, such as urcc/ast folder, into your repository. Do NOT put the whole gcc directory in your repository. This step should be done by Wednesday (Apr. 7th 11:59pm).

You are encouraged to read the many on-line tutorials on Mercurial. The basic commands you need are as follows. Note that unlike subversion, you have a copy of the repository on your local machine, and you check out from and check into the local repository.

  1. create a directory for your repository, which should be on the dept file system if this is the project repository.
  2. initialize it by calling 'hg init' inside the directory
  3. if this is your local repository, pull from the project repository using 'hg pull'. You may use ssh if your local machine is not on the same file system, e.g. your laptop computer.
  4. run 'hg update' to check out files from the local repository into your local directory
  5. add files using 'hg add'
  6. check in changes to your local repository using 'hg commit'
  7. send your past commits from the local repository to the project repository using 'hg push'

To avoid having to explicitly type in the repository address at each pull/push, you can create a file in the .hg/.hgrc at the root level of the repository directory with the following contents:

[paths]
default = ssh://[uid]@cycle1.cs.rochester.edu//[dir]
default-push = ssh://[uid]@cycle1.cs.rochester.edu//[dir]

To specify your user identity (that is, the authorship of your commits), you can create a file .hgrc under your home directory with the content:

[ui]
username = First Last 
step #2. Generate OpenMP code for shared-memory parallel execution.

Based on Project 2 and 3, your compiler should be able to identify all the loops and do conservative dependence checking for simple loops by now. For the loops your compiler declares there is no loop-carried dependence, you have to parallelize the loop iterations using OpenMP directives. A simple example is following.

    // there is no loop-carried dependence in this example
    // you can parallelize the iterations easily.
    for (i=0; i < N; i++)
       c[i] = a[i] + b[i];

    //your compiler should convert the source code to ( In other words, your *_urcc.c file should be):  

    int chunk = 10; // here, 10 is just an example value. You do not have to follow this value.
    #pragma omp parallel shared(a,b,c,chunk) private(i)
    {
        #pragma omp for schedule(dynamic,chunk) nowait
        for (i=0; i < N; i++)
        c[i] = a[i] + b[i];
     }  // end of parallel section

Please familiar yourself with OpenMP and more OpenMP examples before you start coding. For the loops which has loop-carried dependence which prevent it from being parallelized automatically, you compiler should never output incorrectly parallelized code.

step #3. Advanced transformations for parallelism ( Competition Part. Extra credit for CS255 students ).

By now you have a fairly complete grasp of the theories and techniques for dependence elimination at the loop level and working knowledge of URCC compiler. In the last phase of the project you have the freedom to develop creative and effective solutions to parallelize sequential code aggressively. The results from the test programs and (possible) hidden benchmarks will become part of the growing record of the annual compiler competition, so your compiler competes not only with the compiler from your classmates but also the best and brightest from future years. The following example just give you a general idea of how advanced transformations works for parallelism.

    // there is loop-carried dependence in this example
    for (i=0; i < N; i++){
       t=a[i]+b[i]
       c[i]=t+1/t;
   }
       
    // you can use scalar expansion to eliminate the dependence and get the following code
    for (i=0; i < N; i++){
       t[i]  = a[i] + b[i];
       c[i]= t[i] + 1/t[i];
    } 
    t = t [N-1];

     // then parallelize it as below

    int chunk = 10; // here, 10 is just an example value. You do not have to follow this value.
    #pragma omp parallel shared(a,b,c,t,chunk) private(i)
    {
        #pragma omp for schedule(dynamic,chunk) nowait
        for (i=0; i < N; i++){
            t[i] = a[i] + b[i];
            c[i] = t[i] + 1/t[i];
        }
     }  // end of parallel section
     t = t[N-1];

step #4. Test your transformed program.

I will commit the test cases into your working repository. To run the generated OpenMP programs, you should have following commands at hand.

    gcc -fopenmp loop_urcc.c -o loop
    setenv OMP_NUM_THREADS 4
    ./loop

You can use node4x2a ( node4x2a.cs.rochester.edu ) as your test machine. This machine has four CPU chips, each containing two cores, each further containing two hardware hyperthreads. So each machine includes 16 processors in total. Given its uniqueness, it can be heavily used at times. You should be courteous to others who also use this machine. Specifically, you should always check whether the machine is being used before running your program. Since this machine was purchased primarily for research purposes, you should give priority to those who use it for research.

Project milestones

  • Monday, April 05, final groups formed, and roles assigned.
  • Wednesday, April 07, repository created and initial version of compiler souce code committed.
  • Friday, April 09, design and implementation strategy reviewed.
  • Monday, April 12, first feedback from team leaders.
  • Wednesday April 14, second feedback from team leaders.
  • Friday, April 16, 11:59pm, final code submission.

* Set ALLOWTOPICCHANGE = ChenDing, XiaoyaXiang


This topic: Main > TWikiUsers > ChenDing > CS255Spring10 > CS255Spring10ProjectHome
Topic revision: r17 - 2010-04-14 - XiaoyaXiang
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback