关于算法:CMDA-并行计算

CMDA 3634 SP2021 Parallelizing the Wave Equation with OpenMP Project 03
Project 03: Parallelizing the Wave Equation with OpenMP
Version: Current as of: 2021-03-22 14:30:01
Due:
– Preparation: 2021-03-30 23:59:00
– Coding & Analysis: 2021-04-09 23:59:00 (24 hour grace period applies to this due date.)
Points: 100
Deliverables:
– Preparation work as a PDF, typeset with LaTeX, through Canvas.
– All code through code.vt.edu, including all LaTeX source.
– Project report and analysis as a PDF, typeset with LaTeX, through Canvas.
Collaboration:
– This assignment is to be completed by yourself.
– For conceptual aspects of this assignment, you may seek assistance from your classmates. In your submission
you must indicate from whom you received assistance.
– You may not assist or seek assistance from your classmates on matters of programming, code design, or
derivations.
– If you are unsure, ask course staff.
Honor Code: By submitting this assignment, you acknowledge that you have adhered to the Virginia Tech
Honor Code and attest to the following:
I have neither given nor received unauthorized assistance on this assignment. The work I am presenting
is ultimately my own.
References
The Ising model:
– Section 2.6 of“Parallel Algorithms in Computational Science”by Heermann and Burkitt
✯ Available for free on VT Library site https://link-springer-com.ezp…
book/10.1007%2F978-3-642-76265-9
OpenMP:
– General tutorial https://computing.llnl.gov/tu…
– Reference Book https://mitpress.mit.edu/book…
– Timing https://gcc.gnu.org/onlinedoc…
– General discussion https://pages.tacc.utexas.edu… (14-26)
1
CMDA 3634 SP2021 Parallelizing the Wave Equation with OpenMP Project 03
Code Environment
All necessary code must be put in your class Git repository.
Use the standard directory structure from previous projects.
All experiments will be run on TinkerCliffs. You may develop in your VMs or directly on TinkerCliffs.
Be an ARC good citizen. Use the resources you request. Use your scratch space for large data.
A code solution to Project 2 has been provided in the materials repository.
Any scripts which are necessary to recreate your data must be in the data directory.
DO NOT INCLUDE VIDEO FILES OR LARGE NUMBERS OF IMAGE FILES OR IN YOUR
GIT REPOSITORY!
Your tex source for project preparation and final report go in the report directory.
Remember: commit early, commit often, commit after minor changes, commit after major changes. Push
your code to code.vt.edu frequently.
You must separate headers, source, and applications.
You must include a makefile.
You must include a README explaining how to build and run your programs.
2
CMDA 3634 SP2021 Parallelizing the Wave Equation with OpenMP Project 03
Requirements
Preparation (20%)

1. Write a work plan for completing this project. You should review the coding and analysis sections, as well
   as the remaining assignment schedule between now and the due date. To properly answer this question, you
   will need to take some time and think through the remainder of the assignment. A quality answer should
   require at least half of a page of detail.
   Your work plan should include:
   A brief assessment of the effectiveness of your plan for Project 2. Your new plan should take into
   account what you learned about your working style from the last project.
   A description of the steps you think will be necessary to complete the required tasks, how you plan to
   test those tasks, and an estimate of the time that each task will take.
   An a accounting of the ARC resource requirements. You will need to submit some batch jobs to
   TinkerCliffs (rather than interactive jobs) to get data.
   Any other information you think will be useful to help you work through the assignment.
2. A solution to Project 2 has been provided in the cmda3634 materials repository. Review this solution and
   compare it to the one you submitted. Give at least three (3) specific bullet points describing differences in
   implementation and overall design.
   You should consider things that you learned by making the comparison, what the consequences of different
   design decisions are, and how seeing a different solution may influence your future approach. You should
   consider aspects of structure, style, and syntax.
   However, try not to focus entirely on small, line-by-line, decisions and try not to focus entirely on large-scale
   design decisions. Remember, there is more than one way to do things and just because I do things one
   way, doesn’t mean yours is necessarily wrong. The purpose of this question is for you to learn other ways
   to think about program design, which you cannot do without looking at a lot of code.
3. In the context of OpenMP, where might we find parallelism in our simulation of the wave equation?
4. For a function a(x, y) on an nx × ny grid, the norm of a is
   ka(x, y)k =
   1
   nxny
   vuut
   nXy−1
   j=0
   nXx−1
   i=0
   a(xi
   , yj )
5. (1)
   Give a pseudo-code function for an algorithm for computing the norm of the error between two solutions to
   the wave equation. We can define the pointwise error as,
   e(x, y) = usimulated(x, y) − utrue(x, y). (2)
   The inputs to the function should be the two solutions usimulated and utrue. You may add other inputs if it
   helps.

6. Design a weak scalability study for the case where n = nx = ny. Let P be the number of cores (processors),
   wP be the amount of work on P cores, and nP be the problem size leading to that work load.
   (a) What is the difference between a strong scalability study and a weak scalability study?
   (b) For a single iteration of the wave equation simulation:
   i. Give an approximate expression for wP , in terms of nP . Here are a few hints:
   The expressions depend on total number of grid points.
   Asymptotically, n − 1 and n − 2 are the same as n.
   “Work”is constant for each grid point.
   3
   CMDA 3634 SP2021 Parallelizing the Wave Equation with OpenMP Project 03
   ii. In terms of P and w1, give an expression for wP , the amount of work needed for P processors in
   a weak scalability study.
   iii. In terms of n1 and P, what is nP , the dimension of the problem needed for P processors in a
   weak scalability study?
   iv. If n1 = nx = ny = 2501, what is n2? n4? n8? n16? n32? n64?
   4
   CMDA 3634 SP2021 Parallelizing the Wave Equation with OpenMP Project 03
   Coding (50%)
   For the coding portion of this assignment, you have a choice: you may start your implementation of this project
   from your submitted solution or from the provided solution.
   The source code for your solution is to be submitted via GitLab.
   This project is to be written in the C language, using OpenMP.
   You must include a Makefile in your code directory. This makefile should include targets for each executable
   you are required to produce, a target to compile all executables, and a clean target to remove intermediate
   build files and executables.
   You must include a readme file, explaining how compile and run your code.
   Hint: If you do not want to hardcode the number of OpenMP threads (or if you do not want to take them as
   a command-line argument), you can run your programs by setting the thread count as an environment variable.
   For example, the following command runs the program for 4 threads:

   OMP NUM THREADS=4 ./my program arg1 arg2
   You can also use this style in experiment scripts.
   Tasks:

7. Modify your makefile to enable compilation with OpenMP.
8. Use OpenMP to parallelize your function that evaluates the standing wave solution on a grid.
9. Use OpenMP to parallelize your function that computes one iteration of the wave equation simulation.
10. Implement a function which computes the norm of the error of two wave equation solutions. This function
    should be parallelized with OpenMP.
11. Write a program that computes the time history of the error between the simulated solution and the true
    solution (given by your function for evaluating the standing wave solution). There should be one error value
    for each time-step. You may output the time sequence however you want, but keep in mind that you may
    need to output very long sequences. This program should take n, mx, my, α, and T as arguments. Update
    your makefile to include this program.
12. Update your timing and image output programs:
    Make any necessary changes to use of your parallelized routines.
    Convert your timing functionality to use the OpenMP timing functions.
    Update your program arguments to take nt, the number of time steps to run as an argument in place
    of the final run-time T.
13. Write SLURM submission scripts for generating the required results for the analysis section. You may create
    more than one script!
    5
    CMDA 3634 SP2021 Parallelizing the Wave Equation with OpenMP Project 03
    Analysis (30%)
    Your report for this project will be submitted via Canvas. Tex source, images, and final PDFs should be
    included in your Git repositories.
    All timings and analysis should be from experiments on TinkerCliffs.
    I suggest that you run each of the experiments as separate jobs on TinkerCliffs. Use the early experiments
    to estimate how long the later ones might take.
    Unless otherwise specified, use α = 1, mx = 13, and my = 7.
    You should assume that n = nx = ny.
    Tasks:
14. Run a strong scalability study for n = 2501, nt = 8838, and P = 1, 2, 4, 8, 16, 32, and 64 for your wave
    equation simulation. (nt = 8, 838 corresponds roughly to T = 2.5 at this resolution.)
    (a) You should run a small number of trials per experiment.
    (b) Create plots of both the run-times and speedup. Remember, these are a function of P.
    (c) Does this problem good strong scalability? Justify your claim and explain why you think you observe
    this behavior.
15. Run a weak scalability study for n1 = 2501 (for P = 1), nt = 250, and P = 1, 2, 4, 8, 16, 32, and 64
    for your wave equation simulation. Use your values for nP developed in the preparation phase. (We will
    provide correct values for this.)
    (a) You should run a small number of trials per experiment.
    (b) Create plots of both the run-times and speedup. Remember, these are a function of P.
    (c) Does this problem good weak scalability? Justify your claim and explain why you think you observe
    this behavior.
16. For P = 64 (the total cores on one processor of TinkerCliffs) and P = 128 (the total number of cores
    on 1 node of TinkerCliffs), time the execution of nt = 100 iterations of your Monte Carlo simulator for
    n = 301, 501, 1001, 2501, 5001, 10, 001, and 25, 001.
    Plot your results as a function of N = nx × ny. On separate lines on the plot, include your results
    from Projects 1 and 2. You may either re-run the experiments from Project 1 and 2 for 100 iterations
    or rescale the results so that they are equivalent to 100 iterations.
    Estimate how long it will take to run 100 iterations at n = 100, 000 for P = 64 and P = 128.
    How do the times and estimates compare to those from the serial Python and serial C experiments?
17. For n = 5001, include images from time-steps 100, 500, and 1000.
    You may use as many OpenMP threads as is reasonable to create these images. Report how many
    you chose.
18. Use your program for generating the time history of the error to measure the error for n = 301, 1001, and
19. for T = 2.5. Plot your results. What trends do you see? Why do you think the error oscillates the
    way it does?
    You may use as many OpenMP threads as is reasonable to obtain this data. Report how many you
    chose.
    WX：codehelp