• March 01, 2021, 12:09:35 PM

Login with username, password and session length

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

0 Members and 1 Guest are viewing this topic.

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Multi-threading and Multiple Processors
« on: February 17, 2020, 12:20:25 PM »
I have done a lot to improve the speed of my fractal program but still have one big drawback. Most CPUs have multiple cores and it would be good to utilise all the processing power, especially for deep zooms.

I tried to make sense of the source code of Kalles Fraktaler, but the code is not commented and I find it hard to see what's happening. I see that the main calls are CreateMutex() and CreateThread(). However, I struggle to see how the image is segmented for each thread and how the control is passed back to the calling routines.

I have tried to simply segment the image into vertical slices but am not sure how the main routine is aware that all the threads have completed their task.

Does anyone have a simple bit of c or c++ source code for Windows to help make sense of multi-threading? Or is there some explanation of program control of the threads etc? Any help greatly appreciated.

Many thanks.

Linkback: https://fractalforums.org/programming/11/multi-threading-and-multiple-processors/3323/
Paul the LionHeart

Offline superheal

  • Strange Attractor
  • ******
  • Posts: 94
Re: Multi-threading and Multiple Processors
« Reply #1 on: February 17, 2020, 03:28:25 PM »
I don't have any c or c++ code available, since I wrote my app in java, but I see two approaches.

You either spawn the threads on the main thread, and then use "join" (most implementations will have it), or you ignore the main thread completely (which usually handles the gui and painting) and add some synchronization mechanism on the threads, for instance if you spawn 4 threads, then increase a a counter with a mutex, and the last thread to arrive should trigger the repaint.
I am using the second one.

Offline hobold

  • Fractal Fluff
  • *****
  • Posts: 397
Re: Multi-threading and Multiple Processors
« Reply #2 on: February 17, 2020, 03:43:13 PM »
Code: [Select]
/*
  simplistic multithreading example with C++11 standard libraries
  ===============================================================

  The basic idea here is to spread one loop across the available threads, by
  using a std::atomic<int> as the loop variable, incremented by the fetch_add
  member function.

  Atomic variables, when accessed with the proper member functions, guarantee
  that regardless of thread timing variations, all values from zero to max will
  be observed exactly once by some thread. So there will be no skips and no
  duplicates. Furthermore, atomic variables tend to have less overhead than
  semaphores, mutexes, and other forms of more explicit synchronization.

  ATTENTION: some care has to be taken which loop should be distributed among
  processor cores in this manner. You want the work packages for each thread
  to be between maybe a million clock cycles to maybe a hundred million clock
  cycles. Much smaller work packages will exhibit notable overhead for thread
  management. Much bigger work packages won't balance the load between cores
  as well.

  So you probably don't want to split the innermost loop, or the outermost
  loop of a big program. I usually split computation of a single animation
  frame. Then the rest of the program can remain sequential, frame by frame, by
  design. And I get natural restart points, with each frame saved to disk, to
  protect against a power outage (or some other catastrophe).

  Distributing an image row by row isn't ideal. But it's good enough in many
  cases.
*/

#include <thread>
#include <atomic>


// to coordinate worker threads
std::atomic<int> curRow(0);
int numThreads = 1;  // to be properly initialized later

// frame buffer storage
float* ImgBuf = NULL;  // to be initialized later


// compute one row of ImgBuf
void renderRow(const Vista2D& vista) {
  int y = curRow.fetch_add(1);  // number of the next row that needs to be done

  while (y < ImgHeight) {

    // ... render row y ...
   
    y = curRow.fetch_add(1);
  }
  return;
}


// parallelize with std::thread
void render(const Vista2D& vista) {
  curRow.store(0);  // reset our "work queue"

  std::vector < std::thread > threads;
 
  // launch render threads
  for (int i = numThreads; i > 0; --i) {
    threads.push_back(std::thread(renderRow, vista));
  }
 
  // wait for render threads
  for(auto &thread : threads) {
    thread.join();
  }
 
  return;
}



// main renders and writes an image to file
int main(void) {
 
  // set up number of worker threads
  numThreads = std::thread::hardware_concurrency();
  fprintf(stderr, "will use %d threads\n", numThreads);

  // set up image buffer
  ImgBuf = new float[ImgWidth*ImgHeight];
  if (ImgBuf == NULL) {
    fprintf(stderr, "error: out of memory for ImgBuf\n");
    return -1;
  }
 
  Vista2D theVista;
  theVista.init(-0.75, 0.0,   // center
0.0,          // angle, clockwise
0.0,          // zoom
1000,         // max iterations
0.0, 0.0,     // orbit trap location
0.0,          // hue shift
1.0);         // aspect ratio

  theVista.magnify(0.6);
 
  render(theVista);

  // ... write image ...
 
  delete[] ImgBuf;
 
  return 0;
}
« Last Edit: February 17, 2020, 06:19:15 PM by hobold »

Offline claude

  • 3f
  • ******
  • Posts: 1784
    • mathr.co.uk
Re: Multi-threading and Multiple Processors
« Reply #3 on: February 17, 2020, 04:14:04 PM »
KF does it like Hobold's code, with one worker thread per core, and an atomic counter that is incremented per pixel (which may be slow at "easy" locations), except that KF uses Windows API instead of standard C++ features (I guess they were not well-supported by compilers when the project was started).  But to avoid the main (GUI) thread blocking during rendering, it spawns a background thread to fork/join all the worker threads.  I'm not entirely sure how the main thread synchronizes with this background thread to signal "abandon work, new frame requested" (from main to background) or "work is all done" (from background to main).  Especially the second case (background to main) is the most spaghetti part of KF's code that I've discovered so far...

Offline Adam Majewski

  • Fractal Frogurt
  • ******
  • Posts: 452
Re: Multi-threading and Multiple Processors
« Reply #4 on: February 17, 2020, 05:30:53 PM »

Offline 3DickUlus

  • Administrator
  • *******
  • Posts: 2053
    • Digilantism
Re: Multi-threading and Multiple Processors
« Reply #5 on: February 17, 2020, 10:15:47 PM »
Quote
the most spaghetti part
but the meatball and mushroom sauce is delicious  :P

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #6 on: February 18, 2020, 12:11:35 AM »
Wow, so many replies. Thanks everyone.

Hi Superheal, I will spawn all the treads from the main program that does a lot without multitasking. I need to explore the "join" function. I'm sure Microsoft VC++ would have something like that. Thanks.

Hi Hobold, Thanks for the program. I will use it to help me structure my code, but I prefer to stay with Windows APIs such as CreateThread(). I've had a few problems using standard C++ libraries I don't fully understand. However, your code is very helpful. Thanks.

Hi Claude, great to chat with you again :)
Quote
But to avoid the main (GUI) thread blocking during rendering, it spawns a background thread to fork/join all the worker threads.  I'm not entirely sure how the main thread synchronizes with this background thread to signal "abandon work, new frame requested" (from main to background) or "work is all done" (from background to main).
Now you hit on one of my main issues. There is so much to learn here. This is as daunting as the early discussions we had on perturbation  ;) But with your help and many others, I got there.

Hi Adam Majewski, This looks complicated. I will try to get more understanding of what I'm doing before I launch into new libraries. However, this would make a great upgrade once I get something working. Thanks for your reply.

Hi 3DickUlus,
Quote
but the meatball and mushroom sauce is delicious
my mouth is watering now. Gee so much to learn. The idea of using the GPU sounds attractive.

Thanks everyone. I am a bit overwhelmed at the moment. I think I need to build some stub programs and play and learn how it all works. I might come back with more specific questions once I progress a little further in my knowledge.



Offline hobold

  • Fractal Fluff
  • *****
  • Posts: 397
Re: Multi-threading and Multiple Processors
« Reply #7 on: February 18, 2020, 12:21:05 AM »
I will not try to talk you out of using Windows APIs. Using whatever is native on your OS is the path of least resistance. Getting things up and running is a lot more important than getting things perfect. :)

(I am approaching my 6th decade, and have transitioned between too many different APIs. I now prefer standardized portability whenever possible.)

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #8 on: February 18, 2020, 07:17:37 AM »
Thanks Hobold.

It sure is a mysterious art. I have been able to get some multiple threads going with letters bouncing around the screen using some Microsoft sample code. But when I try to do some more esoteric stuff, it seems to go to pieces. I just need to spend the time playing until I learn the basics.

I suspect I might even be a bit older as I'm nudging towards my 70s  :))

Offline hobold

  • Fractal Fluff
  • *****
  • Posts: 397
Re: Multi-threading and Multiple Processors
« Reply #9 on: February 18, 2020, 10:24:16 AM »
It's never too late to start programming. Seriously.

Offline kosalos

  • Fractal Friar
  • *
  • Posts: 131
Re: Multi-threading and Multiple Processors
« Reply #10 on: February 18, 2020, 06:24:53 PM »
Are you using the GPU at all, or only the CPU?
this fractal app uses the GPU:  https://github.com/Kosalos/Fractal2
I can make you a simple demo app if all that's required if you're interested.

Offline ThunderboltPagoda

  • Fractal Furball
  • ***
  • Posts: 254
Re: Multi-threading and Multiple Processors
« Reply #11 on: February 18, 2020, 10:42:14 PM »
I have tried to simply segment the image into vertical slices

This is a very good idea if all pixels get the same treatment. This is the case with Lyapunov fractals, because there is no such thing as an "escape" here. You can watch Lyapunov Pagoda working exactly this way. But I doubt that it is the best way, if you don't know if a pixel gets 10 or 10000 iterations.

Offline kosalos

  • Fractal Friar
  • *
  • Posts: 131
Re: Multi-threading and Multiple Processors
« Reply #12 on: February 18, 2020, 11:04:09 PM »
the number of iterations per pixel doesn't matter.
what does matter is whether a pixel's value depends upon its' neighbors.
in the CPU you have control the for/next looping, so you know which pixels have already been updated.
In a GPU shader you don't have control over the pixel visitation order.
As long a pixel result is independent of its neighbors, use a  GPU shader, to render  up to 1000x faster than the CPU.
« Last Edit: February 18, 2020, 11:35:59 PM by kosalos »

Offline LionHeart

  • Uploader
  • *
  • Posts: 164
    • ManpWIN Fractal Generator
Re: Multi-threading and Multiple Processors
« Reply #13 on: February 19, 2020, 03:14:45 AM »
Hi Hobold,

I love programming. I'm just not very good at it  :embarrass:

Wow kosalos, that;s impressive. Great work  :thumbs:
Quote
I can make you a simple demo app if all that's required if you're interested.

Yes please. I'm always interested to learn new things. Does the code work on all GPUs or just specific ones? Anyway, it will be good to experiment. Many thanks.

Thanks ThunderboltPagoda. The issue is that I am only developing this for perturbation fractals and they have a dependency on nearby pixels. If it was pixel independent, I would use a guessing algorithm. I know Kalles Frakteler does some guessing as well as a wonderful way to progress through the image. But the source code is complex and not documented. So it's hard to find where it even does image scanning. If I create a number of threads, I may still speed up the images a fair bit. I want to do deep zooms without waiting a week for them to complete.

Hi again kosalos, Shucks. Perturbation is dependent on nearby pixels. However, for regular fractals (not using perturbation), this sounds like a way to get speed.

I have a single thread working so far. But when I add another, it crashes. So there must be something in shared memory causing a conflict. Maybe it's time to learn and understand using Mutex with CreateMutex().

Thanks everyone for this discussion.

Offline kosalos

  • Fractal Friar
  • *
  • Posts: 131
Re: Multi-threading and Multiple Processors
« Reply #14 on: February 19, 2020, 05:08:11 PM »
GPU shaders is still the way to go.
I imagine you have the coordinates of the Perturbation points in an array.
You pass that 'control structure' along with a destination texture to shader#1, who populates just the Perp pixels after your gazillion iterations.
Now you pass the same two parameters to shader#2, who iterates only the delta pixels (if current pixel is in P list, then abort).
Only problem: do you have the source code for the high precision number system(s)?
You would need to have shader renditions of those libraries.
Once you're spoiled by the speed of the GPU, you can't go back.
All GPUs should be okay; they differ only in the number of pixels that can be calculated in parallel.


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
258 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
179 Views
Last post October 27, 2019, 07:56:26 AM
by SCORPION