HPC Project 4: Combining Patterns

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.

Part I

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.

Part II

Write a second version of the program, this time using the Master-Worker and Message-Passing patterns. More precisely:

Timing The Approaches

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.

Extra Credit: MPE Graphics and Event-Handling

For extra credit:

  1. The program in mandel.c uses just two colors to draw the Mandelbrot Set, but the MPE library supports up to MPE_Num_colors colors, and the MPE_Make_color_array() function can be used to create an array of colors spanning the spectrum. Use these tools to draw points outside the set using different colors, in order to produce more beautiful/interesting visuals. (For example, see Google Images for some inspiration.)

    The file MPEfunctions.c contains some MPE 'drawing' functions that you can use as they are, or as models for your own functions.

  2. The MPE library also provides mouse-sensing functions. For example, it might be convenient if a left mouse-click would "zoom in" to a rectangle centered on the click-point, a right mouse-click would "zoom out", and a middle mouse-click would reset to the original perspective. You can read more about the MPE capabilities in the on-line MPI man pages (at the bottom of the page).

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.

Hand In

Hard copies of:

  1. A 1-page analysis of the performance of your two programs, their behavior as the number of PEs increases, their respective speedups and efficiencies, and anything else you discover that's interesting. As always, make this as quantitative as possible.
  2. Your spreadsheet and charts showing your two programs' timing results, speedups, and efficiencies using 1, 2, 4, 8, 16, 32, and 64 processes.
  3. A script file in which you use cat to list your program, use make to show that it compiles correctly, and then show that it runs correctly using 1 process and 16 processes.
  4. At least one screen capture showing your program's output.
Please staple these pages together and make certain that your name is on each page.

CS > 374 > Exercises > 04 > Homework Project

This page maintained by Joel Adams.