• February 25, 2021, 06:10:02 PM

Login with username, password and session length

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

0 Members and 1 Guest are viewing this topic.

Offline xenodreambuie

  • Fractal Friar
  • *
  • Posts: 111
Re: Multi-threading and Multiple Processors
« Reply #30 on: February 22, 2020, 11:05:17 PM »
LionHeart:
I use Delphi, not c++, so I can't give you direct help on threads. There are different ways to use threads, and how to interact with them depends on how they are set up. You can tell a thread to terminate, but only if you can be sure it hasn't already terminated itself.

When I use self-terminating threads, for line by line rendering, I still have the thread method run a loop. It checks if it has been terminated (in which case, break); it calls a method to get the next row, and it renders that row. If there are no more rows, it sends a message to the UI that it has finished, and terminates, else restarts the loop. In this case, the UI can be sure if each thread has finished or not, so it can terminate the thread sooner if it wants.

But there is overhead in creating threads. For interactive previews, it's usually more convenient to have threads that don't self-terminate. They run in a 'While not terminated' loop, and when not busy, they wait for a signal to start again. These threads have methods Run and Stop that you call. The Stop method just sets a private Stopped flag, which your iteration code should check periodically, and break if stopped. Stopping doesn't terminate the thread, it just tells it to go and wait for a Run signal. To terminate the thread, just set its terminated flag and call Run (assuming the iterate method isn't called if terminated is true). All communication from threads to the UI is either by them setting variables directly, or sending messages (not too many.) One advantage of using thread classes is that you can inherit and customize them as much as you like.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #31 on: February 23, 2020, 11:08:32 AM »
Thanks Adam,

I'll take a look. There are some interesting fractals in the Wikibooks article I may not have added to my software yet  :)

Hi xenodreambuie,

That's the main issue. I don't know how to find the current state of the thread. If I knew, then I could either terminate it or wait until it completed. I'm a real novice at multi-threading. Trying to read the Microsoft documentation has taken me in circles. The issue is I don't understand the meaning of the terms. Like when and how does one use a Mutex or a semaphore? I know what I want to do, but the silly program keeps having memory access failures. The only way I can prevent this is to put large pauses to give the threads time to end before moving on. 

I think I need to do some research on the theory before I do too much more programming.

Thanks for your suggestions.
Paul the LionHeart

Offline xenodreambuie

  • Fractal Friar
  • *
  • Posts: 111
Re: Multi-threading and Multiple Processors
« Reply #32 on: February 23, 2020, 11:28:08 AM »
Hi LionHeart.
The issue isn't exactly knowing how to find the current state of the thread. It is that you should not even try unless the thread is set up in a way that makes it safe. Threads have to be done correctly or else bad things happen. You can't learn how to do it right from documentation of the API; only from sources that explain how to use threads in various ways, correctly; or from well written source code that does the same thing you want to do. As there are many things that can go wrong, it helps to read something that explains all those things and how to avoid them.

Offline hobold

  • Fractal Fluff
  • *****
  • Posts: 396
Re: Multi-threading and Multiple Processors
« Reply #33 on: February 23, 2020, 01:52:30 PM »
Unfortunately I have to agree that multithreading is a topic that cannot be learned from API documentation alone. For relatively simple scenarios it's okay; say, one master thread plus a number of independent worker threads, without intermittent user action.

But if the workers have to communicate with each other, whole new classes of problems can crop up: race conditions, deadlocks, non-deterministic results.

And the next step up from that would be threads that are all on the same level of hierarchy, all capable of reacting to user input. It's not obvious how the application should be structured, or what the user interface should look like.

Long talk, little sense: start out simple. Try to find example code; preferably with explanations.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #34 on: February 24, 2020, 04:19:02 AM »
Hi xenodreambuie and hobold,

That explains the silly results I'm getting. I sort of manage it with long sleep() commands, but this still fails sometimes.

I have the source for Kalles Fraktaler and they do multi-threading well. Unfortunately, the source is complex and poorly documented. They use Mutex commands that I don't understand at all.

However, I hope I can make progress as the speed improvement is well worth the effort. One deep zoom went from 3 days without using threads to a couple of hours using 16 threads on a 4 core processor. It's almost as fast at deep zooms as Kalles. 

Thanks for your replies  :thumbs:

Offline xenodreambuie

  • Fractal Friar
  • *
  • Posts: 111
Re: Multi-threading and Multiple Processors
« Reply #35 on: February 25, 2020, 11:14:36 PM »
Thanks Duncan C, for the idea to use pooled threads on blocks instead of slices. It turns out not to be too complicated to do this with progressive refinement for a preview. I settled on 64x48 pixel blocks, as the initial resolution is 16 pixel squares. The resolution for each block is halved after processing it, and the queue cycles around until all blocks have been processed at 1 pixel. I use a spinlock rather than a critical section to protect the GetNextBlock function, as it's generally fast.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #36 on: February 26, 2020, 02:57:51 AM »
Hi xenodreambuie,

Do you have any simplified code to demonstrate this? It sounds like a great idea. Fractint used solid guessing and reduced the block sizes down to individual pixels. But it uses a lot of global variables and is difficult to understand. Any suggestions greatly appreciated. Thanks.

Offline xenodreambuie

  • Fractal Friar
  • *
  • Posts: 111
Re: Multi-threading and Multiple Processors
« Reply #37 on: February 26, 2020, 04:33:08 AM »
Hi LionHeart.
I am not using any accelerated method for pixel calculations (no guessing, boundary following, perturbation, etc) because they don't really fit into my generalized framework as far as I know. The pixel calculations need to show whatever the user has chosen, including lighting, and the only quality difference between the preview and full render is multisampling. So the preview just uses normal iteration methods, but at a lower resolution initially and filling in the extra pixels. The logic for that is easy: if resolution=1 then set pixel color, else call bitmapfiller(x,y,resolution,color).

The simple preview code just runs a repeat loop around the main iterations, decreasing resolution each time.
The block pooling preview code is similar, but in the repeat loop, it calls GetNextBlock, breaks if <0, else uses the block record for the rectangle coordinates and resolution.

First you need a thread pool, so the threads don't terminate when they finish each task.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #38 on: February 26, 2020, 05:37:32 AM »
Hi xenodreambuie,

I must be thick as a brick. I still don't get it. The preview blocks are easy. It's the allocation of blocks to each thread that I don't get. If we don't let the threads terminate, how do we know when to start the next block?

Is it possible to show a little pseudo-code?

Many thanks.

Offline claude

  • 3f
  • ******
  • Posts: 1781
    • mathr.co.uk
Re: Multi-threading and Multiple Processors
« Reply #39 on: February 26, 2020, 08:31:20 AM »
I have written a small Mandelbrot set renderer using C++ standard threading support.  I commented it heavily because some of the issues in concurrency are quite subtle.  Example output:
Code: [Select]
         , ....,---...+++..+*+****^*^***++,++-...--,            ? -1
         .,--....+++..++*+*^*^*^*//\//^*^*^++..++-.......         48
    .-.....,---...+^+*^**^*^^*///\\OO\\//^*^*+*+...--+,..       . 51
    ..,---...++++***^**^**////\\\\OOOO\\\//^^*^*++*--...   .    , 52
,.  ....--++..++^*^^*^^////\\\\\\OO!!!OO\\\\/^^^++....--,*..    - 55
   ,+--...+*+*^^*^^/////\\\\\OOOOO!!!!OOOOOO\//^*+++*--,..      + 58
 .....-+++***^^*///\\\\\\\\OOO!!!!!!!!!!!!OO\\/^**+,........    * 61
,-,--...++^*^^/\/\\OOOOOOOOO!!!!!!!!!!!!!!!!O\//***++++*--,.    ^ 67
....-++**^^///\\\\OOOO!!!!OO!!!!!!!!!!!!!!!!O\\/***+,.......    / 75
 .,,..+*//\\\O\OOOOO!!!!!!!!!!!!!!!!!!!!!!!O\\//***+++---,,     \ 98
 .,,..+*//\\\O\OOOOO!!!!!!!!!!!!!!!!!!!!!!!O\\//***+++---,,     O 2021
....-++**^^///\\\\OOOO!!!!OO!!!!!!!!!!!!!!!!O\\/***+,.......    ! 2048
,-,--...++^*^^/\/\\OOOOOOOOO!!!!!!!!!!!!!!!!O\//***++++*--,.
 .....-+++***^^*///\\\\\\\\OOO!!!!!!!!!!!!OO\\/^**+,........
   ,+--...+*+*^^*^^/////\\\\\OOOOO!!!!OOOOOO\//^*+++*--,.. 
,.  ....--++..++^*^^*^^////\\\\\\OO!!!OO\\\\/^^^++....--,*..
    ..,---...++++***^**^**////\\\\OOOO\\\//^^*^*++*--...   .
    .-.....,---...+^+*^**^*^^*///\\OO\\//^*^*+*+...--+,..   
         .,--....+++..++*+*^*^*^*//\//^*^*^++..++-.......   
         , ....,---...+++..+*+****^*^***++,++-...--,       
-1.9993075057864189 + 0.0000000000000000 i @ 3.725290e-09
Use numpad keys to navigate: 5 zooms into center, 7 top left, 2 middle bottom, etc.  0 zooms out.  + and - adjust the iteration count.
You need to press enter after each command character because of terminal input line buffering.  h gives some help text.

Source code:
https://code.mathr.co.uk/fractal-bits/blob/HEAD:/threaded-cplusplus/main.cc (latest version)
https://code.mathr.co.uk/fractal-bits/blob/33b8372e2bc603e9a94e46c8c91ca58eb5dfe0f7:/threaded-cplusplus/main.cc (current version at time of posting)

Offline xenodreambuie

  • Fractal Friar
  • *
  • Posts: 111
Re: Multi-threading and Multiple Processors
« Reply #40 on: February 26, 2020, 10:04:23 AM »
Hi LionHeart,
sorry, I haven't been detailed about the thread part because I'm using Delphi's thread class (and hence my descendants of it), not the API or any third party thread libraries, and haven't used any other method so I don't know how they compare. However, the answer to your question is easier. The preview method that the threads run has a repeat loop, that I mentioned, that does not exit until there are no more blocks to process. This loop is responsible for getting the next block. Doing it this way is much faster than exiting and re-entering a thread for each block. Here's some simplified pseudocode for that:

Code: [Select]
procedure CalcPreview(Thrd: TPreviewThread)
begin
  init stuff
  repeat
    blockno:= GetNextBlock;
    if blockno<0 then break;
    pb:= @blocks[blockno]; // pointer to block for convenience
    for each y, x in block, stepping by pb.pixsize, do
      iterate, plot, etc
      if Thrd.stopped then break
    end
    if Thrd.stopped then
      break
    else begin
      if pb.pixsize>1 then
        pb.pixsize:= pb.pixsize div 2
      else
        pblock.finished:= true;
      pblock.inuse:= false;
    end;
  until done;
  cleanup stuff
end

Since the threads are calling GetNextBlock, it has to be protected with a lock so only one thread can access it. Yes, the block stuff is kind of easy, but also easy to get some details wrong. Here's my actual code for it.
Code: [Select]
type
  PreBlockRec = record
    startx,endx,starty,endy,pixsize: integer;
    inuse,finished: boolean;
  end;

// BlockLock is a global longint
function GetNextBlock:integer;
var count: integer;
    found: boolean;
begin
  // spinlock; pointer version
  // if using the longint version, simplify to:  InterLockedCompareExchange(BlockLock, 1, 0) <> 0
  if integer(InterLockedCompareExchange(Pointer(BlockLock), Pointer(1), nil)) <> 0 then begin
    Sleep(0);
    while integer(InterLockedCompareExchange(Pointer(BlockLock), Pointer(1), nil)) <> 0 do
      Sleep(1);
  end;
  count:=0;
  found:= false;
  while not found do begin
    with blocks[curblock] do
      if not inuse and not finished then begin
        inuse:= true;
        found:= true;
        result:= curblock;
      end else
        if finished or inuse then Inc(count);
    inc(curblock);
    if curblock>=NumBlocks then curblock:=0;
    if not found and (count>=NumBlocks) then begin
      result:=-1;
      break;
    end;
  end;
  // release lock
  BlockLock:= 0;
end;

Before each preview start you need to init the pixsize, inuse and finished fields of each block.

That will let you process all the blocks however you have the threads set up, since they won't die while any blocks are waiting.
But as I've said, if your threads are terminating when they finish work, there are two problems. First, it's not safe to stop them early, because your UI can't be sure the thread still exists. Second, it's not very efficient to create new threads every time you want to restart the preview, if you want it interactive. And for interactive, you do want to be stopping the threads early so you can restart with new parameters.

There are two common answers to that. One, use a thread pool library, so when the threads finish they go back into the pool ready for new work. Two, use a thread class that you can subclass to do whatever you want. Then you create a dedicated thread pool for the preview, without any other stuff that general thread pools might have. It doesn't take much to make a thread do that: just a few fields and methods, plus a device for the thread to wait for signals so you can start and stop it without it terminating. The thread itself runs in a loop, but is not busy while waiting for the Run signal. Stopping the thread doesn't terminate it, it just tells it to stop work and wait for a signal. You can guarantee the thread still exists until you tell it to terminate. To give some idea how that works, here's my TPreViewThread class Execute method:

Code: [Select]
begin
  while not Terminated do begin
    fEvent.WaitFor(INFINITE);
    fEvent.ResetEvent;
    if not Terminated then begin
      Calculate(self); // nominal procedure to be assigned before calling the thread; self=this in c++
    end;
  end;
end;

The Calculate(self) method is what I assign the CalcPreview method to. I could just put it in there directly, except I actually use the class for some other things too (the Julia explorer and recalculating color/lighting run independently of the preview iterations, so I have three thread pools running concurrently.) You should be able to find the equivalent way of running threads in c++ somewhere, or else use a thread pool library.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #41 on: February 26, 2020, 12:20:44 PM »
Hi Claude,

Many thanks for writing this for me. You're a gem. It took me a while to compile it with my MS VC++ 2017. But I finally got there.

There's a lot for me to learn here. I'm not used to programming with std. I usually use standard windows API calls. I'll see if I can find my way through it.

Thanks for going to all that trouble.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #42 on: February 26, 2020, 12:23:50 PM »
Thanks xenodreambuie,

I should be able to work through it and replace your Delphi calls with C++ calls. The basic structure looks good. Let's see how I go implementing it.

There's so much to learn.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #43 on: March 01, 2020, 11:16:58 AM »
Dear Fractal Friends,

I have made a lot of progress thanks to you all. I have been able to improve speeds 10 fold even with only 4 cores. I am only using vertical slices at the moment to prove the concepts. Now it is time to do more suitable plotting methods.

I just want to say a big thank you to all who contributed. 

Offline hobold

  • Fractal Fluff
  • *****
  • Posts: 396
Re: Multi-threading and Multiple Processors
« Reply #44 on: March 01, 2020, 01:21:28 PM »
You are very welcome. :)


xx
Multi-Processor access

Started by admaxtv on Mandelbulb3d

4 Replies
526 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
253 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