Project 6 : Parallel Code Generation

Project 6: Parallel Code Generation

Due Date: 04/30/07

Programs should be submitted using the turnin program on csnet.cs.tamu.edu by the announced time. Submissions should be in the form of a single file named project6_XXX.tar.gz file containing the relevant source code (see Creating .tar.gz File below on how to create and submit this file.).

Introduction

In this project, you need to combine all the previous codes (except GCSE) together and generate parallel code on the input program. The previous project codes are linked like this: convert_gotos - bblock - ssa - propagate_constants - ddtest - dessa - codegen. With the results of ddtest, you need to generate parallel directives. To simplify design, the project is broken into two parts:

Combining all previous code. (70 %)
Parallel code generation (30%)

Program Design

Code Generation Function

Note: code generation is not an independent pass. It should be implemented in the cvdl/ddtest directory, such that it is more convenient for you to access the dependence information. However, you should define a function named with codegen in your implementation and it is called in your ddtest pass. When you submit your code, you should submit the new ddtest pass again.

Algorithm Design

The whole algorithm is simple. Basically, there are three steps for generating parallel directives for each do loop:

Find out privatizable scalars by checking if the scalars are written before they are read;
Check if there are data dependences for this loop with consideration of privatization;
If there are no dependences, generate parallel directives for the loop with privatization directives for the scalars (if there is any).

You can read class slides set 11, page 132 and Wolfe book section 11.2.1 to get an idea of privatization.

Parallel Directives

Normally each machine vendor provides his own directives for parallelization. There is also a standard OpenMP for this.

Specifically, there are three directives which should be used: C$DIR LOOP_PARALLEL, C$DIR LOOP_PRIVATE(), C$DIR SAVE_LAST. C$DIR LOOP_PARALLEL directive forces parallelization of the immediately following loop; C$DIR LOOP_PRIVATE declares a list of variables private to the immediately following DO loop; C$DIR SAVE_LAST causes the thread that executes the last iteration of the loop to write back the private(or local) copy of the variable into the global reference. For more information, you can read on-line document Parallel Programming Guide for HP-UX Systems.

In Polaris, each directives mentioned aboved corresponds to an Asssertion: AssertParallel to C$DIR LOOP_PARALLEL; AssertPrivate to C$DIR PRIVATE and AssertLastValue to C$DIR SAVE_LAST. The Statement class keeps a list of assertions which can be accessed by assertions() method. You can insert assertions into the list of assertions associated with the do statement and Polaris will generate corresponding diretives for you automatically.

Example

Here is an source file (Input), test.f:

     PROGRAM TEST
     INTEGER I, J, A(10)
     DO I=1, 10
       J=I*2
       PRINT*, J
       A(I)=J
     ENDDO
     PRINT*, A(2)+A(3), J
     END

The output file, test.polaris.f:

     PROGRAM TEST
     INTEGER I, J, A(10)
C$DIR LOOP_PARALLEL
C$DIR LOOP_PRIVATE(J)
C$DIR SAVE_LAST
     DO I=1, 10
       J=I*2
       PRINT*, J
       A(I)=J
     ENDDO
     PRINT*, A(2)+A(3), J
     END

The first directive tells the compiler that the following do loop: DO I=1, 10 should be run in parallel. C$DIR LOOP_PRIVATE(J) contains the information that variable J need to be privatized. C$DIR SAVE_LAST makes the variable J at the print statement get the value which is assigned at the last iteration of the do loop.

Suppose variable stmt is the reference of DO I=1, 10 and priv_sym is the symbol variable for J. To insert the directives into the above input code, the implementation could be like this:

 AssertParallel * a_parallel=new AssertParallel
 stmt.assertions().ins_last(a_parallel)
 AssertPrivate * a_private=new AssertPrivate
 a_private->arg_list_guarded().ins_last(id(*priv_sym))
 stmt.assertions().ins_last(a_private)
 AssertLastValue * a_last_value=new AssertLastValue
 stmt.assertions().ins_last(a_last_value)

Run Parallel Code

Compiling

On linux:

You can re-compile your files from within the ddtest directory as long as you have compiled mypolaris for once. In another word, there is already a mypolaris generated.

If you have not compiled out mypolaris yet, change to your work directory and make proj5, i.e.

cd ~/minipolaris

make proj5

If you make some changes and want to recompile, just type make at the ddtest directory. Or, if you want to do it from the top-level makefile, you should do (suppose you are at the ddtest directory)

rm libddtest_pkg.so.1

cd ~/minipolaris

make proj5

If you want to compile all your codes including gotos, bblock, ssa, constant, ddtest, dessa as a whole, also change to your work directory and make projall, i.e.

cd ~/minipolaris 

make projall

Creating .tar.gz File

The files necessary for submission should be all source code (.cc and .h) and the Makefiles in the directory cvdl/ddtest in your personal work directory. To create the file proj-codegen.tar.gz, you could create proj-ddtest.tar.gz first and then rename it with proj-codegen.tar.gz. (You can refer to Creating .tar.gz File in project 5 for making proj-ddtest.tar.gz).

Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU