Home > Papers > Parallel Fractals
Introduction | Mandelbrot Set | Image Characteristics | Parallel Algorithm Design | Partitioning | Agglomeration | Output Synchronization | Token-Passing | Polling | Performance Analysis | Conclusion | Bibliography | Slides
Parallel Fractal Image Generation
Parallel Algorithm Design
We have seen that in order to obtain an accurate image, we need to set the maximum iteration count sufficiently high, especially when zooming deeply into a tiny section of the set – which is necessary to see the most interesting areas of the Mandelbrot set. For example, it can be mathematically proven that the inside of the Mandelbrot set is solid, i.e. all points inside set are connected. The fact that we saw isolated black points and "islands" in the previous images is due to the limited resolution of our calculation. If we zoomed in extremely deep and used a very high resolution and iteration count, we could see some of the points connecting the seemingly "isolated" parts of the set.
Obviously, fractal image generation is computationally expensive. For example, to print a highly accurate black and white fractal image on a letter-size sheet of paper (8.5 x 11") at a resolution of 600 dots per inch, we have to apply the iteration formula to 8.5 * 11 * 6002 = 33,660,000 points, and perform up to 1,500,000 iterations on each of those points, leading to an upper bound of 50,490,000,000,000 (over 50 million million) computations.
While there are several ways to optimize the fractal image generation algorithm, like bailing out of the iteration loop early when it becomes obvious that Z is growing without limit, or if Z has converged, the computation can still take a long time. This is especially true when using the serial approach traditionally used by most fractal plotting programs, with images computed one pixel at a time [TW00].
We assume that parallel processing techniques can help us to reduce the computation time by spreading the workload over several processors. Our goal therefore is to develop a parallel fractal computation algorithm that poses no inherent restrictions on the size of the computation job.
|© 2001 Matthias Book|