CSE-443/543: High Performance Computing
Homework #04
Max Points: 73
Note:You should save/rename this document using the naming convention MUid.docx (example: ferrenam.docx).You will be modifying this file and uploading it as part of your submission to Canvas for this homework.
Objective: The objective of this exercise is to:
•Build experience developing a non-trivial parallel code using OpenMP
•Gain experience using the CSE C++ style guidelines
•Build experience with benchmarking parallel programs
•Gain experience using spreadsheets for scientific data analysis
Fill in answers to all of the questions.For almost all the questions you can simply copy-paste appropriate text from the shell/output window into this document or the associated spreadsheets. You may discuss the questions with your instructor and the TA.
Background
In class, you have learned about OpenMP and have done a several labs and a homework assignment to gain experience compiling and running programs in OpenMP.As for Homework 03, you will write a non-trivial program from scratch and then implement it in OpenMP in two different ways.
The program you are writing will determine an estimate for π by using Monte Carlo integration to calculate the area under a quadrant of a circle.Your prep work for Session 18 included information on how this works and we discussed in class as well.You will be parallelizing this code using OpenMP.The way I am asking you to write the code involves two nested loops, and as with Homework 03 you will write code that parallelizes each of these loops, comparing the performance of the resulting program.
Some comments and hints:
•The inner loop of your code will “throw” 1,000,000 “darts” to determine an estimate of π as discussed in Session 18.
•Your outer loop will repeat this computation N times and your code should take N as a command line argument. You should use N = 10000 for the final version you submit for this homework.
•Your program should also have a second command line argument, the random number generator seed to use.This seed should be declared as an unsigned int variable.
•This means that you should run it as, for example, ./monte_omp 10000 1234567
•For your code to work correctly you will need to use a thread-safe random number generator.I am giving you starter code (monte_omp_stub.cpp) that implements the drand48_r random number generator.It may be to your advantage to build your code around this file.
•Your code must adhere to CSE Programming Guidelines for C++.You can test this by running your program through the cpplint.py style checker.To get full credit for this assignment your code must pass the following checks:
•No errors when checked with cpplint.py
•No errors or warning messages when compiled with these options
–O3 –std=c++ -Wall -fopenmp
•It must give the reasonable answers
•As with recent labs and homeworks, you should enter your raw data and perform your analysis in the spreadsheet provided.You can get either a Microsoft Excel or a LibreOffice version from Canvas.You should submit your spreadsheet in its native format, not as a PDF.
•You should implement a method called monteCarloIntegration that takes a single argument (N, the number of runs of 1,000,000 tosses to do.It should return a double value which is the value of pi determined for the run.
•When you write out the value of pi determined by your run, use the setprecision method to set the precision to 10.
•You will be doing two versions of your program, one parallelizing the inner loop (that goes over the 1,000,000 dart throws) and the other going over N (which will be 10,000 for your final runs).
•When parallelizing the inner loop, you will need private and reduction variables.
•When parallelizing the outer loop, I suggest that you use two threadprivate variables in addition to private and reduction variables.
•I am providing you with a shell script that can be tweaked to do your standards compliance checking, compilation and timing runs.You may want to check this script out as it uses some features of bash that you may not have encountered elsewhere.
•Unlike previous labs and homeworks, I am not giving you step-by-step directions for the experiment.You’ve done enough of these that you should no longer need them to meet the requirements.
•Since some of you didn’t remember this:I stop answering questions about the assignment 24 hours before it’s due.You have two weeks to complete this homework so there should be no need to rush at the end unless you choose to wait.
Experiment
Develop the programs requested and generate timing data for them.In each case you should run the program for 1 through 8 threads and do 5 timing runs.
Apparatus
The experiment documented in this report was conducted on the following platform (fill in the two lines of the Details column using information determined in your shell script):
Component
Details
CPU Model
Main Memory (RAM) size
Observations
Enter the raw timing data from your runs into the spreadsheet provided.
Analysis
Compute the requested quantities and enter them into the spreadsheet provided.
Discussion
Did you observe a statistically significant difference in run times comparing your programs that parallelized the inner and outer loop?Support your answer using data from your experiment and appropriate statistical methods.If you observed any “strange” timing behavior, also comment on it in this section.
Submit files to Canvas
Upload the following files to Canvas:
•This MS-Word document (duly filled with the necessary information) saved as PDF using the naming convention MUid.pdf.
•Your homework spreadsheet, saved as MUid.xlsl or MUid.ods
•Your OpenMP C++ code that parallelizes the inner loop of the Monte Carlo integration.
•Your OpenMP C++ code that parallelizes the outer loop of the Monte Carlo integration.
Reviews
There are no reviews yet.