The program in mandel.c draws the Mandelbrot Set using a graphics library called MPE. However, a single process (i.e., process 0) is doing all the work. This week's project is to compare two different approaches to speeding up this computation. More precisely, this week's project is to write two different parallel versions of this program -- one using the Parallel For Loop pattern and one using the Master-Worker pattern -- and see which one is faster.
This program uses MPE, a library that in theory supports parallel graphics on X11 systems, even if those processes are on different machines. However, permitting a remote process to write to your local X-server opens up potential security issues.
Because of this potential security issue, we will do this week's project solely in the Ulab, not on the cluster.
Write one version of the program using the "equal-sized chunks" version of the Parallel Loop pattern to speed up the computation. That is, have each process use its rank and the number of processes to determine which "chunk" of rows it should compute, and then compute those rows.
If it were not for the above-mentioned security problem, each process could draw a pixel as soon as it was computed. Because of the security issue, X11 makes it fairly difficult to display this graphical output in parallel.
The workaround we will use is to have each process compute its "chunk" of values, and then use an appropriate Collective Communication pattern to collect those distributed chunks of pixel-values back into a single block of memory. Process 0 can then use MPE commands to display the resulting image. This almost embarrassingly-parallel approach should minimize the number of transmissions between processes, and provide a good speedup over the sequential version.
However after that, instead of computing another predetermined slice, a worker should (i) send that row to the master, and then (ii) receive from the master the number of the next row it should compute. (Your worker can use the TAG field to communicate the number of the row it computed.) Each worker should continue this cycle until it receives a message from the master whose tag is a sentinel value (e.g., -1), at which point it can terminate.
Once you have both of your programs working, use MPI's timing mechanism to measure how long each approach takes to compute the Mandelbrot Set, excluding all user-I/O. (Since each approach has process 0 drawing the pixels, the time to display the pixels should be the same in both approaches.)
Using a spreadsheet, record your timing results for the two approaches using 1, 2, 4, 8, 16, 32, and 64 processes. Create a line-chart comparing these times of the Parallel Loop approach to those of the Master-Worker approach.
Using those timing results (in the same spreadsheet), compute the speedups and computational efficiencies for each program. Create two other line-charts: one comparing the speedups of the two approaches, and one comparing their computational efficiencies.
As always, label your charts and their axes, and format the lines of your line-charts so that they can be distinguished when the chart is printed on the Ulab printer.
For extra credit:
The file MPEfunctions.c contains some MPE 'drawing' functions that you can use as they are, or as models for your own functions.
To give you sufficient time for all of this, you have two weeks for this project, unlike the previous projects. Your goal should be to complete one of the programs within the first week, so that you have the full second week to complete the second program, conduct your analysis, and pursue any extra credit.
As always, your program should reflect good programming style, be well-documented, and so on.
Hard copies of:
CS > 374 > Exercises > 04 > Homework Project