• February 27, 2021, 11:32:36 PM

Login with username, password and session length

Author Topic:  Multi-threading and Multiple Processors  (Read 1230 times)

0 Members and 1 Guest are viewing this topic.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #15 on: February 20, 2020, 02:39:55 AM »
Hi kosalos,

I've played with your program. Very nice. It generates some lovely images. I use MPFR for arbitrary precision arithmetic. I have the source, but it is quite complicated.

You said previously:
Quote
I can make you a simple demo app if all that's required if you're interested.
Is that still available? I would love to give it a go.

Many thanks for your support.
Paul the LionHeart

Offline kosalos

  • Fractal Friar
  • *
  • Posts: 131
Re: Multi-threading and Multiple Processors
« Reply #16 on: February 20, 2020, 04:40:19 AM »
thanks for the kind words.
I haven't written a demo program, but what I envisioned was stripping away everything I could from my app, leaving just enough to demonstrate all that is required to make us of compute shaders in a Windows app.
It would still be 'complicated', because DirectX makes it a little tedious to get from A to Z, but as you saw in my app,
the result is very fast code (the FXC compiler is slow as heck, but it generates terrific shader code in assembly language).
I'll give it a go, and notify you of any progress.
Reminder: what I'll demo is just regular floating point math in a compute shader.
I have no experience with the  higher precision stuff you are interested in.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #17 on: February 20, 2020, 05:31:43 AM »
Hi kosalos,

Any help would be great. Take your time. I still have so much to learn.

I originally used the arbitrary precision code from Fractint. The only issue is that it used a lot of global variables making it hard to transfer to c++ code. But then I found MPFR. It is faster than the C version of the Fractint Library. But without perturbation, it soon gets slow as well. Perturbation allows reasonable speed at deep zooms, but when I look at Kalles Fraktaler, mine is a dinosaur  :embarrass: Hence the need for multi-threading and better pixel scanning. I tried to use Fractint type guessing in perturbation but it failed miserably. Maybe a GPU is the hidden ingredient.

Thanks for your efforts.
 

Offline kosalos

  • Fractal Friar
  • *
  • Posts: 131
Barebones Windows 3D Fractal
« Reply #18 on: February 20, 2020, 09:02:39 AM »
visit: https://github.com/Kosalos/BareBonesWindowsFractal
Stripped down 3D Fractal app displays the Apollonian for Windows 10, using a DirectX compute shader.

1. Switched to a barebones user interface, because everyone has their own favorite methods.
2. The shaders are stored in individual HLSL files, and the compiler calls FXC to generate corresponding .H files.
    I think this is much better than having the program compile all the shaders during run time.
    There are 3 shaders: the fractal code, the vertex shader and the fragment shader.
    The fractal is generated by a compute shader that stores the data to a 2D texture. 
    The texture is displayed by rendering to a textured quad via the vertex & fragment shaders.
3. Plan to add a Mandelbrot generator soon.
« Last Edit: February 20, 2020, 09:25:30 PM by kosalos »

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #19 on: February 20, 2020, 11:41:21 PM »
Wow thanks heaps, kosalos.

Do I still use the same MS VC++ compiler?

Unfortunately, when I try to download the zip file it says "Not found".  Am I doing something wrong?

Thanks for your help so far.

Offline kosalos

  • Fractal Friar
  • *
  • Posts: 131
Re: Multi-threading and Multiple Processors
« Reply #20 on: February 20, 2020, 11:47:53 PM »
I keep messing up my Github repositories when I use Visual Studio.
I updated the link in the post above to this new one:  https://github.com/Kosalos/BareBonesWindowsFractal
I used VS2019.

Just updated the app.
I now draws the Mandelbrot as well (very simplified rendition just to get you started).
« Last Edit: February 21, 2020, 01:20:02 AM by kosalos »

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #21 on: February 21, 2020, 07:13:08 AM »
Many thanks kosalos.

Yep I got it this time. This will keep me busy for a while.

I have made some progress on multi-threading:



I leave a small gap to help locate the thread being processed.

However, there are some glitches in slices 4 and 7.

Basically, I use the same reference points for all threads and simply mask out the pixels being calculated for each slot.

Code: [Select]
for (i = 0; i < RemainingPointCount; i++)
    {
    x = pointsRemaining[i].getX();
    y = pointsRemaining[i].getY();
    if (x < Colstart || x >= Colstop - 2)
continue;
    if (calculatePoint(x, y, magnifiedRadius, window_radius, bailout, glitchPoints, user_data, plot, potential, TZfilter, TrueCol) < 0)
return -1;

The beauty is that I have been able to get a huge improvement in speed, but it's not quite right  :fp:

Any ideas? Maybe I need to calculate separate references for each slice (a lot of work).

I'll keep working on it.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #22 on: February 21, 2020, 07:53:31 AM »
Hi kosalos,

I got your little program working. What a beauty.  ;) I'm not sure I understand how it works as yet, but it sure is a skeleton I can build on. I love the Apollonian implementation.  All I had to do was to change toolset from V142 to v141 to match my MS VC++ 2017.

Thanks heaps for your trouble.

Offline kosalos

  • Fractal Friar
  • *
  • Posts: 131
Re: Multi-threading and Multiple Processors
« Reply #23 on: February 21, 2020, 09:35:55 AM »
Can you post some pseudo code that demonstrates how the Perp. algorithm works?
I understand you pick certain pixels to be 'reference points', and you iterate them many times using high precision variables, but what is the relationship of those points to all the 'delta points', and how far in distance does that effect broadcast? Are delta points affected by multiple reference points? Is high precision math a requirement for the reference points? How exactly is the value determined by the reference point(s) used by the delta points?

thanks

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #24 on: February 21, 2020, 11:56:03 AM »
Hi kosalos,

Take a look at the discussion I had last year. The members here were great at helping me work out how to do it.  There are some useful links in the initial question that shows some simple code. One needs to use arbitrary precision arithmetic to do the deeper zooming. I use MPFR. The link is also given in the discussion.

https://fractalforums.org/programming/11/perturbation-code-for-cubic-and-higher-order-polynomials/2783

It took me a while to sort it out, but I have made lots of progress. Let me know if you need more info.


Offline Duncan C

  • Fractal Friend
  • **
  • Posts: 14
Re: Multi-threading and Multiple Processors
« Reply #25 on: February 22, 2020, 02:12:39 AM »
I wrote my fractal program, FractalWorks (for Mac OS) in Objective-C. That's a superset of C with OOO extensions.

The multithreading part was using POSIX threads.

I don't have any code for your OS, or your specific language, but the approach will be similar regardless of those things.

I create a number of threads that's the same as the number of logical cores (double the number of physical cores, due to hyperthreading on Intel processors.)

I then slice up my fractal into at least 2*threads number of rectangles, and create a pool of Job objects that contain descriptions of those rectangles for rendering.

I set up a thread-safe Job queue that provides a new job to the rendering threads on demand, and a thread-safe "number of pending jobs" counter that tracks the number of remaining jobs. Each thread asks the job queue for a job to do. It then renders that job from beginning to end, and then tells the job counter to decrement the number of pending jobs, before asking the job queue for another job to do. Once the number of pending jobs drops to zero, the plot is complete.

Google Windows thread-safe queues and thread-safe counters for more information. The specific implementation will be different from UNIX to Windows, but the concepts will be the same-

Since there are at least twice as many jobs to do as threads to do them, threads that are assigned fast-completing tasks are able to ask for another task to do once they complete their work.

On the main thread, I monitor the number of pending jobs, and when it reaches zero, I render the fractal to the screen.

My program renders Mandelbrot and Julia set fractals, and uses boundary following to avoid rendering the interiors of contiguous areas of Mandelbrot points (and other contiguous regions with the same iteration count if it's not calculating fractional iterations or distance esimtates). Boundary following is the fastest when the area being rendered has a small ratio of perimeter to internal area, so cutting the plot into too many narrow slices ends up being counter-productive. I slice my plot into horizontal slices, which isn't ideal. I should really divide it into smaller and smaller squares, since long skinny rectangles have more perimeter than squares with the same area, but it nevertheless works well.

I recently added a section to the Wikipedia article on the Mandelbrot set on multi-threading and other optimizations. You can read it here. (It starts out discussing border tracing, and then there's a section on more general multi-threading.)

(Note that border tracing makes a dramatically larger difference than multi-threading.)

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #26 on: February 22, 2020, 04:10:06 AM »
Many thanks Duncan C.

I like your philosophy. So far I simply allocate each thread to a slice, but the slower ones hold up the job. I get a substantial improvement in speed, but your approach sounds even better. The main issue I've found in monitoring the threads for completion. The bigger issue is user interrupt. If one thread is stopped, I have to flag all the other threads to stop. I think your suggestion of thread-safe queues will help.

Your Wikipedia reference is brilliant. Many ideas for me to follow there. I am using periodicity checking for straight calculations, but I will try to implement it in perturbation as well. Let's see how we go.

Offline xenodreambuie

  • Fractal Friar
  • *
  • Posts: 111
Re: Multi-threading and Multiple Processors
« Reply #27 on: February 22, 2020, 08:18:50 AM »
What works best will depend to some extent on the details of the rendering methods.
For Mandelbrot/Julia previews and exploring, I use a vertical slice per thread. Breaking it into blocks for pooling makes sense; however, with progressive refinement it would be more complicated and I haven't thought about it yet. For interactive previewing the less messaging between main and worker threads the better.
For final anti-aliased renders, I allocate each row to a thread when it's ready.
For IFS and other random access calculations, threads have full coverage and write to buffers with or without locking depending on the context and consequences.

Note that not all Intel processors have hyperthreading, so you should get that information from the API rather than assuming it.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #28 on: February 22, 2020, 10:31:14 AM »
Hi xenodreambuie,

Thanks for your reply.

I use a number of modes in "normal" fractal generation: solid guessing, boundary trace, teserral, spiral etc and have no problem. However, with perturbation, it is not so easy because one needs to compare to the reference.

So far, vertical slices work well. I'm still experimenting. I have 2 issues, however:

1. How to find the best reference for perturbation. Sometimes I get glitches, even when I use Pauldebrot's method. http://www.fractalforums.com/announcements-and-news/pertubation-theory-glitches-improvement
2. How to process user intervention and shut down the threads so a new set of threads can be created with the new zoom information etc.

I have been using:
Code: [Select]
for (i = 0; i < NumThreads; i++)
    {
    IsOkay = GetExitCodeThread(hThread[i], &ExitCode);
    if (IsOkay)
        ExitThread(ExitCode);
    else
        ErrorCode = GetLastError();
    }

...and the program hangs immediately after the first ExitThread(ExitCode). I'm not sure how to end threads cleanly or to tell them it's time to stop. If I let them time out, all is fine. But deep inside a fractal with high iteration count, one gets impatient  :yes:

Multi-threading is a steep learning curve.

Offline Adam Majewski

  • Fractal Frogurt
  • ******
  • Posts: 452
Re: Multi-threading and Multiple Processors
« Reply #29 on: February 22, 2020, 01:18:35 PM »
I recently added a section to the Wikipedia article on the Mandelbrot set on multi-threading and other optimizations. You can read it here. (It starts out discussing border tracing, and then there's a section on more general multi-threading.)

What about wikibooks : https://en.wikibooks.org/wiki/Wikibooks:What_is_Wikibooks
because : https://en.wikipedia.org/wiki/Wikipedia:What_Wikipedia_is_not#Wikipedia_is_not_a_manual,_guidebook,_textbook,_or_scientific_journal

You can put it :  https://en.wikibooks.org/wiki/Fractals

HTH





xx
Multi-Processor access

Started by admaxtv on Mandelbulb3d

4 Replies
527 Views
Last post April 26, 2018, 11:20:51 AM
by hobold
xx
Music Video with multiple Mandelbulber renders

Started by Nepenthes Sloth on Fractal movie gallery

2 Replies
256 Views
Last post February 10, 2021, 11:18:45 PM
by Tas_mania
xx
Activation email didnt receive multiple times in a row?

Started by realflow100 on Forum Help And Support

3 Replies
267 Views
Last post February 11, 2018, 09:48:12 AM
by 3DickUlus
clip
FragM multiple object transparency with user defined depth

Started by kosalos on Code Snippets (fragments)

2 Replies
177 Views
Last post October 27, 2019, 07:56:26 AM
by SCORPION