Jump to content
  • Advertisement
Sign in to follow this  
skyfire360

Thread Management - Design patterns for load balancing?

This topic is 4215 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I had big plans for a multithreaded graphics engine complete with physics, animation, and motion capture. And for the first time ever in all of the myriad of projects I've started, I've actually seen it most of the way through! I've got a thread for : * Management - Starting, monitoring, and stopping threads * Rendering - Direct3D based * Scene Animation/Physics - Just barely hooked into the PhysX library, but it's coming along * Loading - streaming and/or static loading of meshes, textures, and shaders * Input - Using DirectInput with a basic input-state manager All my threads are running at the same time and at roughly the same rate, and that's where my problem lies: the Input thread really doesn't need to run as fast as the Rendering thread tries to run, but it should be run faster/polled more than the Loading. And I'd like to cap my engine at 60fps and use some of the "extra" cpu time on other threads. While I've messed around with thread priorities, profile results only show a slight increase in load balancing. 'SleepEx'ing works to a point, but sleeping for 1 ms results in a 11-16 ms delay, after being pulled off the queue while sleeping and then put back on at the end after 1 ms. 'SleepEx(X)'ing only guarantees it will sleep for at least X ms, so it's not that helpful for trying to load balance efficiently. Are there any design patterns out there that have been applied to multithreaded load balancing? Semaphores seem like they might be able to do it, but it seems they suffer from the same queue removal as SleepEx.

Share this post


Link to post
Share on other sites
Advertisement
I've never tried it myself, but I believe (in Windows at least) you can create things called "fibres" or something. They're basically threads, but you control when they are executed instead of the kernel. Of course, this means you'll have to write your own scheduler too.

Share this post


Link to post
Share on other sites
Quote:
Original post by DudeMiester
I've never tried it myself, but I believe (in Windows at least) you can create things called "fibres" or something. They're basically threads, but you control when they are executed instead of the kernel. Of course, this means you'll have to write your own scheduler too.
Do not use fibers. Do not, do not, do NOT. They're a tool for migrating certain classes of legacy applications. They are not meant for general use!

Now, as for the OP. Separate the concept of logical and hardware threads. What you listed are logical threads; they're separable tasks that communicate as if they were threads. However, a system only has a fixed number of hardware threads -- one for each core, or two in the case of hyper threading. The OS injects an intermediate layer for us, of course, but we can ignore that distinction for the most part. Now, allocate your logical threads to real threads, and time slice them. So each hardware thread runs an infinite loop, and ticks the logical threads it owns as necessary. You might get two graphics ticks and an input tick through each loop iteration on one thread, for example.

Share this post


Link to post
Share on other sites
Quote:
Original post by skyfire360
Are there any design patterns out there that have been applied to multithreaded load balancing? Semaphores seem like they might be able to do it, but it seems they suffer from the same queue removal as SleepEx.

Load balancing is a pure run-time thing. Design pattern deals with structural design. They are not related, since the "amount of work which is done in a thread" has nothing to do with the structure of a program.

Sleep() is a very particular function. Sleep(N) does not pause your thread during N milliseconds, it pause your thread, tell the scheduler to activate the next thread in the list, and make sure that your thread won't be woke up before N milliseconds are elapsed. In the end, it means that your thread wait at least N milliseconds before the wake up. The exact time it waits is dependent on the OS you use, more exactly it depends on the time quantum of the system. The time between two subsequent activations of the same thread is usually 10ms, but it will depends on the system load and on the other thread priorities. Sleep(0) is a particular invocation of Sleep(), since it will just stop this thread handling and give control to the next thread in the list.

If you want to have a finer control over the time you sleep, you'd better use large N values (because an error of 1 to 5 ms would then be negligeable). Unfortunately, you can't do that in threads that need to work on every frame.

Regards,

Share this post


Link to post
Share on other sites
sleep based functions with small interval (<10ms) are generally regarded as yield() type function, where the scheduler just moves on to other threads and eventually comes back after specified time goes by. It is not a precise form of scheduling.

Instead have your threads perform N tasks before calling sleep and use that to balance the priority. So you can do 100 rendering tasks then sleep and see how it works and increase/decrease that number. Other threads should behave the same way. Tuning this pseudo-work quanta is a bit easier than messing with OS specific scheduling. For very hig proirity threads you may never want to call sleep and let the OS work in the other threads while the high priority one is running.

Share this post


Link to post
Share on other sites
Thanks for the replies all!

Promit: I'll certainly stay away from fibers with that strong of a warning. That's a great idea about the 'ticking' and allocation of virtual threads to the actual hardware threads, as it means you can start/stop threads depending on how many cores are present. However, this system is still susceptible to the problem of blocking and long function calls. If I were to implement virtual threads and 'tick' them as you suggest, there might be a problem that one of those 'ticks' lasts significantly longer than is acceptable.

Say, for instance, between the two ticks of a RenderFrameVirtualThread the TextureLoaderVirtualThread is ticked. If the TextureLoader received a request to load a 2048x2048 texture, its tick would be extraordinarily long, meaning the RenderFrameVT wouldn't be ticked for nearly half a second (using the texture loading library I have). Short of implementing my own texture decompression library that can pause mid-load, I can't think of a way around this.

Emmanuel Deloget: ::smiles:: I'm aware that load balancing is a run-time concept, but I was looking more for Design Patterns that would allow for load-balancing to occur at run-time. Promit's idea above is very close to the idea I was looking for, but still runs into one problem. Though by far, it's better than the ideas I was implementing. Thanks for confirming my thoughts on SleepEx, as I hadn't been able to find anything more concrete than what my professor had said in class.

Achacha: Interesting! While at first this would have things running in spurts, the theory is that it would eventually find a happy-medium and run smoothly after correct "sleep" values are found. Does this hold up when the timings change rapidly, like when a calm scene experiences an explosion and a physics-intensive scene occurs?

Thanks again all, love the ideas. I'm open to any more suggestions/resources that anyone might have :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!