HPC MPI Homework 5 at Calvin College

HPC Project 5

Overview

In this two week project, we want to accomplish several things:

Solve a problem using domain decomposition;
Solve the same problem using processor farm model; and
Introduce MPE, the MPI graphics library.

To do so, we'll provide you with a sequential program that generates the Mandelbrot Set. Your assignment is to "parallelize it" and use MPI's collective communications operations, as appropriate.

Exercise

Each pixel of the Mandelbrot Set can be computed independently, making them ideal candidates for parallel computation.

Save a copy of display.h, display.c, mandel.c, and Makefile. Study the source code in mandel.c, run it, and compare its behavior with its source code until you understand how it is doing what it's doing.

Homework

mandel.c draws the Mandelbrot Set using MPE graphics. However, a single process (i.e., process 0) is doing all the work.

Part I. Rewrite the program, using the domain-composition model to "parallelize" it. That is, write a version of the program in which each PE uses its rank to determine which rows it should compute. Issue: Can individual PEs write to the graphics window in parallel (the way individual PEs wrote to the console in the circuit program)?

If so, have each PE display the rows it computes.
If not, designate one PE as the "I/O PE", and have it "gather" the rows from the other PEs and display them. (Issue: If the number of rows is not evenly divisible by the number of PEs, is it better for the I/O PE to process these "remainder" rows while it is awaiting results from the other PEs, or is it better for the other PEs to process them?)

In other words, make this program as embarrassingly parallel as possible. Minimize the number of transmissions between PEs, and think carefully about how to make this program run as fast as possible for a given number of PEs.. Does the order in which you compute the rows make any difference?

Part II. Then write a second version of the program, this time using the processor farm approach, in which you "farm out" the computation by rows. Your "master" process should send out a row number and receive back WINDOW_SIZE integers from each "slave".

Once you have both of your programs working, add code to time the computation of the Mandelbrot Set, excluding any user-I/O. Thoroughly test your code's correctness in the U-lab; then scp it to dahl for actual execution. Record and chart your timing results for 1, 4, 8, 16, and 32 PEs.

Extra Credit: MPE Graphics and Event-Handling

For extra credit:

The MPE library provides mouse-sensing functions. For example, it would be convenient if a mouse-click would "zoom" in to a rectangle around the click-point. You can read more about the MPE capabilities in the on-line MPI man pages (at the bottom of the page).
The MPE library also provides limited graphical capabilities. The program in mandel.c uses just two colors to draw the Mandelbrot Set. Use more colors to draw points outside the set, in order to elicit more beautiful/interesting visuals. (E.g., see Google Images for some examples.)
The file MPEfunctions.c contains some MPE 'drawing' functions that you can use as they are, or as models for your own functions.
Rewrite the faster of your two programs using an OO approach, with the core functionality in a "model" class, separate from the "view" and "controller" classes.

Hand In

Your source code for the two programs;
A single spreadsheet chart showing the timing results for your two programs for 1, 4, 8, 16, and 32 PEs;
A 1-page analysis of the performance of the two programs, and their behavior as the number of PEs increases; and
At least one screen snap showing your program's output.

Up to the HPC Homework Page

Up to the Calvin HPC Course Page

This page maintained by Joel Adams.