Buddhabrot on GPU

[cbuchner1]

I have started looking into the Metropolis-Hastings algorithm to speed up zooming.

Here is a first result of a moderately deep zoom. Rendered in 1280 x 800 pixels, centered around the
coordinates given below. It took about 30 minutes on a laptop graphic cards with 32 CUDA cores.
It would take about 2 minutes on a GTX 460, I guess. If I could only get this card to work in my
designated PC...

Brightness mapping was done using the formula powf(L, 0.5). I still had to use some contrast adjustment in
a paint program.

Code:

float zx = -0.0423594f, zy = -0.985749f, zoom = 120.f;

// the formula for computing the real and imaginary bounds is like this, ih/iw is the height to width ratio.
float zrmin = zx - 1.0f / zoom, zrmax = zx + 1.0f / zoom;
float zimin = zy - 1.0f / zoom * ih/iw, zimax = zy + 1.0f / zoom * ih/iw;

About the metropolis-hastings:

The "reference code" on Alexander Boswell's web site was a little confusing, he used way more exp and
log expressions in his probability model than mathematically needed. In the end I made some deviating
design decisions: A normal distribution for the small mutations instead of his exponential distribution. And
I choose one of 3 mutations in each CUDA thread, according to a probability model that is much different
from Boswell's (I kept his idea that "good" mutations are more likely to win).

I want to try something else for adding color now. Maybe different color spaces (not the usual R,G,B).
How about HSV for a change? We already have a V channel (intensity). Now we need to find some
coordinates for hue and saturation.

Hmm, maybe I could integrate the nVidia denoise SDK sample into this code. I still see a lot of image grain that a good filter could get rid of.

[ker2x]

I have started looking into the Metropolis-Hastings algorithm to speed up zooming.

I want to try something else for adding color now. Maybe different color spaces (not the usual R,G,B).
How about HSV for a change? We already have a V channel (intensity). Now we need to find some
coordinates for hue and saturation.

What about CMYB with 4 iteration level ? that's something on my todo list.
(that will require conversion to RGB to display on the screen)

[ker2x]

The metropolis-hastings look like a good idea, but :
- i don't understand it
- i don't know how to implement it efficiently (mostly because i don't understand it  )
- i'm not convinced

I haven't seen a buddhabrot using this algorithm that still have a nice "background". It seems to select only the orbit that draw mandelbrot shapes and focus on the center of the screen.
Addtionally, on the gpu, the real bottleneck is happening when the computed point is inside the screen (require one read+write on the global memory per color), computing points that won't be on screen is incredibely fast (unless you have extreme high iteration, of course. Then it could be a major waste of gpu cycle)

I may still try to implement it, just to be sure, if i can put my hand on code i can understand. But it's really not a priority (fixing bugs, and improve coloring are my priorities).

I'have seen enough mandelbrot shape in my life, i'm not chasing after them in the buddhabrot

[cbuchner1]

I think Metropolis-Hastings is actually a misnomer. What it really is, is a "nonuniform random sampling" using tiny mutations of previous samples. The better mutation has a higher rate of suvival, a genetic algorithm really. I was able to hack it in a day.

Basically if you know that your previous sample has hit the screen at least once, you'll make a tiny mutation to the starting location (in the order of 1/100th to 1/10th of the zoom level). Find a metric that honors the number of times the screen is hit (and total iteration length as well) and determine randomly (based on the metric as weights) whether or not to the new sample will replace the previous one. Occasionally draw an entirely new sample to allow the system to find entirely new orbits.

There should be a bias towards longer iterations, and the more often the screen is hit, the better. This is basically why this algorithm may produce images that are biased towards longer orbits (and may indeed look different from uniformly sampled images).

[lycium]

Having implemented it in a 3D rendering engine, I should say that M-H sampling is neither a misnomer (?) nor a simple trick where you just add little offsets to random numbers...

Nevertheless, you've done some interesting work here Chris

[cbuchner1]

Let's just say my implementation is no longer Metropolis Hastings because I deviate from the original Markov model. The problem with the original M-H (as described in the Wikipedia article) creates a whole lot of branch divergence which is bad for performance on this particular hardware architecture. The GPU works best when all threads of its scheduling unit perform the same work at the same time. When a few threads branch off performance suffers because the hardware serializes the different branches (one branch after the other instead of executing all in parallel).

In M-H there is a significant chance that the new (mutated) sample won't be accepted. Going back and making another mutation in this case causes mentioned branch divergence. Not attempting another mutation forces the affected thread idle (we cannot render any orbits for a rejected mutations) which is also very wasteful with computing resources. So whatever you do it's bad for performance because only some of the CUDA cores will do useful work.

So I choose to test three mutated samples in each thread, weighing each sample's survival probability using a metric similar (but not identical to) the original M-H algorithm. There is also a certain probability to stick with the previous sample and to not draw the orbit, but this probability has been much reduced. I guess my current approach breaks the underlying maths for markov chains. I would have to study some statistics text books to fix this, my higher maths skills have become rusty

[kram1032]

the RGB colourspace is pretty natural...
Well, you could do a direct frequency to frequency color space, so to say...

Just like sound:

Where your f is basically the iteration count or maybe the period of that specific point.
Then use that (mapped linearly, logarithmically or what ever) to actual frequencies of light, perceivable by us and then finally convert those via La*b* to RGB.

Not sure if that'd work like this... Maybe it's way more complicated^^
But if it does, you should get some nice colours
Shifting or stretching the shape causes different frequencies to be visible

[hobold]

Conditional execution is a weak point of SIMD machines (just rephrasing your statement about GPUs in the terminology of the "multimedia" instruction set extensions of CPUs). However, I think it is wasted effort to try and achieve 100% utilization across the whole vector width. Scalar CPUs do not predict conditional branches with 100% accuracy either.

In other words, a bit of "warp divergence" is not necessarily a killer criterion for a particular algorithm. As long as you can maintain good average utilization, you will beat scalar processors handily. Re-arranging computation across vector lanes is rather expensive, so you might well be better off not doing it after every iteration, but only once after the current utilization drops below some threshold.

This used to be a bigger problem with SSE or AltiVec, where vectors are four lanes wide (in the case of 32 bit floats). One inactive lane already costs 25% of potential performance. But GPU vectors are 32 lanes wide, so you don't lose as much potential when one lane goes inactive.

[cbuchner1]

Here is a new binary + source distribution. Binary is found in "Release" folder. You may need to place the DLLs found in separate attachments in the same folder.

Also contains CUDA source code. Tested with CUDA SDK 2.3 Just unzip the folder into the SDK's C/src directory and build.

I am allowing for interactive zooming and exploration now.
Left mouse button and dragging selects an area.
Hold Ctrl to zoom around the point where you clicked first.
Hold Shift to remove the aspect ratio lock during zooming.

The program shows the other available keystrokes on the console, mainly for controlling brightness/exposure.

The window can now be resized. The program also accepts --width=x and --height=y parameters on the command line
to set an initial window size. It may be easier to just hit the "maximize" window button though

Christian

[ker2x]

Code:

The following error has occurred during XML parsing:

File: D:\projets\Buddhabrot-cuda\Buddhabrot\Buddhabrot_vc90.vcproj
Line: 22
Column: 4
Error Message:
Custom build rules file 'd:\projets\common\Cuda.rules' was not found or failed to load.
The file 'D:\projets\Buddhabrot-cuda\Buddhabrot\Buddhabrot_vc90.vcproj' has failed to load.

[cbuchner1]

Custom build rules file 'd:\projets\common\Cuda.rules' was not found or failed to load.

Attaching my cuda.rules file. It is part of the CUDA 2.3 SDK, which you can get from the nVidia site.

http://developer.nvidia.com/object/cuda_2_3_downloads.html

Without the SDK, I guess my code won't compile. The Buddhabrot folder must go into the SDK's
C\src folder. Make sure you can compile and run the other graphical SDK samples first, before
trying the Buddhabrot. My code was based on the "Sobel" SDK sample code.

One more thing. My Analysiskernel requires sm_11 architecture (Compute capability 1.1) because
it makes use of global atomics. On your GTX 8800 you may want to comment out the Analysiskernel
call and change the project options to use sm_10 for compilation. This kernel only reports statistics
on how many threads actually plot useful orbits but it won't run on a GTX 8800 card with Compute
capability 1.0

[cbuchner1]

What about CMYB with 4 iteration level ? that's something on my todo list.
(that will require conversion to RGB to display on the screen)

CMYK you mean? That's what Google suggests instead after searching for
CMYB.

I think the black (or Key) color is only used to save ink on the cyan, magenta
and yellow and also to allow for printing high detail text - so it is really useful
only for printing.

So maybe a CMY color space (without the black) would suffice for experiments
with the Buddhabrot.

[kram1032]

I did an error above that made the colour stuff to not make much sense...
What I meant was:
directly map either the iteration count or the periodicy to the frequency of the light spectrum and then convert that to RGB, possibly based on receptor messures of the human eye.

Just tweak the mapping to highlight different parts.

Would that work?

[cbuchner1]

directly map either the iteration count or the periodicy to the frequency of the light spectrum and then convert that to RGB, possibly based on receptor messures of the human eye.

Iteration count mapped to a spectral wavelength would mean I would only get the "pure" colors found in a rainbow. Still sounds nice. Maybe it will give the look of a soap bubble.

[cbuchner1]

CUDA Buddhabrot has been updated to allow interactive zooming. I've just updated this once more
this night to allow for resizing of the window.

the EXE file, source code and first part of the DLLs are found here: http://www.fractalforums.com/index.php?topic=3614.msg19874#msg19874

Find the second DLL archive for updated CUDA Buddhabrot.zip (binary EXE) attached. Use them if
the EXE can't find these DLLs in your system. Just place them in the same folder as the EXE itself.

*Really* enjoy this on an nVidia GTX 260 or better. You definitely need a CUDA capable graphics
cards and not too ancient drivers. The more shaders (CUDA cores) the better.

The next thing I'm shooting for will be color. But even in black & white it's already fun exploring.
I've placed 3 sample pictures in the gallery. All taken as screen shots and cropped in MS Paint