Mon. Jan 17th, 2022

# Mandelbrot Set in HLS

Nov 28, 2021

The Mandelbrot set is a group of complex numbers c for which the sequence number generated by the quadratic recurrence equation shown in ‎(1)  does not diverge to infinity.

$Z_{n+1}=Z_n^2+c \;\;\;\;\;\;\;\;$ (1)

$Z_0=0$

The following code shows the pseudo-code of the algorithm generating the Mandelbrot set. This algorithm consists of a for-loop in which each iteration checks the convergence of Equation ‎(1).

for each $c=x+iy \in$ Complex Numbers
if $z_{n+1}=z_n^2+c$ converge

Each loop iteration should generate a sequence of complex numbers using a loop structure whose trip count may be infinite.

Different algorithms have been proposed to generate the Mandelbrot set. One of the most straightforward algorithms is the escape time algorithm, in which each iteration checks the value to see whether it has reached an escape condition. If the condition is reached, then the most inner loop stops and a colour is assigned to the generated point based on its behaviour. The colour determines how fast the corresponding point reached the escape condition. As the number of iterations in the escape time algorithm can be very large, considering a maximum trip count limit for the loop statement makes the algorithm feasible to run on a computer.

If we show a complex number with a point in a 2D coordinate, then the Mandelbrot set can be shown by an image. If and represent the real and imaginary parts of a complex number, respectively, then the following equations ‎determine the coordinates of the numbers in the sequence

$c=x_c+iy_c$

$Z_n=x_n+iy_n$

$Z_{n+1} =Z_n^2+c=(x_n+iy_n)^2+x_c+it_c$

$Z_{n+1}=(x_n^2-y_n^2+x_c)+i(2x_ny_n+y_c)$

$x_{n+1}= x_n^2-y_n^2+x_c$

$y_{n+1}=2x_ny_n+y_c$

The Mandlebrot set is usually studied and plotted in a 2D small region around the centre, for example,    $x=-2$ to $1.25$ and $y = -1.25$ to $1.25$. Therefore, the coordinate of the image representing a Mandelbrot set should be scaled into this region. The following code shows the pseudo-code for the algorithm plotting a Mandelbrot set. The $x^2+y^2>4$ represent the escape condition.

for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
int x_c  = scaleX(i);
int y_c  = scaleY(i);

int x := 0.0
int y := 0.0
int iteration := 0
int max_iteration := 1000
while (x*x + y*y ≤ 4 && iteration < max_iteration) {
float xtemp = x*x - y*y + x_c;
y = 2 * x*y + y_c;
x = xtemp;
}
if (iteration == max_iteration) {
// This point is in the Mandelbrot set as it did not escape so its colour is black
out[i*width+j]     = 0; // black colour
} else {
// This point is not in the Mandelbrot set as it escaped
// So its colour is based on how quickly it escaped
out[i*width+j]  = 256-iteration%256;
}
}
}



The entire code can be synthesised with an HLS tool, and it will be executed sequentially, mainly because of the while-loop statement which cannot be unrolled. To address this issue, the while-loop iteration can be modified as shown in the following code. The most inner for-loop in this code can be fully unrolled if  max_iteration is a small number. In this case, the outer nested loops can be flattened and pipelined to get the maximum performance of the synthesised HLS code. In addition, for a large value of max_iteration, the most inner for-loop can be partially unrolled and pipelined. In this case, the outer nested loops can be flattened and executed sequentially.

for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
…
for (iteration_i  = 0; iteration_i < max_iteration; iteration_i++) {
float x2, y2, z;
x2=x*x;
y2=y*y;
z = x2 + y2;
if (z > 4 && flag == 0 ) {
diverge_iteration = iteration_i;
x_out_local   = x;
y_out_local   = y;
flag = 1;
break;
}
float xtemp;
xtemp = x2 - y2 + x_c;
y = 2 * x*y + y_c;
x = xtemp;
}
...
}
}