H

ello again! Although I usually don’t have much time writing, I do occasionally see an interesting post or question regarding something I like. As I was browsing facebook, a question came to the Matlab forum I visit from time to time.It was not exactly a question to be honest, but a request for aid regarding computing of the Mandelbrot set, which is one of the famous fractal sets and in fact nothing more, that just evaluating some function in the complex plane over and over again until we decide for each point, whenever it lies in the set or it doesn’t. Basically, one defines a starting value for each point in the plane and then iterates a function of a form Z(n+1) =   Z(n)*Z(n) + C. This is the exact formula for computing the Julia set instead, but both the Mandelbrot and Julia sets are very similar in term of computing. Here, C defines a complex constant, which is added in each iteration to point lying somewhere in the complex plane. As it happens, its a numerical iteration-based solving of the set. One could create an infinite iteration loop, but then he would never see the result. It is therefore always a good idea to specify 2 things:

  • Maximum amount of iterations to be processed.
  • Iteration threshold – a function value which when crossed specifies that the point is  / is not a part of the set.

The iteration is usually stopped when any of the above is asserted. Either we have reached maximum amount of iterations or the function value has crossed the Threshold. The complex plane is usually defined from range -2 to 2 on both the real and imaginary axis. This is because values greater than 2 or -2 taken to the power of 2 always tend to go to infinity in this case and there is nothing special on them. To visualize the set, it is therefore necessary to evaluate the function in each point in the area of interest. In our basic case between -2 and 2 on real and -2 and 2 on the imaginary axis. Lets say we have a resolution of 1000 points in both real (x) and imaginary planes (y),this gives us a total of 1000*1000 = 1e6 points to be evaluated in order to visualize the set. Not precisely though as some points lying on the set edges require quite a large amount of iterations, lets say 100 for example. This gives us 1e6*100 = 1e8 complex multiplications and additions in order to visualize the set. This is quite a huge number even for modern multi-core computers.

Main CUDA Kernels

 

Now the problem is, that computing the set and displaying the set in Matlab is quite easy, however because of extra overhead of the Matlab language, one can easily run into a situation, where the evaluation of the set in this resolution will take tenths of minutes if not hours for large resolutions such as 2K or 4K. To illustrate the problem: there are 3 loops! The outermost one, which loop across iterations and 2 inner loops looping across the set’s X and Y – dimensions. writing the ultra inefficient will result in 3 for-loops, which will be sequentially executed on a single CPU core and not all available CPU cores. In fact using for-loops is highly not recommended for Matlab (Although sometimes just has to be used). An alternative solution is to use Matlab’s great vectorization technique as Matlab stand in fact for “Matrix Laboratory”. To do the vectorization, we just compute “all” values at once for a single iteration. To do so,we define the Initial value as a matrix and the constant as a matrix as well, when evaluating the function,we use the element-wise operations on matrices and vectors, which are very likely executed on several CPU cores are also very likely optimized with vector instructions such as SSE or AVX. By doing this, we can remove the 2 loops looping across the X and Y dimensions. The last iteration loop just has to stay as the results of the the next iteration is dependent on the previous result and although millions of points can be executed in parallel, their new values can only be computed as soon as their previous function values are known. This is overall known as data-dependency.

For those,who want to take a quick look at the performance and the demo, I have prepared a small demonstration video available on youtube. Unfortunately, the audio stream is the one I had in background while recording the screen and it has been captured as well. It has nothing to do with the demo. For those who wonder what those songs are: #1 Sudha feat. Zoe Johnston – Leche – Thomas Schwartz #2 Taylor Swift – This Love from album 1989.

 

 

 

Share This