CSE 160/260 Programming Assignment #2

CSE 160/260: PROGRAMMING ASSIGNMENT #2

Due Date: 5/7/99 11:59 PM

The goal of this assignment is to learn how to implement an embarrassingly parallel program using a manager/worker model and the dynamic load balancing technique, work queue. As with the last assignment, this assignment will be done individually.

Resources:

Embarrassingly parallel programs are described in your book in Ch. 3
Work queue is also known as work pool in your book (in sections 3.2.2 and 7.2).
Be sure to check the announcements page often for hints, clarification of assignment, etc.
Great web sites to find images to use in this assignment:
- Dmitrii Zagorodnov's photography page
- Walfredo Cirne's photography page

Assignment description: Edge detection algorithm

You will perform an edge detection algorithm using the Sobel operator as described on pg. 342 in your text. Below shows an example of the edge detection algorithm using an image off Dmitrii Zagorodnov's web page:


INPUT IMAGE	OUTPUT IMAGE

The algorithm: Each image is an MxN matrix of pixel values.

----------------
| x0 | x1 | x2 |
----------------
| x3 | x4 | x5 |
----------------
| x6 | x7 | x8 |
----------------

To compute the value of each pixel in the resulting image for a number of various image processing algorithms, the following format is used:


      (w0 * x0) + (w1 * x1) + (w2 * x2) + (w3 * x3) + (w4 * x4) + (w5 * x5) + (w6 * x6) + (w7 * x7) + (w8 * x8)
x4' = ---------------------------------------------------------------------------------------------------------
                                                          9

The values w0,...,w8 are referred to as a mask.

----------------
| w0 | w1 | w2 |
----------------
| w3 | w4 | w5 |
----------------
| w6 | w7 | w8 |
----------------

The edge detection algorithm using the Sobel operators requires 2 masks

----------------          ----------------
| -1 | -2 | -1 |          | -1 | 0  | 1  |
----------------          ----------------
| 0  |  0 | 0  |   and    | -2 | 0  |  2 |
----------------          ----------------
| 1  |  2 |  1 |          | -1 | 0  | 1  |
----------------          ----------------
   mask 1                       mask 2

Each mask is performed on the original values of the image. Say the result of the value of a pixel after applying mask 1 is x4'' and the result of the value of a pixel after applying mask 2 is x4'''. Then the value of x4' is the addition of the absolute values of x4'' and x4''':

x4' = |x4''| + |x4'''|

How do you handle the border values? Just put a border of 0's around the image(also known as ghost cells). More about this will be presented in discussion.

Why can we use an embarrassingly parallel solution for this algorithm? In order to determine the value of each pixel, we require the values of the pixel itself and its surrounding 8 pixels (also known as a 9 point stencil). So, each pixel is dependent on the other values in the image. However, when we hand out a work chunk (described below) to a process, we can give it all the values it needs, so there is no need to communicate among processes (except of course, to hand out the work and retrieve it...more on this below as well). So, for example, suppose we have the following image and we divide the image into 9 chunks:
```
+---------------+---------------+---------------+
|		|		|		|
|      P0	|	P1	|	P2	|
|		|		|		|
|	       +-----------------+		|
+--------------|+---------------+|--------------+
|	       ||		||		|
|	P3     ||	P4	||	P5	|
|	       ||		||		|
|	       ||		||		|
+--------------|+---------------+|--------------+
|	       +-----------------+		|
|	P6	|		|		|
|		|	P7	|	P8	|
|		|		|		|
+---------------+---------------+---------------+
```
All we need to do to make work chunks independent of each other (and thus embarrassingly parallel) is to send the border values of the the neighboring work chunks.
Why use work queue? The machines you are running on (at least in the uAPE lab) are heterogenous and also will be operating under differing load values. So, the time each processor takes to process work chunks will most likely be different. This lends itself to the load balancing technique work queue. More on this will be presented in discussion. In work queue, we divide up the problem into XxY work chunks where X evenly divides M and Y evenly divides N.
The manager/worker model: In this project, your processes will consist of one manager and multiple workers. The manager is responsible for distributing the work to each processor throughout the computation and collecting the results. The manager should be able to handle varying chunk sizes determined by command line inputs. Each worker is responsible for receiving an arbitrary work chunk size from the manager, performing the computation, and sending the result back to the manager. Each worker will be expected to process work chunks until it is notified by the manager that the entire compuatation is complete.
A serial version of this program is available for you in $PUBLIC/edge

Images:

Input and output images will be in ascii PGM (Portable graymap file format). You can find more information about PGM in the man pages by typing 'man pgm'. Briefly, a PGM file looks something like the following.
```
<magic number><whitespace><width><whitespace><height><whitespace><max gray value><whitespace><width*height gray pixel values>
```
So, for example,
```
P2
1024 768
255
168 169 169 169 169 169 169 169 169 169 170 170 171 171 171 171 176
...
```
- magic number: The file format id...P2 stands for PGM in ascii format
- width/height: The dimensions of the image in ascii format
- max gray value: in ascii format
- width*height gray pixel values: Integers from 0 to <max gray value> separated by whitespace
- Note: Lines should not exceed 70 characters
- Note for 260 students: The following variables will need to be set in your .cshrc file in order to see the man pages on PGM and to use any PGM tools (if you want to use them).
```
setenv PBM /usr/local/netpbm
setenv MANPATH ${MANPATH}:${PBM}/man
setenv PATH ${PBM}/bin:${PATH}
```
Sample images will be available in $PUBLIC for you to use. (Since, you are supplied with the serial code, you can generate output images for yourselves). If you would like to use other images, you can use xv to generate PGM files for you.

Command line format:

You should be able to specify the input filename, the output filename, and the work chunk size via command line inputs. The command line should be of the following form:

mpirun -np <num> -machinefile <machines> pedge_detect -i <input filename> -o <output file name> -x <width of work chunk> -y <height of work chunk>

Timings:

You will be required to time the total execution time of your program (the manager can handle this). In addition, for each process, you will be required to time the overhead time (communication time + idle time) and the computation time. These timings will come in handy for your next programming assingment which will be about how to get better performance out of your program. No specific format is required for these timing messages. Also, feel free to insert any other additional timing messages that you think are important.

Instructions for turning in programming assignment #1:

Tar up your makefile and your source code (i.e. no *.o's and no executables).

160 students: Use the turnin in command
```
turnin -c cs160s <tarfile>
```
260 students: turnin it in the same way as you did for the first assignment

Grading:

Due to the size of this class and the limited number of computers available for you to work on (for CSE 160 students), extra credit will be offered as an incentive to turn in your program early. So, if you turn in your assignment before 11:59 PM on April 30, you will receive an extra 5%.