Silicon Fractals

Introduction

A fractal is really nothing more than graph of dots and colors plotted along the x and y axes. They are complex and extremely mathematical to draw, yet beautiful and intriguing to view. For my final parallel programming project, I created Illinois State's first fractal drawing program on the Silicon Graphics machine.

Fractals actually wouldn't be possible without the help of computers, as they are extremely computationally intense. Iteration is the key to creating fractals. Like a simple x y graph, a value (or values) is provided into a function, and the function then produces a new value (or set of values for fractals). Fractal algorithms take those values and then put them through the function again to get a new set of values. This process then continues to infinity, or until we have decided that we have iterated enough times. The result is that each point iterates through a loop that determines its color a certain number of times depending the function and values we initialize the function with. Piece of cake, right?

Benoit Mandelbrot was one of the first to notice that these fractal images were similar to shapes found in nature. Thus, it has been proposed, (the field of fractal study is relatively young) that our traditional Euclidian geometry is the natural way to describe man-made shapes and objects such as squares, triangles, and cubes. Fractals, on the other hand, seem to be the natural way to describe clouds, leaves, and other natural objects (Stevens pg. 19). This paves the way for "Chaos Theory", a philosophy that contends that objects that seem chaotic (or random) in nature can actually be expressed in terms of mathematics. "Fractals appear to provide solutions to many previously unanswered questions at the frontiers of the physical sciences" (Stevens pg. 25).

The Procedure

The fractal algorithm I developed is from the Mandelbrot set and segments of code are borrowed from Roger Stevens' book on fractals and SGI's OpenGL documentation. The fractal algorithm functions in the following way.

Initialize XMax, XMin, YMax, YMin.

The values for these variables will determine which Mandelbrot set will be plotted. There are many interesting combinations listed for these values in Stevens' book (and some commented out in the program source code).

We then initalize the deltaP, deltaQ, P, and the Q[] array using the values just supplied.

These values will be used to generate colors in the heart of the algorithm.

The next step is our first for loop. This loop iterates through the columns.

Now we enter a nested for loop. This loop iterates through the rows.

Now that we are going point by point through the rows, we have entered the heart of the fractal algorithm in deciding which color we are going to plot at this particular point. A while loop is used to iterate either a maximum number of times or up until our function causes us to break out.

Once out of the while loop, we plot our pixel color at the current row and column.

That's it! Now to parallelize this... My approach to parallelize the fractal algorithm was to do so in the second for loop, where we are iterating through the rows. This will give each processor a chunk of code with a while loop without any data dependencies! However, we need to synchronize outside of the while loop to prevent two or more processors from trying to draw to the screen at the same time. The resulting algorithm would look something like this.

The next step is our first for loop.

BEGIN PARALLEL REGION
Now we enter a nested for loop. This loop iterates through the rows.

BEGIN CRITICAL REGION
Once out of the while loop, we plot our pixel color at the current row and column.
END CRITICAL

END PARALLEL

The Results

For those who are interested, here's the source. It is ready and willing to compile.

I was able to create a few images that really captured my eye. Check out the Gallery for some of these.

Is parallelization really worth the time and effort? Decide for yourself. View the Results page.

Summary

Fractals are a new relatively new field. It takes a blend of mathematian, scientist, philosopher, and artist to fully appreciate the beauty, potential and discovery.

Fractal algorithms are easily parallelized, making their discovery and understanding all the more possible.

The fractal algorithm developed here for the SGI achieved a maximum of 2.15 for speedup using 3 processors. In a perfect world, one in which no one else used the SGI machine while I ran my program, we would hope to see better than that. The greatest values in efficiency were always with the use of 2 processors, this may have had something to do with the amount of time it takes OpenGL to execute a write to the screen command.

I couldn't be more pleased with the final product. The algorithm produces large, beautiful Mandelbrot fractal images, and it does it very quickly.

-B

References

Stevens, Roger T. Fractal Programming in C, M&T Publishing, Redwood City, CA: 1989. - This book was lent to me by Dr. Hartman. It's a little old, but it has some good example programs to work from.

Berkowitz, Jeff. Fractal Cosmos - The Art of Mathematical Design, Dharma Enterprises, Oakland, CA: 1994 Lifesmith Classic Fractals. - This book truly got me interested in fractals. It is 90% page after page of beautiful images.

Sprott's Fractal Gallery - A great gallery website with many awesome fractals. http://sprott.physics.wisc.edu/fractals.htm

Carlson's Fractal Gallery - Another great gallery website. This one offers a little more info on how to reproduce the artwork presented. http://sprott.physics.wisc.edu/carlson.htm