Distributional Fractal Creating Algorithm in Parallel Environment

Abstract

Nowadays, the fractal is used widely everywhere. Then, its creating time becomes an important study area for complex iteration functions because the escape-time algorithm (ETA), which is the most used algorithm in fractal creating, performs not so well in this condition. In this paper, in order to solve this problem, we improve ETA into the parallel environment and reach well performance. At first, we provide a separation method of ETA to reform it into a SIMC-MC2 grid. Secondly, we prove its correctness and compute the complexity of this novel parallel algorithm. Meantime, we separate an improved ETA which we have presented into the same parallel environment and compute its complexity. Additionally, theoretical and experimental results show the characteristics of this novel algorithm. Finally, the computational result shows that a novel environment is needed to decrease large manual allocation strategies, which block the improved benefit.

1. Introduction

Since Mandelbrot presented the Mandelbrot set (M set), which is the dictionary of all Julia sets [1], the fractal has been soon used everywhere for 30 years. Nowadays, thinking and algorithms, which are generated by fractal, have been used in many science domains. Today, two algorithms are generalized and used when fractals are created [2]. One is the escape-time algorithm (ETA), and the other is the iterated function system (IFS). Although IFS is a fast algorithm, it can be only used in fractals with a certain iteration strategy. However, admittedly, a lot of fractal iteration functions are uncertain in practical applications. So the ETA becomes the most universal and effective algorithm in creating fractal where the iteration functions are complex.

In order to decrease the creating time of ETA, we reform ETA into the parallel environment to improve its speed and effectiveness in this paper. At first, we should show the ETA by Algorithm 1 [2].

Algorithm 1: The escape time algorithm.

Step 1. Assuming N as the escape threshold number, M as the max iteration number,

$m_z=\mathit{0}$ as the iteration number of point z and $N_z=z$ as records of $f^n(z)$ .

Step 2. For all points z in complex plane,

   While $m_z\le M$ and $\left|N_z\right|<N$

    Let $m_z=m_z+\mathit{1}$ . $N_z=f(N_z)$ .

Step 3. Color all points z with color strategy of $m_z$ .

Algorithm finished.

In this way, we know that ETA is such an algorithm that uses the escape threshold and the max iteration number to create fractals. Then, it colors all points in the displayed area with different colors. These colors are different with different iteration times under a given color strategy. Finally, if $m_z>M$ , the point z is convergent, and if $m_z\le M$ , the point z is divergent.

Earlier on, to solve some defects of ETA, we have presented an improved algorithm (IA) to remedy the following two defects [3].

•  

  Defect a. The convergent points have to perform max iterations.

•  

  Defect b. When the iteration midresults are in the computed regions, ETA wastes existing computations.

Although IA remedies these two defects of ETA, its performance is also not so well when the iterated function is more complex and the displayed area is larger. For example, we use two iteration functions to create fractals with IA: one is in [4, 5], and the other is the one we created in [6]. We have these two results, and we show them in Tables 1 and 2. We can see that the fractal creating times enlarge greatly when we enlarge the displayed area and compute more points. From the bold data in Tables 1 and 2, we can see that these data are so large that we cannot wait for a so long time for these fractals in practice. Then, we know that there are more images that need more points to compute. So we have to reach a novel method to solve them.

Table 1

Runtimes of the two functions with ETA.

Iteration functions	$f(z)=(\mathit{1}/\mathit{2})z{\mathit{3}}^{{\sin }^{\mathit{2}}(\pi z/\mathit{2})}$	$f(z)=(\mathrm{1}/\mathrm{2})(z{\mathrm{3}}^{{\sin }^{\mathrm{2}}(\mathrm{\pi }z/\mathrm{2})}+{\sin }^{\mathrm{2}}(\mathrm{\pi }z/\mathrm{2}))$
Displayed area/points’ number	$\left(-\mathit{1},\mathit{1}\right)\times (-\mathit{1},\mathit{1})/\mathit{640}\times \mathit{640}$
Runtime(s)	16.887	139.242
Displayed area/points’ number	$(-\mathit{2},\mathit{2})\times (-\mathit{2},\mathit{2})/\mathit{1280}\times \mathit{1280}$
Runtime(s)	67.353	573.460
Displayed area/points’ number	$(-\mathit{4},\mathit{4})\times (-\mathit{4},\mathit{4})/\mathit{2560}\times \mathit{2560}$
Runtime(s)	278.441	2318.005

Table 2

Runtimes of the two functions with IA.

Iteration functions	$f(z)=(\mathrm{1}/\mathrm{2})z{\mathrm{3}}^{{\sin }^{\mathrm{2}}(\mathrm{\pi }z/\mathrm{2})}$	$f(z)=(\mathrm{1}/\mathrm{2})(z{\mathrm{3}}^{{\sin }^{\mathrm{2}}(\mathrm{\pi }z/\mathrm{2})}+{\sin }^{\mathrm{2}}(\mathrm{\pi }z/\mathrm{2}))$
Displayed area/points’ number	$(-\mathit{1},\mathit{1})\times (-\mathit{1},\mathit{1})/\mathit{640}\times \mathit{640}$
Runtime(s)	3.165	6.287
Displayed area/points’ number	$(-\mathit{2},\mathit{2})\times (-\mathit{2},\mathit{2})/\mathit{1280}\times \mathit{1280}$
Runtime(s)	12.914	24.102
Displayed area/points’ number	$(-\mathit{4},\mathit{4})\times (-\mathit{4},\mathit{4})/\mathit{2560}\times \mathit{2560}$
Runtime(s)	52.411	101.578

We analyze these large runtimes in Tables 1 and 2, and we find that the phenomenon of these results is due to the large extra space, which stores the midresult of IA by an   $n\times n$ matrix ( $n\times n$ is the computational points number). So the extra matrix becomes too large to compute when we enlarge the computational points (the displayed area).

In order to consider a novel method to decrease computational complexity, we admit that the parallel environment is a suitable way to solve this problem [7, 8]. Furthermore, it is more suitable in fractals [9]. This is because many fractals have highlighted characteristics and fit into parallel environments. For example, symmetrical characteristics are owned by many generalized Mandelbrot sets [10, 11], Julia sets [12], and other fractals [13].

So, in this paper, we separate and improve ETA and IA into parallel environments with a separation method at first. Moreover, we prove their correctness and compute their complexity. Then, we use some well-known generation method in the experiment. Finally, we discuss the experiment result by our conclusion.

The remainder of this paper is organized as follows. We present a separation method of both ETA and IA in Section 2. Moreover, we have their parallel experimental results and analyses in Section 3. Finally, Section 4 summarizes the main results of this paper and presents the following study objectives.

2. Separation Method of ETA and IA

In order to reform ETA and IA into parallel environments, our separation method can be given by 4 steps.

Step 1 (dividing computations into tasks).

In this step, we divide computations into a class of tasks. The strategy makes all processes busy as far as possible without much supervisory cost. In this way, parallel structure is constructed.

Step 2 (distributing tasks among processes).

The objective of this step is to load balance between processes in task distribution. The balanced load contains computation, input/output, data access and communication, and so forth

Step 3 (applying coordination, communication, and synchronization of data).

Coordination decreases the cost of communication and synchronization. Moreover, in order to increase locality of data access, this strategy must finish those tasks earlier, which depends many tasks.

Step 4 (mapping processes into processors).

From Steps 1–3, we get a complete parallel algorithm which can control mappings from processes into processors. Otherwise, this work is executed by OS. Of course, this mapping is for a certain system or environment.

So, in order to run ETA and IA in parallel environments, we should distribute them in parallel forms. In this paper, we use the SIMC environment to distribute them and the separation method of ETA and IA. We show the separation method in Algorithms 2 and 3. To simplify without loss of solution, we divide the displayed area into $p(n)$ parts by horizontal lines.

Algorithm 2: Separation method of ETA.

Primary node

For all task nodes

 Send group message ( $x_{\text{start}}$ , $x_{\text{end}}$ , $y_{\text{start\_}i}$ , $y_{\text{end}\_i}$ , f) to ith

task nodes;

    - - $y_{\text{start\_}i}=y_{\text{start}}+(i-\mathit{1})*\mathrm{int}[(y_{\text{end}}-y_{\text{start}})/p(n)]$

        - - $y_{\text{end}\_i}=y_{\text{start}\_i+\mathit{1}}-\mathit{1}$

 - - $x_{\text{start}}$ , $x_{\text{end}}$ , $y_{\text{start}\_i}$ , $y_{\text{end}\_i}$ are all pixel numbers (positive integer),

       f is iterated function/mapping

While all task nodes send its result

 Connect all sub-images and display it;

Finished;

Task nodes

If primary node send message ( $x_{\text{start}}$ , $x_{\text{end}}$ , $y_{\text{start\_}i}$ , $y_{\text{end}\_i}$ , f)

 Use ETA to create sub-image by compute all points

in this area with iterated function f;

Send sub-image to primary node;

Finished;

Algorithm 3: Separation method of IA.

Primary node

For all task nodes

 Send group message ( $x_{\text{start}}$ , $x_{\text{end}}$ , $y_{\text{start\_}i}$ , $y_{\text{end}\_i}$ , f) to ith

task nodes;

    - - $y_{\text{start\_}i}=y_{\text{start}}+(i-\mathit{1})*\mathrm{int}[(y_{\text{end}}-y_{\text{start}})/p(n)]$

        - - $y_{\text{end}\_i}=y_{\text{start}\_i+\mathit{1}}-\mathit{1}$

While all task nodes send its result

 Connect all sub-images and display it;

Finished;

Task nodes

If primary node send message ( $x_{\text{start}}$ , $x_{\text{end}}$ , $y_{\text{start\_}i}$ , $y_{\text{end}\_i}$ , f)

 Use IA to create sub-image by compute all points in

this area with iterated function f;

 {

  $\mathrm{\Delta }x+i\mathrm{\Delta }y=f(x+iy)$ ;

 While $\mathrm{\Delta }y\in (y_{\text{start\_i}},y_{\text{end}\_i}$ ) and $m_{x+iy}<M$ ;

   $f(x+iy)=f(\mathrm{\Delta }x+i\mathrm{\Delta }y)$ , $m_{x+iy}=m_{x+iy}+m_{\mathrm{\Delta }x+i\mathrm{\Delta }y}$ ;

 If $\mathrm{\Delta }y\notin (y_{\text{start\_i}},y_{\text{end}\_i})$ and $m_{x+iy}<M$ ;

  Send message ( $\mathrm{\Delta }x$ , $\mathrm{\Delta }y$ , i, Need) to jth node;

      - - $j=\mathrm{int}[\mathrm{\Delta }y/(y_{\text{end}\_i}-y_{\text{start}\_i}+\mathit{1})]$

 If receive message ( $x,y,j$ , Need)

  Send message ( $\mathrm{\Delta }x$ , $\mathrm{\Delta }y$ , $m_{\mathrm{\Delta }x+i\mathrm{\Delta }y}$ ) to jth node;

        - - $\mathrm{\Delta }x+i\mathrm{\Delta }y=f(x+iy)$

 If receive message ( $\mathrm{\Delta }x$ , $\mathrm{\Delta }y$ , $m_{\mathrm{\Delta }x+i\mathrm{\Delta }y}$ )

   $f(x+iy)=f(\mathrm{\Delta }x+i\mathrm{\Delta }y)$ , $m_{x+iy}=m_{x+iy}+m_{\mathrm{\Delta }x+i\mathrm{\Delta }y}$

 If $m_{x+iy}>N$

   $m_{x+iy}=N$ ;

 }

Send sub-image to primary node;

Finished;

After these two separation methods are presented, we process our experiment by constructing a parallel environment with the same 9 PCs (personal computers). In our experiment, one PC is a primary node, and other 8 PCs are task nodes. Then, all subresults are connected to the primary node as the final result.

In our experiment, in order to decrease communicational cost, we find that the communications are mostly between the task nodes; that is, there is no need for the primary node.

3. Parallel Experiment and Analysis

3.1. Parallel Parameters

At first, we have some parallel evaluating indicators of a parallel algorithm. In the following evaluating indicators, n is the scale of the problem:

• (a)

  running time $t(n)=t_r+t_c$ , where $t_r$ is routing time of data by network or memorizer and $t_c$ is the computing time of arithmetic and logic in processors;

• (b)

  number of processors $p(n)$ , which obeys the exponential distribution by defining $p(n)=n^{1-e}\hspace{0.17em}\hspace{0.17em}(0<e<1)$ ;

• (c)

  parallel cost $c(n)=t(n)·p(n)$ , which is called the best cost when the time complexity of executing cost is same between the existing parallel algorithm and the worst serial algorithm.

• (d)

  speedup ratio $\text{SR}(n)=\text{WS}(n)/\text{WP}(n)$ , where $\text{WS}(n)$ is the worst time cost with the best serial algorithm and $\text{WP}(n)$ is the worst time cost of the parallel algorithm with the same problem; easily saying that $1\le \text{SR}(n)\le p(n)$ and that the parallel algorithm is better when $\text{SR}(n)$ is larger;

• (e)

  parallel efficiency $\text{PE}(n)=\text{SR}(n)/p(n)$ , which is used to measure utilization efficiency of processors in a parallel algorithm;

• (f)

  parallel flexibility measures, which is the relation between n and $\text{PE}(n)$ by a steady $p(n)$ , calling an algorithm flexible when $\text{PE}(n)$ increases linearly by n.

3.2. Experiments with $T(z)$ and $B(z)$

Then, we execute fractals of (1) and (2) as our experiments. The creating fractals are given in Figures 1 and 2.

Figure 1

Fractals of (1).

Figure 2

Fractals of (2).

In our experiments, we left the primary node free for computations, and we only granted it with the authority, which is the connection with another 8 worker nodes. The connection is done under the SIMC strategy with ETA and the MIMC strategy with IA. This is because ETA needs fewer communications. In ETA, the primary node only sends the computational area to the task nodes. Meantime, the task nodes do not have any other communications. In this way, ETA can be executed with single instruction. On the contrary, IA needs many communications by the worker nodes. So we use multiple instructions in it.

We have the running time of every fractal image, which are created by (1) and (2) in Tables 3 and 4 with the different algorithms ETA and IA. Every running time contains both serial time and parallel time:

$$\begin{array}{cc}& f_1\left(z\right)={\frac{\mathrm{1}}{\mathrm{2}}z\mathrm{3}}^{{\sin }^{\mathrm{2}}(\pi z/\mathrm{2})},\end{array}$$

(1)

$$\begin{array}{cc}& f_2\left(z\right)=\frac{\mathrm{1}}{\mathrm{2}}\left({z\mathrm{3}}^{{\sin }^{\mathrm{2}}(\pi z/\mathrm{2})}+{\sin }^{\mathrm{2}}\frac{\pi z}{\mathrm{2}}\right).\end{array}$$

(2)

We compare the running times of ETA and IA with iteration functions (1) and (2). Then, we compute the evaluating indicators of these two algorithms. We use $p(n)=8$ as the constant. So we only discuss $c(n)$ , $\text{SR}(n)$ , $\text{PE}(n)$ , and PF (parallel flexibility) in our paper.

Table 3

Running time of ETA.

Iteration functions	$f(z)=(\mathrm{1}/\mathrm{2})z{\mathrm{3}}^{{\sin }^{\mathrm{2}}(\mathrm{\pi }z/\mathrm{2})}$	$f(z)=(\mathrm{1}/\mathrm{2})(z{\mathrm{3}}^{{\sin }^{\mathrm{2}}(\mathrm{\pi }z/\mathrm{2})}+{\sin }^{\mathrm{2}}(\mathrm{\pi }z/\mathrm{2}))$
Displayed area/points’ number	$(-\mathit{1},\mathit{1})\times (-\mathit{1},\mathit{1})/\mathit{640}\times \mathit{640}$
Runtime(s)
Serial	16.887	139.242
Parallel	2.326	17.710
Displayed area/points’ number	$(-\mathit{2},\mathit{2})\times (-\mathit{2},\mathit{2})/\mathit{1280}\times \mathit{1280}$
Runtime(s)
Serial	67.353	573.460
Parallel	8.594	72.135
Displayed area/points’ number	$(-\mathit{4},\mathit{4})\times (-\mathit{4},\mathit{4})/\mathit{2560}\times \mathit{2560}$
Runtime(s)
Serial	278.441	2318.005
Parallel	35.260	291.462

Table 4

Running time of IA.

Iteration functions	$f(z)=(\mathrm{1}/\mathrm{2})z{\mathrm{3}}^{{\sin }^{\mathrm{2}}(\mathrm{\pi }z/\mathrm{2})}$	$f(z)=(\mathrm{1}/\mathrm{2})(z{\mathrm{3}}^{{\sin }^{\mathrm{2}}(\mathrm{\pi }z/\mathrm{2})}+{\sin }^{\mathrm{2}}(\mathrm{\pi }z/\mathrm{2}))$
Displayed area/points’ number	$(-\mathit{1},\mathit{1})\times (-\mathit{1},\mathit{1})/\mathit{640}\times \mathit{640}$
Runtime(s)
Serial	3.165	6.287
Parallel	1.694	3.556
Displayed area/points’ number	$(-\mathit{2},\mathit{2})\times (-\mathit{2},\mathit{2})/\mathit{1280}\times \mathit{1280}$
Runtime(s)
Serial	12.914	24.102
Parallel	7.063	14.381
Displayed area/points’ number	$(-\mathit{4},\mathit{4})\times (-\mathit{4},\mathit{4})/\mathit{2560}\times \mathit{2560}$
Runtime(s)
Serial	52.411	101.578
Parallel	28.623	54.279

We know that $c(n)=t(n)·p(n)$ and $p(n)=9$ . So we have Figure 3 to show their costs individually. Moreover, we show $\text{SR}(n)$ in Figure 4 using the times $\text{WS}(n)$ and $\text{WP}(n)$ in experiments. Then, we need not compute $\text{PE}(n)$ because it is only a constant coefficient different from the $\text{SR}(n)$ . Finally, we use Figure 5 to present parallel flexibility with equation $\text{SR}(n)/n$ .

Figure 3

Running time to compare between ETA and IA with these two iteration functions into these two environments.

Figure 4

Speedup ratio to compare between ETA and IA with these two iteration functions.

Figure 5

Flexibility to compare between ETA and IA with these two iteration functions into these two environments.

Then, with these results, we have that the speedup ratio of ETA is better than that of the IA (in Figure 4), and that of the running time of IA is smaller than that of the ETA (in Figure 3). Admittedly, the upper bound of the speedup is $p(n)=9$ . It is to say that parallel ETA still has space in speedup ratio. Contrarily, the speedup ratio of IA is lower because there are too many communications between worker nodes in parallel IA. However, it reduces $t_r$ , but it increases $t_c$ . Then, we have to say that speedup ratio is smaller when worker nodes are more.

Moreover, from Figures 4 and 5, we can see that the two absolute flexibilities of the two algorithms are not so well. Especially, flexibility of IA is worse. But this does not this mean that their complexities are nearly linear. So the two relative flexibilities of the two algorithms are well.

Finally, the created fractals are the same as in Figures 1 and 2. So we do not present them with additional figures.

3.3. Experiments with Generalized M Sets

After the experiments with $T(z)$ and $B(z)$ , which are two iteration functions about the generalized $3x+1$ functions, we reach the final experiment of the generalized Mandelbrot sets with exponent k (k-M set). Similarly, in order to validate effectiveness of the novel algorithm, we process a k-M set with $k=2.47$ in serial ETA (SA), serial IA (SIA), parallel ETA (PA), and parallel IA (PIA). The fractal image of k-M set is given in Figure 6.

Figure 6

Fractal image of the k-M set with $k=2.47$ .

Then, we use Figure 7 to present the eight subresults of the k-M set. It also validates the correctness of PIA.

Figure 7

Subfractal image of the k-M set with $k=2.47$ .

In fact, the k-M set is a fast creating fractal. In this way, we do not present the creating time for these four methods (SA, SIA, PA, and PIA) because they are mixed and hard to discuss. In this paper, we only compute $\text{SR}=\text{WS(SA)}/\text{WP(PA)}$ and $\text{flexibility}=\text{SR}/n$ of them. We present them in Figures 8 and 9. In Figure 8, we present SR of the k-M set, and, in Figure 9, we present the flexibility of the k-M set.

Figure 8

Speedup ratio to compare between ETA and IA with the k-M set, where $k=2.47$ .

Figure 9

Flexibility to compare between ETA and IA with the k-M set, where $k=2.47$ .

In Figures 8 and 9, we also use $n=640\times 640$ , $1280\times 1280$ , and $2560\times 2560$ .

In Figures 8 and 9, we also use $c(n)=t(n)·p(n)$ and $p(n)=9$ with any n. So we have SR₁(n) = WS(SA)/WP(PA) = c(SA)/c(PA) and SR₂(n) = WS(SIA)/WP(PIA) = c(SIA)/c(PIA) in Figure 4 by using the cost time instead of WS and WP in experimental results. Then, we use Figure 9 to present parallel flexibility with equation $\text{SR}(n)/n$ .

Then, with these results, we also have that speedup ratio of ETA is better than that of IA (in Figure 8). Then, we find that the SR of the k-M set is smaller than those of $T(z)$ and $B(z)$ . This is because the creating time of the k-M set is small. Meantime, the distributional time comes to a larger ratio. So SRs are decreasing. But we also find that the SR of IA is larger. This is because of the local attractiveness of the k-M set. Moreover, it is similar that the speedup ratio of IA is lower than that of ETA. This is also because there are too many communications between worker nodes in PIA.

Moreover, from Figure 8, we compute flexibilities of the two algorthims, and we find that both of them are not so well. Then, we can also find that two relative flexibilities of the two algorithms are well.

4. Conclusion

We constructed a parallel environment to run the distribution fractal creating algorithms ETA and IA by static task distribution strategy. Then, we compared these two parallel algorithms by some parallel evaluating indicators. Although there were many communication redundancies in IA, experiment results show that both ETA and IA can increase their speed and efficiency with a better environment.

The next step is to avoid communication redundancies, so we will transplant ETA and IA into a cloud environment. We will process this transformation since we have computed a universal computational complexity of fractal creating methods by iteration conditions. It is a new way to use inner mechanism in the cloud environment to avoid outer communication. Furthermore, we will present a special novel algorithm for the generalized Mandelbrot sets with rational number exponent when we have its structural characteristics.