The black figure in the 2D graphic above is called the Mandelbrot Set, named after the mathematician Benoit Mandelbrot who created early visualizations of it. The values of the (x,y) points within this figure can be determined by a simple but non-linear iterative function f(x,y). For each (x,y) within the central part of the figure (shown in black), the values produced by f(x,y) converge; for each (x,y) outside of that central area (shown in shades of blue), the values produced by f(x,y) never converge (i.e., they diverge toward infinity). The boundary between these regions of convergence and divergence (shown in gold in the figure above) is a fascinating chaotic recursive fractal that contains many patterns similar to those found in the natural world. Check out the Mandelbrot Set Wikipedia page for more information.
In the source folder for this project, the file mandel.cpp is a C++ program that draws the Mandelbrot set. This is a traditional sequential program; a single-threaded process is doing all the work. This one-week project is to create and compare two different approaches to speeding up this program:
The program uses a graphics library developed here at Calvin University called the Thread-Safe Graphics Library, aka TSGL. Other graphics libraries are not thread-safe, meaning if two threads try to perform graphical calls at the same time, the program will likely crash. To support multithreaded graphical programming, we developed TSGL, which lets different threads safely perform simultaneous graphics calls in approximately real-time.
Since TSGL is only installed in Calvin's CS labs, you will need to do this week's project using one of the CS lab workstations or one of the remote-access Guacamole systems; you cannot do this project on the cluster or your own machine (at least not without installing TSGL).
Make a new project folder and download the files from this folder to your project folder. Look over the statements in mandel.cpp to see how it is structured.
Use the provided Makefile to build the program; then run it. You should see the Mandelbrot set drawn using Calvin colors (i.e., a gold figure on a maroon background).
Your first task is to measure how long this sequential program is taking to compute and draw the Mandelbrot set. Where MPI had the MPI_Wtime() function to measure 'wall clock' time, OpenMP has the omp_get_wtime() function that behaves in a similar fashion. Modify the program by adding calls to omp_get_wtime(): (i) after the first printf() near the begining of the program, and (ii) just before the printf() statement near the end of the program. (Since this is an OpenMP function, you will need to #include <omp.h> as well; the Makefile is already set up to utilize the OpenMP library.) Then modify that final printf() so that it displays the total time the program takes to compute and draw the Mandelbrot set.
When you have this working, open up a spreadsheet, run the program three times, record the times in the spreadsheet, and then use the spreadsheet to compute the median of those times. We will use this as a baseline to compare against our parallel versions, and as the T1 value in our SpeedupT computations.
In a separate folder, make a copy of mandel.cpp (e.g., mandelChunks.cpp) and modify it to use OpenMP's "Equal Chunks" Parallel Loop to speed up the computation. You should have no problems doing this if you have completed this week's lab.
Note that each iteration of the Mandelbrot computation is independent of the others. In a multithreaded version, a thread can compute and draw the pixels in its 'chunk' of the window without interacting with any other threads, making this an embarrassingly-parallel problem. It follows that this approach should provide a good speedup over the sequential version.
For convenience, we want to be able to control the number of threads the program uses when we run the program. Using the examples you explored during this week's lab, add logic near the beginning of your program (i.e., before the first printf()) that passes the number of threads the user species on the command-line as an argument to the omp_set_num_threads() function. Then modify that first printf() so that is displays the number of threads being used.
Finally make a copy of the project Makefile and adjust it so that it builds your new program.
With these changes, you should be able to specify the number of threads when you run your program; for example, if your program is named mandelChunks, to run it with 1 thread you would enter:
./mandelChunks 1to run it with 2 threads, enter:
./mandelChunks 2to run it with 3 threads, enter:
./mandelChunks 3and so on. If the user neglects to specify the number of threads on the commandline, you should display a "Usage" message that shows them how to run the program and then either terminate abnormally, or proceed using a single thread as the default number of threads.
Run your program a few times with different numbers of threads (or no commandline arguments) to verify that it is working correctly.
When you have Version I of your program fully debugged, you are ready to begin time-trials!
Time Trials. For each thread-value T = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12: run your program three times and record those times in your spreadsheet.
Then use the spreadsheet to compute the medians of those times.
Then use those medians and the medians you computed for the sequential version to compute the SpeedupT for each value of T.
Finally, use your SpeedupT values to compute the EfficiencyT for each value of T.
Create a second parallel version of the program, but use OpenMP's version of the "Slices" (aka Chunk-size 1) Parallel Loop in this version.
Run your program a few times using different numbers of threads. If you look carefully at how it is drawing the Mandelbrot set and compare its behavior to that of your "Chunks" version, you should see different graphical behaviors from the two versions. Make certain this new version is working correctly before starting the time-trials for this version.
As always, make certain that both of your programs follow good style guidelines, are well-documented, etc.
Time Trials. For each thread-value T = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12: run your program three times and record those times in your spreadsheet.
Then use the spreadsheet to compute the medians of those times.
Then use those medians and the median you computed for the sequential version to compute the SpeedupT for each value of T.
Finally, use your SpeedupT values to compute the EfficiencyT for each value of T.
Now that we have collected data for both versions, your next task is to determine which approach (if either) works better for this problem.
To visualize your data, use your spreadsheet to create the following line-charts:
As always, give your charts descriptive titles and label their axes. Make certain the lines for each version can be clearly distinguished on a gray-scale printer by using different line-styles (e.g., solid vs. dotted).
Here are some things to keep in mind as you analyze your results:
Hard copies of:
Please staple these pages together and make certain that your name is on each page.
CS > 374 > Exercises > 05 > Homework Project