2.3. Generation of Fractals

The algorithm presented here is a problem that can be solved by a data parallel program with the `divide-and-conquer' method. This is, however, not possible with all divide-and-conquer algorithms, since the different branches usually have to carry out different program parts. The algorithm presented here generates a one-dimensional fractal curve using midpoint displacement (see [Peitgen, Saupe 88]). It starts with a straight line, which has its midpoint displaced up or down according to a weighted random value. Two line segments with different slopes arise from this process, and these are handled recursively in parallel in exactly the same way during the following steps (see Figure 14). The number of line segments to be processed doubles at every step, until the required resolution is reached. The processor structure used here is a binary tree structure. Beginning with the root, in each step the following tree level is activated until the leaves are reached. After computing the leaf level, the program prints the result values of the whole tree and terminates. Since with the exception of the communication there is only one tree level active at a time, only half as many PEs would be sufficient with a more complicated connection structure.

A simple tree structure is declared in the Parallaxis program, through which start and end points of the lines are passed (`**' denotes the exponential operator). Only procedure MidPoint is shown, where the actual processing takes place. The tree levels are activated successively, and the midpoint displacement is carried out for each level (using function Gauss not shown here, which returns a gaussian distributed random value). While the leaves have not yet been reached, the data values low and high are passed to the child nodes. In this method, the left child receives the values low and x as the start and end points of its line segment, while the right child receives x and high.

Figure 14 Divide-and-conquer implemented with tree topology 

CONFIGURATION tree [1..maxnode]; 
CONNECTION    lchild : tree[i] <-> tree[2*i]   :parent; 
              rchild : tree[i] <-> tree[2*i+1] :parent; 
 
VAR low, high, x: tree OF REAL; 
 
PROCEDURE MidPoint(delta: REAL; level: INTEGER); 
BEGIN   (* select level *) 
  IF 2**(level-1) <= ID(tree) <= 2**level-1 THEN 
    x := 0.5 * (low + high) + delta*Gauss; 
    IF level < maxlevel THEN
      SEND.lchild (low,low);  (* values for children *)
      SEND.lchild (x,high);
      SEND.rchild (x,low);
      SEND.rchild (high,high);
    END;
  END;
END MidPoint;

Figure 15 Fractal curve generated by program

The computation time required for this program is log2 n steps for n leaf nodes (equal to the tree's height). Figure 15 shows a fractal curve generated by this program with 127 PEs, while Figure 16 shows the beginning of another fractal number sequence interpreted as fractal music.

Figure 16 Fractal music

[ Previous Page | Table of Contents | Next Page ]