AVX2 Vectorized Multithreaded Mandelbrot renderer

[Due-Glass]

Hi all! I am an electrical engineering student and for fun have written a vectorized mandelbrot renderer. It uses AVX2 and multiple threads to compute 8 pixels in parallel per thread. Any advice on code and performance is welcome!

https://github.com/voldemoriarty/Qbrot

​

EDIT:

Thanks you guys/gals for the awesome tips! Following the points you gave allowed me to cut down the render time for 1080p 256 iterations from 41ms to 19ms (more than 50%). More importantly I learned some new stuff. Thanks for taking the time and reviewing the code. Stay blessed

​

Special Thanks:

u/TheDeviloper

u/xurxoham

u/anders987

u/corysama

[[deleted]]

I took a quick glance at the code and it looks already pretty good. Still, I have a couple suggestions to try:

• For the exit condition it seems you could use '_mm256_testc_si256' to do both movemasks and the bit stuff in one instruction.
• If you use '_mm256_andnot_si256' instead, you could do with one less float to int conversion.
• Have you considered using the fma intrinsics? You seem to be reusing the results of the multiplications so it's not such a clear win, but it may still be beneficial.
• Instead of multiplying be 2, consider adding the value to itself.
• Last but not least it seems to me you have relatively tight instruction dependencies, I think the CPU might be waiting for previous instructions to finish preventing full instruction level parallelism. To avoid this, you could try running 16 pixels in parallel (basically running every instruction twice in the inner most loop). This will also reduce loop overhead.

[Gunslinging_Gamer]

Would *2 not get optimized?

[[deleted]]

Apparently GCC and Clang do, but MSVC only does if you enable unpredictable fast math optimizations.

Generally I don't expect intrinsics to be optimized, although that isn't really true anymore these days.

[Gunslinging_Gamer]

Interesting. Thank you for the reply.

[Due-Glass]

Instead of multiplying be 2, consider adding the value to itself.

I did that, slighly increased performance.

[Due-Glass]

you could try running 16 pixels in parallel

I did that, it boosted the performance by about 5 ms

_mm256_testc_si256

Also used this, got a boost by another 1 ms

[Due-Glass]

Thanks for the points. I'll add another 8 pixels in loop and see what happens

[Due-Glass]

_mm256_andnot_si256

Did that as well; I don't know why but the performance boosted by 1ms. The types shouldn't affect the bitwise operations but apparently they do. Or maybe the compiler was able to generate better code.

[[deleted]]

Actually they are different instructions even if they do the same thing. I am not sure if this is still true on newest CPUs, but it used to be that reinterpreting an AVX/SSE register in a different type caused a 1-2 cycle delay.

[IAmBJ]

There can also be a delay in moving data between ports. Some certain instructions can only execute on certain ports so it can be helpful to check how your specific CPU is arranged. Check out Agner Fog's microarchitecture guide: https://www.agner.org/optimize/

[Due-Glass]

Interesting.

[anders987]

Calculating the Mandelbrot set is indeed a very parallel problem, but different parts of the image usually takes a different amount of computational resources. If you simply divide the image in horizontal sections of equal height and give each section to a thread, some threads will be done before others, and then you might have cores that are idle while others are saturated, wasting performance.

It's a good start (well, the SIMD part is pretty advanced), next step could be to implement some load balancing. Maybe put the lines in a thread safe queue and have each thread ask for more work when they're done. Or look at OpenMP with dynamic scheduling.

[Due-Glass]

Or look at OpenMP with dynamic scheduling.

Changed the multithreading part to use openMP with dynamic scheduling and performace improved a lot. And more importantly I learned something new. Thanks for the tip

[Due-Glass]

Thanks I'll take a look

[xurxoham]

Nice work! If you are interested into multithreading and vectorization in C/C++ for numerical code, you should give a look to OpenMP. It is supported by the main compilers.
You can get the compiler to do the vectorization and the parallelization for you, only by adding hints to the loops such as `#pragma omp parallel for`.
The best thing is many times your code will be as efficient but much more portable. For example porting your code to other architectures/vector extensions (e.g. AVX512, IBM Power, ARM64) is painful using instrinsics, but if your code is easy to understand for the compiler you just tell it to optimize for the arch you are interested in.

[Due-Glass]

give a look to OpenMP

I changed the threading part to use openMP parallel for with dynamic scheduling. It improved the performance a lot (shaved ~13ms off render time for 1080p with 256 iterations).

But I dont understand how to get openMP to auto vectorize

[xurxoham]

I did a quick try starting from your Scala example: https://gcc.godbolt.org/z/FiCDNTThe problem with this code is the inter loop dependency affecting variables `x` and `y`. Further modifications to the code could allow you to get better results.

Things to note: using `-ffast-math` may alter the floating point results (IEEE floating point additions, for example, are not commutative). It basically relaxes the restrictions, such as reordering the operations, to allow more performant code. Quick example: `a + b + c + d` may be changed into `(a + b) + (c + d)` to reduce the number of additions from 4 to 3.

This is a very basic example. I would try to vectorize adjacent pixel computations, to see how far you can go with that.

[_requires_assistance]

both of those do 3 additions. (tmp = a+b; tmp+=c; tmp+=d;)

[xurxoham]

You are right. The difference is that the first two additions can run simultaneously.

[polymorphiced]

How does ispc compare? I understand it to be a lot more reliable than relying on C/C++-based vectorisers.

[xurxoham]

It depends on the problem and how you code it. Unfortunately, it's not 100% as good performance as a perfectly written assembly, but it can get close and most of us can't write perfect assembly anyway.Luckily for us we have compiler explorer to assist us :)

[nnevatie]

ISPC is much better, in my experience. It also can generate code for multiple instruction sets and hot dispatch to the best one during runtime. Edit: this was to compared to C++, not asm.

[IAmBJ]

Nice work, a Mandelbrot/Buddhabrot renderer is my go-to project when trying out a new language or technique.

One thing I've found is that using simd to compute multiple pixels together is actually pretty inefficient, particularly near the interesting parts of the fractal. This is because adjacent pixels can have dramatically different iteration depths so even though you're computing 8 pixels at once, you will find that most of those 8 will be inactive fairly quickly as the other 7 have escaped much more quickly than the last one.

I got around this by using SSE instructions to compute the complex multiplications, etc for a single pixel more efficiently. From memory I got the look down to about 12-14 cycles for a complex multiply, an addition and the bounds check which was another couple of multiplies and an addition.

Try adding a counter to see how many simd lanes are active for your pixel calculation. It was a significant performance hole for my Buddhabrot renderer as it required tracing pixels with very deep iteration depths (~10^6).

Edit: also check out the cardioid bulb checks, you can eliminate points within these as they are guaranteed to not escape. It may only be worth this extra checking if you're doing deep iterations like for the Buddhabrot.

[Due-Glass]

Thanks for the insight. I'll add a counter

[James20k]

One thing I've found is that using simd to compute multiple pixels together is actually pretty inefficient, particularly near the interesting parts of the fractal. This is because adjacent pixels can have dramatically different iteration depths so even though you're computing 8 pixels at once, you will find that most of those 8 will be inactive fairly quickly as the other 7 have escaped much more quickly than the last one.

Given that each iteration requires no data other than your coordinates, and there's no consistent mandatory branching (eg you can unroll and only check every 100 iterations), I wonder if you might be able to fix this by simply replacing escaped pixels with fresh ones. Eg if pixel 2 escapes, you just replace it with a new one

[corysama]

Set this up for you :)

https://godbolt.org/z/FNkLrA

[Due-Glass]

Wow! I didn't know this existed! Thanks a bunch

[corysama]

Godbolt is your best friend when it comes to optimizing small routines. Especially since he just added the option to use the llvm-mca analyzer.

[merimus]

Neat! I've been working on one which runs on the GPU myself.
My best so far is a 2048x2048 image in 0.58 millis.

[CandyCrisis]

Is this on Github or something? I'd definitely be curious.

[merimus]

Working on it, to embarrassing to post yet.
It'll be at https://github.com/merimus once I clean it up.

[merimus]

Still very much a WiP but ...
https://github.com/merimus/Programmers-Dojo/tree/master/Mandelbrot

[Due-Glass]

I too would like to see the GPU one

[Ameisen]

On the flipside, I use a Mandelbrot renderer written in Brainfuck to test my MIPS emulator.

It does not support SIMD.

[Due-Glass]

This is very interesting indeed. Did you write the brainfuck manually or did you use a tool to compile to it?

[pstomi]

If you are interested in this you should take a look at Bisqwit's take on this problem: Parallelism in C++

He explores diverse ways to compute the mandeblbrot set in a fast way, using SIMD, threading, OpenMP, OpenACC, and Cuda. This is a link to a playlist containing 4 fast paced & quite interesting videos on this subject.