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

• Introduction
  • The Mandelbrot Set
  • Fractal Image Characteristics
• Parallel Algorithm Design
  • Partitioning
  • Agglomeration
  • Output Synchronization
    • Token-Passing Synchronisation
    • Polling Synchronization
• Performance Analysis
• Conclusion
• Bibliography
   
• Slides

Downloads

• Paper (PDF)
• Slides (PDF)
• Presentation (zipped PPS)

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.