CS475 Fall 2009 - Homework 4

OpenMP Programming

Objectives

The objective of this homework is to write three OpenMP programs. The parallelizations of the first two are relatively simple, and the results should be pleasing in terms of performance/speedups. The third program is a bit more challenging.

As always, you should measure the performance of your parallelization as a function of the number of processors and the problem size, and analyze, plot and discuss your observations. For these programs, you may use the department machines for debugging and program development.

1. Jacobi Stencil computation

Parallelize the Jacobi stencil computation from the provided sequential code (see below). Please make sure that you modify the computation as follows. Make sure that the constant EPSILON is small enough (e.g., 10^-6). Also make sure that the convergence test is correct, i.e., the program should stop when the maximum (over all i,j) of the absolute value of the change (i.e., the difference between curr and prev) is less than EPSILON, or if the number of iterations loop exceeds MAX_ITERATION.

Note: You must produce two executables for this program by default. See below for details

2. Row-wise knapsack

Return to the memory efficient program that fills up the knapsack in the row-wise order. Write, debug, analyze and report on an OpenMP parallelization of this program. You should use the knapsack.c provided in the previous homework for this assignment.

3. Needleman-Wunsch

The objective of is to write an OpenMP program for the well known Needleman-Wunsch algorithm for global sequence alignment. The sequential program for a simplified version of the Needleman-Wunsch algorithm is provided below.

Note that the default problem sizes are deliberately small for debugging purposes. Please make sure to change them appropriately when you gather performance data.

Provided Code

Jacobi 2D Needleman-Wunsch

Questions to discuss in your report

How to achieve good load balance
Effect of grain size of parallelization (as per Section 17.4 of the textbook)

What/When/How to Submit:

You should provide a Makefile that compiles your programs by simply typing make, and produces executables jacobi_2D, knapsack and seqalign respectively. In addition, for Jacobi produce jacobi_2D_debug with the debug mode (described below) on. (So typing make produces total of four executables)
The default output should be the same as the output for the sequential code when not in debug mode. The exception is jacobi_2D and the required output for this executable is explained below.
You do need to implement debug mode for Jacobi, slightly different from the debug mode in the provided sequential code. The provided code prints the errors each iteration and the full matrix in the beginning and in the end, but this will be too much output for larger programs. Thus, remove the print statements for the errors, and the initial matrix, and only print a small region of the final matrix. Use the following code to print a small region of the matrix. You can assume that our test inputs will be large enough so that the following code will not crash.
```
    void printMatrix(double *data, int size) {
       int i,j;
	      
	   for ( i=(size/2)-2 ; i < (size/2)+2 ; i++ ) {
            for ( j=(size/2)-2 ; j < (size/2)+2 ; j++ ) {
                 printf("%lf ", data[i*size+j]);
            }
            printf("\n");
	   }
							      
       return;
    }
	
```
The output of the modified debug mode should look like the following.
```
	>jacobi_2D_debug 10
	Final data
	99.995512 99.994896 99.994896 99.995512
	99.994896 99.994196 99.994196 99.994896
	99.994896 99.994196 99.994196 99.994896
	99.995512 99.994896 99.994896 99.995512
	Data : 10 by 10 , Iterations : 206 , Time : 0.000411 sec
	
```
11:59 PM Sunday, Nov 15. OpenMP source files and Makefiles to be submitted via checkin. A detailed description is given above. Please read carefully and make sure that your programs match the description.
11:59 pm, Tuesday, Nov 17. Lab report to be checked in, as well as data and scripts, as per the standard protocol.