Mandelbrot Set: Generation with Multithreading and Analysis

The Mandelbrot set is a mesmerizing pattern of complexity derived from a simple mathematical formula. It consists of complex numbers with a unique property: they either remain confined within a boundary or diverge when plotted. To determine if a number belongs to the set, a straightforward iterative calculation is performed.

For any given point \( c \) on the complex plane, we start with \( z_0 = 0 \) and iteratively apply the formula: \[ z_{n+1} = z_n^2 + c \] Intuitively, as \( n \) increases, the magnitude of \( z \) may grow significantly. However, computing this for each pixel in an image—say, a 3200x3200 resolution with 10.24 million pixels—requires independent, iterative calculations, which can be computationally intensive and time-consuming.

Core Mandelbrot Calculation

int get_mandelbrot(double real, double imaginary)
{
    std::complex<double> c(real, imaginary);
    std::complex<double> z = 0;

    int iter = 0;

    // The core loop!
    while (std::abs(z) <= 2.0 && iter < MAX_ITER)
    {
        z = z * z + c;
        iter++;
    }
    return iter;
}

Upon analysis, it was clear that the calculation for each pixel is independent of others, making it an ideal candidate for parallelization. This independence allows us to leverage multithreading to significantly improve performance.

Modern CPUs have multiple cores, each capable of executing instructions independently. C++ provides access to this power through its <thread> library.

Multithreading Strategy

The strategy for implementing multithreading is as follows:

1. Divide the image into horizontal strips.
2. Assign each strip of rows to a separate thread.
3. Run all threads simultaneously, each computing its portion of the image.
4. Once all threads complete, save the final image.

Each thread is assigned a starting and ending row number, applying the same pixel computation function within its range.

Multithreaded Code Example

// Each thread computes its own row range
void compute_rows(int y_start, int y_end)
{
    for (int y = y_start; y < y_end; ++y)
    {
        for (int x = 0; x < WIDTH; ++x)
        {
            // Map pixel to complex plane
            double real = (x - WIDTH / 2.0) * 4.0 / WIDTH;
            double imaginary = (y - HEIGHT / 2.0) * 4.0 / WIDTH;

            int iter = get_mandelbrot(real, imaginary);

            // Store result in shared image data
            image_data[y][x] = iter;
        }
    }
}

With this row computation code, each thread can contribute to the construction of the Mandelbrot image set, independently. The number of threads were increased chronologically, to see the difference of time of execution in each method. For each thread, it can be called as:

    threads[i] = std::thread(compute_rows, y_start, y_end);
  

Results

I ran the code for my 3200x3200 image with different numbers of threads. Here are the results:

• 2 Threads: 52.40 seconds
• 8 Threads: 35.87 seconds
• 16 Threads: 25.71 seconds