CMSC498X/CMSC818X - Introduction to Parallel Computing (Fall 2020)

Introduction to Parallel Computing (CMSC498X/CMSC818X)

Assignment 3: OpenMP

Due: Monday November 9, 2020 @ 11:59 PM Anywhere on Earth (AoE)

The purpose of this programming assignment is to gain experience in parallel programming on a cluster and OpenMP. For this assignment you have to write a parallel implementation of an iterative stencil computation.

We will use a two-dimensional (2D) Jacobi calculation to simulate heat diffusion. This calculation performs iterative sweeps (called timesteps) over a given array of values. The serial algorithm is described here and you have to implement its parallel version using C or C++, and OpenMP.

Input/Initialization

Your program should read in a file containing the values that will be used to initialize the 2D array of doubles. A sample file is available here. This sample input corresponds to the initial conditions in the figure below. Two regions of size 128x128 are assigned initial values of 212 and 32 degrees F respectively to denote hot and cold zones. All remaining array elements are assigned an initial temperature of 72 degrees F.

Your program should take five command line arguments: the name of the input data file, the number of iterations or timesteps, the X and Y sizes of the 2D array, size_X, and size_Y, and the name of the output csv file. To be more specific, the command line of your program should be:


      ./jacobi2d <input filename> <# of timesteps> <size_X> <size_Y> <output filename>

For the sample file above, size_X = size_Y = 512. You will use OMP_NUM_THREADS to set the number of threads used for parallelism.


      export OMP_NUM_THREADS=X

Serial Computation

At each timestep, the value in each cell (array element) is updated by averaging the values of its four neighbors and itself.


      A[i, j] = (A[i, j] + A[i-1, j] + A[i+1, j] + A[i, j-1] + A[i, j+1]) * 0.2

You can assume periodic boundary conditions so the array elements at the edges will exchange data with elements on the opposite edge.

Output

Your program should write a single file (name set using the command line parameter) that contains comma separated values (up to three decimal points) of the 2D array. Each line in the file should correspond to one row of the array starting with i=0, j=0. This is the correct output file for the sample input file above after 100 timesteps. The only print from your program to standard output should be from the master thread that looks like this:


      TIME: 41.672 s

where the time is measured for the "main" for loop (over 100 timesteps) for the sample 512x512 input file. Make sure that you use "-O2" as a compiler flag for fast timings.

Parallel Version

You can use any OpenMP scheduling policy for assigning work to threads, and even experiment with different policies to study their impact on performance. You can assume that size_X and size_Y are powers of 2, and much larger than the number of threads.

Other sample inputs and outputs after 100 timesteps:

Input 1 Output 1 size_X = 32, size_Y = 32, timesteps = 100
Input 2 Output 2 size_X = 64, size_Y = 128, timesteps = 100
Input 3 Output 3 size_X = 128, size_Y = 256, timesteps = 100

What to Submit

You must submit the following files and no other files:

jacobi2d.[c,C]: your parallel implementation
Makefile that will compile your code successfully on deepthought2 when using mpicc or mpicxx. You can see a sample Makefile here. Make sure that the executable name is jacobi2d and do not include the executable in the tarball. NOTE: assignments without a Makefile will not be graded.
You must also submit a short report (LastName-FirstName-report.pdf) with performance results (a line plot). The line plot should present the execution times to run the parallel version on the sample 512x512 input file (for 1, 2, 4, 8, and 16 threads) for 100 iterations.

You should put the code, Makefile and report in a single directory (named LastName-FirstName-assign3), compress it to .tar.gz (LastName-FirstName-assign3.tar.gz) and upload that to ELMS.

NOTE: If the output file or timing output is not as described above, you will not get any points. Sample timing code below:


    double start, end; 

    start = omp_get_wtime(); 
    ... work to be timed ... 
    end = omp_get_wtime(); 

    printf("TIME %.5f s\n", end - start);

Tips

Quick deepthought2 primer.
Use -g while debugging but -O2 when collecting performance numbers.
omp_get_wtime() example
You can use this Python script to visualize the output csv at any timestep.

Grading

The project will be graded as follows:

Component	Percentage
Runs correctly on 2 threads	10
Runs correctly on 16 threads	40
Performance with 2 threads	20
Performance with 16 threads	20
Writeup	10

NOTE: If your program does not run correctly, you do NOT get any points for performance/speedup.