Jump to content
  • Advertisement
Sign in to follow this  
jamesleighe

Data Parallel Multithreading

This topic is 2596 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

I am trying to implement data parallel multithreading into my engine.

For those not sure, this is a scheme where instead of splitting rendering, physics etc into separate threads you make rendering and physics use multiple threads to update themselves instead.

Q1) If I was multithreading rendering by having one core handle 'X' objects won't the rendering states or whatever get mixed up since it's parallel now?

Q2) What is the best way to thread physics? Since each object needs to know about other objects to update it's information. One way could be to have a 'previous' state saved off and use that, but that roughly doubles the memory needed for physics.

Q3) What happens if two threads try and read/write the same variable at the same time? Should I always use locks to prevent this?

Q4) It occurs to me that things like AI will need to know about other AIs to decide it's next move so storing 'previous' states for more than just physics...

Thanks as usual!

Share this post


Link to post
Share on other sites
Advertisement
if you think in terms of tasks, you will find it much easier to synchronize and program for multiple cores. Check out Intel Threading Building Blocks for examples on task based programming. Tasks are basically chunks of work to do that are placed into a queue and then processed by threads which have been initialized at program startup. http://threadingbuildingblocks.org/documentation.php If each system runs in its own thread, synchronization becomes unwieldy. Tasks have a more defined behavior that makes programming easy.

Share this post


Link to post
Share on other sites

if you think in terms of tasks, you will find it much easier to synchronize and program for multiple cores. Check out Intel Threading Building Blocks for examples on task based programming. Tasks are basically chunks of work to do that are placed into a queue and then processed by threads which have been initialized at program startup. http://threadingbuil...cumentation.php If each system runs in its own thread, synchronization becomes unwieldy. Tasks have a more defined behavior that makes programming easy.


Thanks, but this doesn't really answer any of my questions. I am going to be using a 'task' system, but I need help with data parallelism.

Share this post


Link to post
Share on other sites
It helps to think in terms of dataflow or flow-based programming somewhat, with black-box processes forming a DAG, with large amounts of data flowing through the graph.

1) This isn't really a complete question -- rendering is made up of many tasks.
e.g.
* There's culling, which determines the set of objects in the world that need to be rendered. This is a process that takes a list (or a hierarchical structure) of objects as input, a culling device (such as a camera frustum) as input, and produces a list of visible renderables as output.
* There's the sorting of renderables -- this takes an unsorted list of renderables as input, and produces an ordered list of renderables as output.
* There's the building of command buffers, which takes a sorted list of renderables as input, and either calls DX/GL functions as output to either send commands to the GPU, or to produce a command buffer object as output.

Each of these is a task in your task graph. Furthermore, most of these tasks are data-parallel in isolation -- e.g. when culling, you can have many threads all reading from your "world object list" at once, and each inspecting a different part of the world to produce one "visible renderable" list per thread. You could then have another task that takes each thread's result as input, and produces a combined list as output.

2) Again, think about processes with inputs and outputs. Avoid any kind of processing that wants to use the same data as an input and an output at the same time. e.g. a task could use the position of every object as input, and produce a list of collision forces as output. Another task could then use this list of forces as input and produce new positions as output. This way you're not depending on all positions as input and producing updated positions within the same task.
Your task system should support task dependencies, so the latter task (which is actually several data-parallel jobs) won't begin execution until the former task has fully completed.

3) It's called a race-condition and you don't want to do that.
No, you shouldn't use locks -- you should describe dependencies between your tasks and their inputs/outputs so that two tasks that want to read/write a particular data item are not scheduled to execute at the same time.

4) As above. Think in terms of input and output buffers flowing through a graph of processes.

Share this post


Link to post
Share on other sites
Ok, so I thought about it for a while and I have a few questions.

Q1) For generating draw lists, how can I effectively multitask octree traversal?
- I have thought about giving each thread a broad section of the world to be responsible for but this would leave one thread with a heavy workload while the others will have little/none.

Q2) For physics, I update positions (with velocities etc.), generate contacts, then I have to filter contacts so two objects will not be listed twice. I cannot think of a multitask method of filtering contacts.

Thanks again!

Share this post


Link to post
Share on other sites

Q3) What happens if two threads try and read/write the same variable at the same time? Should I always use locks to prevent this?
[/quote]
This sentence suggests that you don't yet have the basics of parallel computing down. Trying to build a large system when you don't have these basics will hurt you. I'd suggest you spend some time learning about multi-threading by building smaller projects that are easy to understand - and more importantly debug.

Putting multi-threading into your engine now when you don't quite understand it will be a frustrating experience. If you care about the outcome of your engine, you'll put it aside until you are more comfortable with threading and parallelism.

This is aside from the usual "do you even need multi-threading" question, but I won't go there.

Share this post


Link to post
Share on other sites
Yea, I am pretty scrub level at threads.
But the engine is currently very small, so that works out!

I'm still curious as to reading/writing to a memory location by multiple threads (just to help me understand things, not that I would do any of this).
* If one thread writes 2 to some memory and another thread writes 3 to the same memory will the value once everything is finished rely on a race condition or will it be indeterminate since the cores may wait to flush changes to ram?
* If two threads read the same memory at the same time this is ok right?
* If two threads write the same thing to the same memory this is ok right?
* If one thread writes to some memory and afterwords another thread tries to read that memory it may not be updates since thread ones core may not have flushed the changes to ram?

I'm pretty scrub level at everything really, but I get by. I also try to understand how things work as much as I can so I end up asking allot of stupid questions.
Thanks guys!

Share this post


Link to post
Share on other sites
1) If one thread writes 2 to some memory and another thread writes 3 to the same memory will the value once everything is finished rely on a race condition or will it be indeterminate since the cores may wait to flush changes to ram?
2) If two threads read the same memory at the same time this is ok right?
3) If two threads write the same thing to the same memory this is ok right?
4) If one thread writes to some memory and afterwords another thread tries to read that memory it may not be updates since thread ones core may not have flushed the changes to ram?
1) There's no guarantees - it depends on the CPU architecture.
On a regular x86 PC: if the variable is CPU-word sized and properly aligned, it will either be 2 or 3, depending on chance. If the variable is not word-sized and/or is not properly aligned, then it could have some bytes written by one thread and some bytes written by another thread, causing a completely corrupt value!
e.g. if we had a misaligned [font="'Courier New"]short[/font] and one thread wrote 513 (0x0201) and the other thread wrote 298 (0x012A), then the result could either be 513 (0x0201), 298 (0x012A), 554 (0x022A) or 257 (0x0101)!
2) yes, perfectly fine. Things don't have to be "thread-safe" if they are read-only.
3) uhhh, technically. It's still not something that should oft be used though ;)
4) Yes, this is where memory barriers come into play. Again, this highly depends on the CPU architecture.
However, if you're writing code that is affected by this kind of detail, then that means that you're writing very low level code! e.g. the person who creates the internals of a lock class (a "mutex" in literature, or a [font="Courier New"]CRITICAL_SECTION[/font] on Windows) needs to be aware of this, but your average application/games programmer does not.

Share this post


Link to post
Share on other sites
Many of the problems with multi-threading occur on the "transactional" level, not only on the level of individual memory operations. Even were writes to a single memory location "safe", you still have a problem with multi-step operations. So say you want to push an object onto a dynamic array. Doing this would result in a number of operations, copying the bits that make up the object into the buffer, and incrementing some internal counter. It could also result in a re-allocation, and the associated book-keeping updates for the internal capacity and buffer values. This entire block of operations needs to complete before anyone reads from the data structure.

Incidentally, this one reason why default memory allocation is expensive. You have a giant shared data structure representing available/allocated memory that needs to be maintained while potentially many threads are requesting/releasing memory from this data structure.


2) If two threads read the same memory at the same time this is ok right?
[/quote]
Reading non-mutable data from multiple threads is safe. However, if any thread can change the data, then it may not be safe. A common example of this is someone who thinks they only need a lock during write operations. This is not true, because you need to prevent readers during updates too.

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!