CS475 Lab 8: Wavefront Parallelization exercises

Objectives

1. To analyze and draw the data-dependencies in the given program.
2. Redraw the dependence graph from the given iteration space to time and processor iteration space.
3. Express the given and transformed iteration space in terms of inequalities.
4. Find the loop bounds of the transformed iteration space using "inside out" method discussed in lecture.
5. Re-write the loop body for the transformed iteration space.
6. Verify the functionality of your transformed program.
7. Insert parallel pragmas for OpenMP parallelization of the transformed program.
8. Measure the performance(speed-up on 1-8 processors) of the parallel code to that of the given code on State-capital machines.

Provided code

1. makefile
   Comment out the lines to compile the necessary files after performing wavefront-parallelization.
2. prog1.c
   It is the same program(Example-1) as we saw in lecture. The sequential code and the wavefront-parallelized code for the transformation discussed in lecture is provided.
   You have to insert the code for the transformation (i,j->p,t) = (i,j->j,i+j-1).
3. prog2.c
   It is a 3 dimensional loop structure. The sequential code is provided.
   You have to work out the wavefront-parallelization technique discussed in class and insert the code corresponding to it.
4. timer.c and timer.h

Description

In the given 2 programs, insert the code to perform Wavefront parallelization. In your lab report,

1. Show the transformed loop bounds.
2. Speed-up on 1-8 processors for N=200,2000,20000.