CS 432 Parallel Computing HW 4
Objectives:
To design and implement an efficient multithreaded version of the "Game of Life" program using OpenMP.
Problem Statement:
The objectives of this homework are:
- Design and implement a multithreaded version of the Game of Life program (developed in Homework-1) using OpenMP. The program must take the problem size, maximum number of iterations, and number of threads as command-line arguments. The program must create a parallel region only once, e., you should not create a new thread during each iteration.
- Test the program for functionality and correctness (the output from the multithreaded version must be identical to the single threaded version).
- Measure the performance of the program and optimize the program to improve performance.
- Determine speed and efficiency of the multithreaded version of the program, analyze the performance results, compare the performance with the Pthreads version, and include the analysis in the report.
- Graduate Students only: Implement a two-dimensional distribution of the data using OpenMP and measure the performance for the following grid sizes: 1x16, 2X8, 4X4, 8X2, and 16X1. Analyze the performance across different grid sizes and include this analysis in the report.
Guidelines and Hints:
- Review Chapter 5. Shared Memory Programming with OpenMP in the textbook, download the source code from the textbook website, compile and test the programs on a Linux system (you can use Vulcan machines in CIS for testing). You can also review the OpenMP Tutorial at https://computing.llnl.gov/tutorials/openMP/.
- Test the multithreaded version of the program for small problem sizes (say, 5x5 or 10x10) first by comparing the result with the sequential version (you have to use the same seed in both versions of the program). After you are convinced that your program is working correctly, execute your program on the ASC cluster for 1, 2, 4, 8, 10, 16, and 20 threads and note down the time taken. Use the matrix size 5000x5000 and maximum iterations as 5000 for all the test cases. Compute the speedup and efficiency and plot them separately. Include details on how you computed the speedup and efficiency in the report. Compare the performance on the OpenMP version with the Pthreads version and include your analysis in the report.
- Make sure that you use Vulcan machines in the CIS department for all development and testing and the ASC cluster for obtaining the performance results. When you are testing, you can initialize the matrix and print the output only in the main thread.
- Make sure you submit jobs to the compute nodes using run_script. Do NOT run any jobs on the login node or head node.
- Make sure you comment out any print statements you might have to print the board when you execute with larger problem sizes. Also, execute the program three times and use the average time taken.
- Check-in the final version of your program to the CIS git server and make sure to share your git repository with the TAs and the Instructor.
Program Documentation and Testing:
- Use appropriate class name and variables names.
- Include meaningful comments to indicate various operations performed by the program.
- Programs must include the following header information within comments:
/*
Name:
BlazerId:
Homework #:
*/ Report:
Follow the guidelines provided in Canvas to write the report. Submit the report as a Word or PDF file. Please include the URL to your git location in the report and make sure that you have shared your git repository with the TAs and the Instructor. If you are using specific compiler flags, please make sure to include that in your report as well as README file and check-in the README file to the git repository.
Submission:
Upload the source files and report (.doc or .pdf file) to Canvas in the assignment submission section for this homework. You can create a zip file with all the source files and lab report and upload the zip file to Canvas. There is NO need to turn in any printed copies in class.
Grading Rubrics:
The following grading policy will be used for grading programming assignments:
|
Program Design and Implementation |
50% (program with no compiler errors or logical errors with the required functionality) |
|
Program Testing and Performance Analysis |
30% (includes selecting appropriate test cases, performing the tests, tabulating/plotting/graphing the test results, and analyzing performance) |
|
Report |
10% (documentation of problem requirements, program design, implementation, instructions for compiling, performance analysis, and test cases) |
|
Source Code Formatting |
10% (indentation, variable names, comments, etc.) |
Rubrics for grading the report is as follows:
|
Correct use of English grammar and spelling comprises a baseline requirement for writing. |
20% |
|
Clear exposition of the ideas central to the report (e.g., performance evaluation and analysis) is accomplished. |
20% |
|
Organizational structure at the high-level, mid-level, paragraph level, and sentence level is reviewed for logic, clarity, uniform continuity, and flow. |
20% |
|
The content fulfills the requirements for the technical writing exercise. |
10% |
|
Word and language usage is consistent with a scientific report (formality of word choice, person, attention to audience). |
10% |
|
Appropriate credit to others (references style and content) is required. |
10% |
|
Formatting of the report is appropriate to enable the communication to be effective and professional. |
10% |
