CS475 Fall 2011 - Homework 5

Parallel Program for the Needleman-Wunsch algorithm

Objectives

The objective of this homework is to write an MPI program for the well known Needleman-Wunsch algorithm for global sequence alignment. You should also develop a good understanding of wavefront parallelization using MPI.

Problem Statement

The sequential program for a simplified version of the Needleman-Wunsch algorithm is given here. Note that the problem sizes there are deliberately small for debugging purposes. You should develop a final program that blocks the iteration space into into tiles of height h and width w, where w is floor(N/P) (N is the size of one input sequence and P is the number of threads/procesors) and h is a command line argument. Each processor is responsible for the computation of a column of blocks. A processor should not start calculating a block until the previous processor has given it the data it needs for that block. Processor 0 is exempt to this rule, since it already has the input sequence. You should submit two programs.

Program1 The simple version where the tile height is fixed to 1. Slides 20-23 of the lecture notes cover this case. This is worth half the points on the assignment.
Program2 A generalization for program 1 which accepts the tile height as a command line argument. This requires you to allocate buffers for the communication and to modify the code so that the first (and last) columns in a tile red from (write to) the receive buffer (send buffer). This is worth half the points on the assignment.

Your code should conform to the following:

Your programs should take the following information as command line arguments:
1. alphabets : size of alphabets in sequences.
2. N : size of the first input sequence.
3. M : size of the second input sequence.
4. h : tile height, optional argument, with default 1.
Your program should print (wrap the other prints in the provided code into the ifdef debug option):
- Final cost
- Running time of the main loops.
Please use this: Makefile

What/When/How to Submit:

11:59 PM Sunday, Nov 13. Code is due.
11:59 PM, Tuesday Nov 15 Report plus updated code.

How to Submit:

You must submit the file from one of the Linux machines, such as crestone or dmx.
All assignments are submitted electronically via the ~cs475/bin/checkin program.
You must submit a single tar file containg all of your source code and your Makefile.
You must name the tar file as HW5.tgz
You may resubmit the file as many times as you like. Subsequent submissions will not overwrite previous submissions.Please do not modify the filename when resubmitting.The system will take care of it.
If you have more than one file for your program, then you should provide a makefile that will compile all executables. Your executables should contain names as described previoudly. Any assignment submitted that contains code that will not compile will receive a 0%.
The checkin program should be used as follows:
~cs475/bin/checkin HW5 HW5.tgz

How to tar files:

Enter the directory that contains the files you want to submit.

Use the command:

 tar czvf HW5.tgz [file1] [file2] [file3] ..

Use the command:
```
 man tar
```
for more information.