This Assignment consists of 2 parts. In Part A you will implement data parallelism (with the display turned off) and measure computational speedups. In Part B you will implement the parallel display functionality.
In this part you have to modify your functionally parallelized program from HW2. Turn OFF plotting for this part.
The computation has to be divided among several processors. This should be a one-dimensional decomposition where the computational domain must be divided (approximately) equally between all processors involved in the computation. You can configure the processors in a way similar to what the Ring program does.
In each iteration, the updates made at each point on the computational mesh depend on neighboring mesh values. At the boundaries of each processor's part of the mesh, you will have to create and use ghost cells. At each iteration, message passing between adjacent processors must be used to populate these ghost cells with appropriate values from neighboring processors.
You will need to time your programs. This can be done by using the MPI_Wtime() function. (Please look at the Ring program to understand how to use this timer function call.). Place the timers around the main computational loop in the code. Measure running times on each processor separately, combine them at the end (using a Reduce call), and pick out the maximum. This will give you the overall running time of the entire program.
You can create computationally intensive runs by using the following padv command-line parameters.
(1) padv -nx 500 -ny 500 -vx 1 -nt 100
(2) padv -nx 1000 -ny 1000 -vx 1 -nt 100
Measure running times on 1,2,4 and 8 processors, for the above problem sizes of 500x500 and 1000x1000. (Problem size is defined as the number of mesh points updated at each iteration : nx x ny). Remember to turn OFF display for Part A of this assignment.
Plots to turn in
(1) Plot the observed running times as a function of the number of processors, for both problem sizes.
(2) Plot the speedups observed for these measurements as a function of the number of processors..
To get accurate timings, you may need repeat your runs a few times to make sure that you get similar timings for every run. If they vary a lot, then take the average of at least 3 different runs. Prior to collecting timings, you should 'warm up' the machine. To do this, you should run your program a few times in succession and discard the timings obtained from the first run.
In this part, you will implement the display functionality, thus combining data and functional parallelism.
There will be only one display server. All computation processors will have to send their part of the updated mesh to the display processor. The display processor will accumulate the data from all the computation processors before displaying it.
In HW2 you must have noticed that plotting takes a lot of time. Along with data parallelization, this corresponds to a large 'serial section' which cannot be parallelized, and this will limit the speedups you can get. So in this part, allow your plotter to display only once every 20 iterations.
Test your parallelized plotter function using the following command-line to padv.
(1) padv -nx 100 -ny 100 -vx 1 -nt 50
You do not need to measure running times or speedups for PartB of this assignment. (A detailed performance analysis of your implementation based on Amdahl's law, will be included in your next programming assignment).
Ring calls MPI's timer function MPI_Wtime() to measure message passing times (as wall clock times), Your timings will reflect interference from other jobs. On a dedicated run, such interference will be minimal; running times will be shorter and reproducible. We aren't yet able to make dedicated runs, however. So run the program several times until you see consistent results. If you are still having difficulties getting consistent results, try running on other nodes. You should use no more than 4 nodes for this experiment.
To get an absolute time take the difference in times sampled by two successive calls to MPI_Wtime:
double t0 = MPI_Wtime();
// some code....
double t1 = MPI_Wtime();
double time = (t1-t0);
The man-page for MPI_Wtime() is found on line. Note,
however, that all times are reported in seconds, and there is no need to
divide by MPI_Wtick() to convert to seconds. (You can
obtain the resolution of MPI_Wtime using
MPI_Wtick())
NOTE: Please make sure that you begin taking your timings as soon as possible. As the assignment deadline approaches, many students will be simultaneously trying to run their programs and time them, and they will interfere with each other in terms of getting accurate timings. One way to smooth this out a bit is to generate and use a random list of compute nodes in your machine-file list.
NOTE: If you have previously set up a ~/.ssh/config file, to ensure correct X11 forwarding (for the plots to appear on your terminal), gnuplot must be instantiated on the correct compute node. This can be done in two steps. First, make sure that the compute node listed as the first entry in the machine-file matches the compute node listed on the first line in the config file. This ensures that this compute node is the one which will be assigned rank=0. Second, in your code, let the process with rank = 0 be the one that runs gnuplot and does the plotting.
Document your work in a well-written report which discusses your findings carefully. Your report should present a clear evaluation of the design of your code, including bottlenecks of the implementation, and describe any special coding or tuned parameters. Further, it should present your timing and speedup observations, with an analysis that describes your understanding of how the speedups (or any other effect you observe) were obtained. Provide code listings for files you wrote, or that you modified based on versions we gave to you (there is no need to provide listings of code we provided, that you did not modify).
Your report should cite any written works or software as appropriate in the text of the report. Citations should include any software you used that was written by someone else, or that was written by you for purposes other than this class.
Provide a hard copy in class. Also transmit the report electronically along with your code. We will run the code on Valkyrie. Transmit a single filePlease tar your writeup, plots, and source code and email them to cs160x1@valkyrie.ucsd.edu. The name of your tar file should be your Login ID.tar. Your archive file should create a directory with the name of your login ID. Be sure and delete all .o files and executables before creating the tar file.
The directory should contain two subdirectories (If you want to provide us additional information about the turnin, you may include a README file):
""src" : All source code
"report" : Your report including any separate plot files or output
If you like, you may put an html file called index.html at the top level. From there you can then link to the README file to the src and report directories. .
The hardware platform for the course is a Beowulf cluster named Valkyrie which is managed by ACS. To learn how to use Valkyrie, be sure to read this very important web page which will tell you how to compile and run MPI programs: Getting Started with Valkyrie.
Software for the course will be placed in a public directory, which you may access from your home directory as ~/../public. The software for this assignment lives in various subdirectories of ~/../public/examples.
Also see two other web pages with links to software available in the course as well as references and other valuable on-line sources of information.. These are found at:
As always, refer to the document titled Getting Started with Valkyrie for detailed instructions on how to set up your environment, and how to use MPI.
MPI documentation is found at at http://www-cse.ucsd.edu/users/baden/Doc/mpi.html.. You can obtain man pages for the MPI calls used in the example programs described here:
Copyright © 2004 Scott B. Baden. Last modified: 04/07/04 04:03 PM