Programming Assignment #1

The Mandelbrot set computation

CSE 160 (Winter 2016)

Changelog

In this assignment you implement the Mandelbrot set computation discussed in class on multiple cores, starting from a provided serial starter code written in C++. Specifically, you'll use C++11 threads to parallelize the code and then conduct experiments, on the Bang cluster, to assess scalability and performance tradeoffs. In the spirit of friendly competition, post your performance results to the A1 Piazza Folder.

The assignment includes a brief report, and the requirements for your report are described at the end of this writeup.

‣ ‣ ‣ Required solution file: pmdb.cpp

This means that the file that contains your solution to the assignment must be turned in by the deadline. It's a good idea to plan to do the assignment well before the deadlines; terminals and tutors can get very busy at the last minute.

In doing this assignment, it's your responsibility to understand the course rules for integrity of scholarship.

You may develop your code anywhere, but you must ensure that it compiles and runs correctly on Bang, because that’s where we’ll be testing it.

Part 1. Getting Started with GitLab

All assignments will be turned in using UCSD's GitLab. The turnin procedure is described below in the section "Turning in your assignment". You must follow these steps to get the starter code and to get set up to do assignment 1.

Refer to the link below for instructions on how to obtain the starter code to get started on your assignment

A1 Git Instructions

Part 2. The Mandelbrot starter code

You have been provided with starter code that implements the serial algorithm. The README file explains the options needed to run the code.

Look over the code so you are familiar with the various modules. The code contains the serial variant which you will use to check correctness of your multithreaded code. This serial variant, in smdb.cpp, calls a low level routine that performs the Mandelbrot set iteration:

ComputeMandelbrotPoint(int x, int y, int dimX, int dimY)

To lessen the risk of error, we recommend that your multithreaded code invokes this same routine to perform the Mandelbrot set computation.

All of your changes will be made to just one file, pmdb.cpp which defines the entry point to a function called Mandelbrot_multiThreaded() that you will implement along with a thread function.

To ensure that your program is correctly graded, do not rely on any changes you have made to any other provided source code files; we will substitute fresh copies when we grade your assignment. Also, don't change the signature of functions defined in pmdb.cpp, as certain provided routines make callbacks to them. It's OK to make changes to provided files besides pmdb.cpp when developing your code, but be sure and refresh them with the provided version before you collect your measurements.

To build your code, use the provided Makefile, as it sets up the appropriate flags for the compiler via an included "arch" file located in $(PUB)/Arch/arch.gnu-c++11.generic. The Makefile produces a target called mdb. Do not change the name of this target. You may add additional source files if you wish, but don't change the names of the any of the provided files.

You may override certain settings, such as compiler optimization, by redefining macros in your Makefile. Within the Makefile, we have provided a commented out line that, if uncommented, will redefine the optimization level. This may come in handy if you want to debug your code using gdb. But don't forget to comment this line out when collecting your timings our your code will run more slowly with optimization turned off!

To compile for debugging with gdb, specify the following argument on the Make command line: dbg=1, i.e.

make dbg=1

Don't forget to do a make clean before rebuilding the code. Otherwise, you may observe anomalous behavior.

2.1 Command line options

The code has various capabilities, which are controlled via command line flags:

-i [number of maximum iterations to compute the Mandelbrot set. Default value: 200] 
-t [number of threads] 
-c [chunkSize] 
-s Run the the provided serial variant instead of the parallel one [default]
-x [number of points to compute in the real dimension. Default value: 1024] 
-y [number of points to compute in the imaginary dimension Default value: 1024] 
-b [bounding box for the computation. Default extent: [-2.5 : 1, -1 : 1]  
-p Plot the results with gnuplot, without saving to a png file
-v Compare the results of the parallel version with the serial version, enabling you to verify code correctness
-o Generate a png file of the computation [output image file name] 

For example,

./mdb -i 500 -t 8 -x 512 -y 512 -b -2.0 0.8 -0.5 0.5 -c 32 -o "output" 

would compute the Mandelbrot set with 8 threads and a maximum of 500 iterations on a computational grid of size 512 x 512. The bounding box's real dimension range from -2.0 to 0.8, the imaginary dimension from -0.5 to 0.5. The -c parameter specifies that block cyclic partitioning is used with a chunkSize of 32. If (-c) is not specified, BLOCK partitioning is used. The results will be plotted and saved in the image file "output.png" which may be viewed with an image previewer. (Note that the color scheme when outputting to a file is different when using on-line plot mode)

./mdb -s -p

2.2 Plotting capability

The plotting capability, controlled via the -p flag, uses gnuplot, and may be useful in debugging. It runs on the main thread only and is not multithreaded. You will need to ensure that your code preserves this constraint or unpredictable results may result. The plotter (Plotting.cpp) interfaces with gnuplot, which is free-ware.

To work remotely, you'll need to use the "tunneling" capability of ssh. If you are connecting to bang from a Linux or Darwin platform using ssh, use the -X option:

% ssh -X yourlogin@ccom-bang-login.ucsd.edu

Remote visual display can be slow if you are off campus. If a display window does not appear on your screen, then your ssh display settings are not set correctly.

Any plots you make will persist unless you close the plot window. This behavior comes in handy if you are comparing plots with different command line parameter settings. However, if you attempt to exit from a qlogin (interactive) node without closing all the plot windows, the process will hang until you close all those windows.

Part 3. Experimentation

3.1 Testing your code

We will grade your assignment on bang. Be sure to do your final testing on that machine, to avoid any surprises at turnin time. When grading your assignment, we will substitute all the files that we asked you not to modify (as noted above) with the original copies of the version we provided you. This is why it is important that you do not depend on change you made to those files, as they will not be available during grading. We strongly suggest you perform some basic testing immediately prior to turnin.

We will test your code's correctness and performance. We will test against the public input described here, plus other inputs that will not be made public. Be sure to test against various combinations of the -x -y, -t and -c command line parameters. You need not handle the case where the number of threads doesn't divide the -y parameter and similarly with the -c chunkSize option.

You can catch obvious errors using the graphical output, but use the -s option to compare results exactly. Only an exact test can be guaranteed to verify correctness; the human eye is subjective, and the visual output may not have sufficient resolution to resolve subtle errors. Verify that results are independent of the number of threads.

3.2 Taking timings

Use the batch queue on Bang to collect timings.

Instructions for setting up your environment on Bang and for submitting jobs are described HERE.

Take timings with the provided timer code (it uses gettimeofday()). Take at least 3 timings for each combination of parameters, and report the minimum timing.

You'll notice that at the end of the run, you'll get a line of output like one of the following , which lists the maximum number of iterations (500), the plotting window (512x512), the running time (0.678493 seconds), whether we are running serially or with multiple threads (S or P), whether we are using BLOCK or BLOCK_CYCLIC decomposition and the bounding box for the computation.

@ 500 512 512 0.678493 S -1.000000 0.800000 -0.500000 0.250000
@ 500 512 512 0.678493 P 4 B  -1.000000 0.800000 -0.500000 0.250000
@ 500 512 512 0.678493 P 4 C 32 -1.000000 0.800000 -0.500000 0.250000

The first line is for a serial run, the second for a parallel run on 4 threads with BLOCK decomposition, and the third run is on 4 threads with Cyclic decomposition and a chunk size of 32.

If you are doing several runs, you can quickly search for the string "@ " (starting in column 1) to extract the performance data from your job output files and process it for plotting (likely with a script). Feel free to post your favorite scripts for extracting and plotting data and organizing your runs.

Do not enable plotting (-p) when you are measuring running times for your performance studies, nor output the result to a file using the -o option as doing so could affect your observations.

3.3 Coding and Experimentation Checklist

1. Write code in pdmd.cpp to implement the multithreaded version of the Mandelbrot set computation. Be sure that you've appended the BASH_PROFILE as explained in the instructions for using Bang, so that you'll automatically get version 4.8.4 of the Gnu compiler suite. To test that you have the correct version, enter the following command: g++ -v. You should see version 4.8.4. identified in the output:

   gcc version 4.8.4 (GCC) 
   

   1. Implement a function, called Mandelbrot_multiThreaded(), to spawn and join threads.
   2. Implement a thread function that the Thread constructor calls when it spawns a thread.
2. Implement BLOCK partitioning (chunkSize=0). You need only support the case where the number of threads evenly divides the Y extent of the computational box.
3. Conduct a strong scaling study, using the default parameters defined in the provided code. Vary the number of threads from 1 to 8, in powers of two. Plot the parallel speedup.
4. Implement BLOCK_CYCLIC partitioning (with support for the chunkSize parameter). You need only support the case where the chunksize evenly divides the Y extent of the computational box.
5. Running on 8 cores, vary the chunkSize parameter from c=1 to c=864, in increasing powers of two. Plot the running time as a function of c Is there an optimal value of c? What is the explanation?
   Use the following parameter settings for this experiment:

   
   -x 512 -y 512 -i 10 -b -2.500000 -0.750000 0.000000 1.000000  
   
   
   -x 128 -y 128 -i 100 -b -2.500000 -0.750000 0.000000 1.000000  
   
   

   This setting results in a more highly imbalanced workload than the default settings of -b, and will enable you to see a much greater improvement with BLOCK_CYCLIC partitioning than with BLOCK.
6. Do another strong scaling study comparing BLOCK and BLOCK_CYCLIC decomposition, using the same parameter settings displayed above for (5). To this end, construct a table or plot comparing BLOCK and BLOCK_CYCLIC decomposition (with c=1) for 2, 4 and 8 cores. To understand the phenomenon you are observing, it may help need to visualize your Mandelbrot sets using the -p or -o option (-p gives an interactive feel, whereas -o is faster but requires that you preview a .png file).


7. Use a different bounding box for this next experiment, by setting the -b parameter as follows:

   -b -2.5 -0.75 0 1
   

   Run on 2, 4 and 8 cores, with c=1. Compare this with BLOCK decomposition (using the same -b setting), putting the observed running times in a table or plot. Explain your results and compare the trends you observed with the previous experiment (6). To understand the phenomenon that your are observing, you will need to visualize your Mandelbrot sets using the -p or -o option (-p gives an interactive feel, whereas -o is faster but requires that you preview the .png file).

8. Report performance. Be sure present to all data in tabular form, as well as in a plot, or, place a label above each data point showing the value of the performance metric you are plotting.

Part 4. Turning in your assignment

4.1 Submission via GitLab

When you have completed the assignment, you must submit it. You will do this by pushing your changes to GitLab. Follow these steps (which are more or less the same as the steps from the "pushing changes to GitLab" section above:

1. Run a ’git status’ to see what files have been changed.
2. Use ’git add <files>’ to stage certain files for a commit, use ’git add .’ to add all files in the working directory to the commit (hopefully you will not be doing this at this late stage—all files should already be in your repository!)
3. Use ’git commit -m "FINAL SUBMISSION"’ to commit the changes to your repository and indicate that you are done and this is your final submission.
4. To push your changes onto your repository on GitLab run ’git push origin master’ Don’t forget this push! You must do this to get credit.
5. As an added safety check, you should log on to GitLab on the web and verify that your push went through.

Some of the finer points about this process:

• Watch out for (and resolve) merge conflicts before your final push!!
  If you have been developing on multiple computers and not syncing with github between switching computers, you will likely get merge conflicts. This happens because your code from one repo is out of sync with your code from another and github doesn't know how to merge the files. You will get these conflicts "at the last minute," because git must sync the code in the repo you're trying to push with the code in the repo you're trying to push to. MERGE CONFLICTS WILL PREVENT YOUR CODE FROM COMPILING. So, even if your code was working perfectly just before you attempted your final push, conflicts will break your code.
  
  It is your responsibility to recognize when you have conflicts (it's not hard--you get a big warning), and to fix them. Please leave yourself enough time to do this.


• If you are submitting with a partner, just push to the joint repository on behalf of both partners. That’s your joint submission.


• Use the commit message FINAL SUBMISSION for your final submission in only one of your individual and partner repositories. You shouldn't be using both anyway, but if you happen to have pushed changes to both, just make sure only one contains the FINAL SUBMISSION commit message.


• If you decide you want to resubmit your assignment before the deadline, just do another commit with the message FINAL SUBMISSION (and don’t forget to push to GitLab!!). We will grade the last commit before the deadline that is tagged as the FINAL SUBMISSION.


• If you submit the assignment within 24 hours after the deadline (i.e. if there is a commit tagged "FINAL SUBMISSION") you will be charged a 10% lateness penalty. . If it is more than 24 but within 48 hours, you will be charged a 20% penalty. After 48 hours, we’ll roll back to the last commit tagged as "FINAL SUBMISSION" that was submitted before the deadline.

4.2 Required files in the submission

1. A PDF document that presents all requested performance data. This file must have the following format. The stem part of the file name (before the .pdf) should begin with "A1-report" and end with you repository name, e.g. A1-report-baden-powell.pdf or, if working alone: A1-report-baden.pdf.

   You may provide data in tabular form only. If you provide a plot, you must still provide the tabular data as sometimes plots can be hard to read. Be sure to provide a caption for each plot or table that describes the experiment you conducted, e.g. "strong scaling."

   Plot your data carefully, plotting only what's necessary to get your points across, and choosing log and linear plots carefully. You must also include any plotted data in tabular form.

   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.

2. Source code. Even though we will be substituting fresh copies of all but one source module, include all code files your worked with, in case we need to unravel a problem with your turnin. For this reason, also include your Makefile.
3. 2 Required text documents

   Your turnin must also include two important documents that accompany the provided code: teameval.txt and DECLARATION.

   1. A file called teameval.txt, a self-evaluation discussing your work. This document addresses the division of labor and other aspects of how you worked together as a team. Be sure to fill it in completely.
   2. A file named DECLARATION, that states that the work was your own, and that you did not violate the Academic Integrity policies in effect for the course. Modify the DECLARATION by filling in your correct login ID(s) and the date only. Don't change anything else.
      

   These documents are required and we will not report a grade for your assignment without them. Be sure to fill in the documents correctly and completely. A 10% penalty will be assessed in cases of missing forms, empty forms, or forms not properly filled out.

Grading

There are 25 possible points on the assignment and your grade will depend on 4 factors: performance attained by your code, correctness, well-displayed results and comments. You must not only put comments inside your code, but every time you commit to your repository. There should be a steady stream of comments that enable us to retrace your development steps.

We will grade your code (on bang) using our own Makefile. Our Makefile will compile your code using g++ and and then link it with a test driver. We will use the same compilation flags as in the provided starter code. Our test driver expects your Mandelbrot_multiThreaded function to satisfy the interface specifications as found in the starter code. To get full credit, design, style and comments (including gitlab commit comments) count.

Frequently asked question, where classmates answer questions

1. Q. While logged into to an interactive compute node via "qlogin", I tried to submit a job: qsub batch_job.sh
   It said "Unable to run job: denied: host "compute-0-11.local" is no submit host. Exiting.“

   A. The batch system won't let you submit a batch job form a qlogin node. If you think about the constraint that a user can run either 1 batch job or 1 interactive login node at a time, you'll see why this makes sense. Your batch job wouldn't run until you logged out of the qlogin node.

[Fri Jan 22 11:07:41 PST 2016]