Papers
Papers
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
A Study of Generating Sequential Data With Parallel Algorithms

Term Project for the Parallel Processing class (CS 580) at The University of Montana - Missoula, presented May 3, 2001.

This paper discusses algorithms to implement an in-order output of sequential data generated by a parallel program, using the example of fractal image generation. After an introduction to the mathematics of fractals, a parallel algorithm that spreads the workload evenly among processors and produces a sequential output is developed. In order to achieve the latter, several synchronization techniques (blocking and non-blocking token passing, non-blocking polling) are examined for their suitability, and polling synchronization is identified as the only certain way to realize an in-order output. A subsequent performance analysis shows that the parallel algorithm achieves an overproportional speedup over serial algorithms, since the non-blocking communication introduces a second layer of parallelization.

HTML Version

Downloads

Note: The slides were presented before work on the project was completed. Thus, they do not cover the performance analysis and the insight that polling synchronization is required to achieve an in-order output.

© 2001 Matthias Book