Project 4: Mandelbrot Set with OpenMP

COSC 365 · Fall 2026

Due: Tuesday, November 17 at 11:59 p.m. on Moodle

The question

Every pixel in this picture is a separate calculation, and no pixel depends on any other. That sounds like an ideal parallel loop. But some pixels take one step to compute, and others take a thousand. If we split the image into equal pieces, do the threads get equal work? You will parallelize the calculation with OpenMP, measure how the work is shared, and find a schedule that balances it.

The Mandelbrot set drawn as a work map. The set itself is a large bright shape in the center of the image, with a smaller bright disk on its left, surrounded by dark regions that took few iterations.

Work needed for each pixel of the Mandelbrot set. Brighter pixels took more iterations.

This uses reduction and shared and private variables from Module 12, default(none) and dependences from Module 13, and for, nowait, and schedule from Module 14. As with all our OpenMP programs, it runs as one process on one PicoCluster node.

The calculation

Each pixel stands for a point \(c = c_r + c_i\,i\) in the complex plane. Start at \(z = 0\) and repeat \(z \leftarrow z^2 + c\). If \(|z|\) ever exceeds 2, the point has escaped, and it would keep growing forever. The Mandelbrot set is the collection of points that never escape.

We cannot run forever, so we stop after 1,000 steps. The number of steps a pixel takes is its escape time, and it is also the amount of work that pixel costs. A pixel in the dark regions of the picture escapes quickly. A pixel inside the set always costs the full 1,000 steps.

You do not need to know complex numbers to do this project. mandelbrot_serial.c is a complete serial program, and escape_time and compute_row already do the arithmetic:

gcc -Wall -O2 -o mandelbrot_serial mandelbrot_serial.c
./mandelbrot_serial 60 24

The two arguments are the image’s width and height in pixels. Images up to 100 × 60 are also drawn as text, where # marks a point that never escaped. You should see this shape, with these two counts:

                                       ..+...
                                     .....+++.
                                   .....++++.....
                                 ......++###++......
                             ...+++..++++###++++....+.
                        .........+##+############+##+..
                   ............+++#################+...
                ...+....+.....++####################++..
             .......++#++++++++#####################++..
           .....+..++########+######################+...
     ..........+++#+###############################+....
     ..........+++#+###############################+....
           .....+..++########+######################+...
             .......++#++++++++#####################++..
                ...+....+.....++####################++..
                   ............+++#################+...
                        .........+##+############+##+..
                             ...+++..++++###++++....+.
                                 ......++###++......
                                   .....++++.....
                                     .....+++.
                                       ..+...

Image: 60 x 24
Total iterations: 295504
Pixels that never escaped: 286
NoteOnly this small image has fixed answers

For larger images, a few points very near the edge of the set are sensitive to floating-point rounding, so the totals can change slightly with the compiler and its options. That is why your program will compare against its own serial calculation, compiled in the same program.

Write the program

Copy the serial program to omp_mandelbrot.c. Keep escape_time and compute_row unchanged. Your program should accept the thread count, width, and height:

OMP_SCHEDULE="static" ./omp_mandelbrot 4 900 600

Support 1 through 16 threads and the sizes the serial program allows. Reject missing or unsupported input with a clear message. Fixed arrays sized for 16 threads are fine. Your program should do these things, in order:

  1. Compute a serial reference. Fill one array using an ordinary loop over the rows, and time it with omp_get_wtime().
  2. Compute the image in parallel into a second array, timed the same way.
  3. Compare every pixel of the two arrays, and compare the two iteration totals. Print PASS or FAIL.
  4. Print the results described below.

The parallel part

Use a parallel directive with an inner for directive, so that each thread can do something after the loop:

#   pragma omp parallel num_threads(thread_count) default(none) \
        shared(/* you decide */) reduction(+: total_iters)
{
    /* Anything this thread needs of its own */

#   pragma omp for schedule(runtime) nowait
    for (int row = 0; row < height; row++) {
        compute_row(image, row, width, height);
        /* Count the iterations in this row */
    }

    /* Record this thread's iterations and its finishing time */
}

Parallelize the row loop, as shown. The directive must include default(none), so the compiler makes you decide the scope of every outside variable. Use reduction for the total. Do not use critical, atomic, or a lock.

Each thread should store its own iteration count and finishing time in shared arrays such as work[16] and finished[16], indexed by omp_get_thread_num(). A thread that receives no rows should report zero iterations, not garbage.

What to print

Each run should print:

  • The value of OMP_SCHEDULE, using getenv as in omp_sin_sum.c, or (not set).
  • The total iterations and PASS or FAIL.
  • For each thread, its iterations, its share of the total as a percentage, and when it finished.
  • The serial time, the parallel elapsed time, and the speedup (serial ÷ parallel).
  • The load imbalance: the largest thread’s iterations divided by the average per thread. A value of 1.00 is perfectly balanced. A value of 2.00 means that one thread did twice its fair share.

Check that it is correct

Compile with warnings enabled:

gcc -Wall -O2 -fopenmp -o omp_mandelbrot omp_mandelbrot.c

Every one of these should print PASS, and each thread’s iterations should add up to the total:

OMP_SCHEDULE="static" ./omp_mandelbrot 1 60 24
OMP_SCHEDULE="static" ./omp_mandelbrot 4 60 24
OMP_SCHEDULE="dynamic" ./omp_mandelbrot 3 61 23
OMP_SCHEDULE="guided" ./omp_mandelbrot 16 60 3

The 60 × 24 runs should also match the totals shown above. In the last run, some threads may receive no rows. Also test one invalid input, such as zero threads. A PASS on one run does not prove that a program is free of races, so read your code with Module 13’s question in mind: is anything written by one thread and used by another?

Measure the schedules

Before you time anything, look at the picture and write down a prediction: with a block schedule (OMP_SCHEDULE="static"), about what share of the work will each thread get with 2 threads? With 4 threads? Remember that a block schedule divides the rows into equal bands from top to bottom. Keep your prediction, even if it turns out wrong.

Then use a 900 × 600 image. Do all the timing runs on the same node, and run each case at least three times, reporting the median. Other people’s programs can slow yours down, so run hostname and uptime first and report both.

Threads OMP_SCHEDULE
1 static
2 static
3 static
4 static
4 static,1
4 static,10
4 dynamic
4 dynamic,10
4 guided

For each case, report the elapsed time, speedup, load imbalance, and each thread’s share of the work. A shell loop like the one in Module 14 will save you some typing.

Explain your results

About one to two pages is enough. Include your table of results and answer these questions:

  1. Dependences. Is parallelizing the row loop safe? Check using Module 13’s test. Why can every thread write to the shared image array without a lock?
  2. Scope. List each variable used inside your parallel region, its scope, and why. Why does total_iters need a reduction clause? What is it inside the region, and what is it afterward?
  3. Your prediction. What did you predict for 2 and 4 threads with a block schedule? What actually happened? Use the picture to explain the difference between the two cases, and include 3 threads in your explanation.
  4. Balance and speedup. With \(t\) threads and a load imbalance of \(I\), the best possible speedup is about \(t / I\). Explain why. How close do your measured speedups come for each schedule?
  5. Choosing a schedule. Which schedule would you use for this program, and why? The cost of a row does not rise steadily, so why does static,1 do as well as it does? Compare dynamic with dynamic,10. What does the chunk size change here, and how does this compare with the trapezoid experiment in Module 14?
  6. nowait. Why is nowait safe here? What would your finishing times show if you removed it?

If your measurements do not match what you expected, say so, and explain what you checked. An honest surprising result is better than a tidy one.

What to submit

Submit through Moodle:

  • omp_mandelbrot.c, compiling without warnings using the command above.
  • Your explanation, including your results table and clearly labeled output from the correctness runs, with the commands, hostname, and uptime.

Do not submit executables.

Optional experiments

Keep these separate from your required results.

  • Parallelize the inner loop instead. Put a parallel for on the column loop, inside the row loop. How does this change the balance and the time? How many parallel regions does a 900 × 600 image start?
  • Zoom in. Change the constants in compute_row to look at a small region near the edge of the set, such as the area around \(c = -0.75 + 0.1i\). How does the best schedule change when almost every pixel is expensive and uneven?
  • Make an image. Write the escape times to a PGM file, copy it to your own computer with scp, and view it in an image program that opens PGM files.
Back to top