CS475 Lab 5: Wavefront Parallelization


This lab is intended to give you an hands-on experience on wave-front parallelization. The objectives are
  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. Re-write the loop body for the transformed iteration space.
  4. Verify the functionality of your transformed program.
  5. Insert parallel pragmas for OpenMP parallelization of the transformed program.
  6. 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

Download the Lab5.tar file. It contains the following files.
  1. makefile
    Comment out the lines to compile the necessary files after performing wavefront-parallelization.
  2. prog.c
    It is the same program as we saw in lecture. The sequential code is provided.
    Complete the code for the transformation:
    (i,j->p,t) = (i,j->i,i+j-1)
    by figuring out i,j in terms of p and t. In the given transformed code, t refers to the outer loop and p refers to the inner loop.
  3. timer.c and timer.h


Complete the code to perform Wavefront parallelization. In your lab report,

  1. Show the transformed loop body and dependences.
  2. Explain, how you compute the values for i,j in the trandformed code and why it is correct.
  3. Speed-up on 1-8 processors for N=200,2000,20000 on a state capital machine.
Last Modified: 9/27/2017