Multithreading

[greenman]

Hello all,

I just read some posts in the GameState thread and realised that we (in my opinion) didn't take multithreading in account as much as we should.
But it's still time to change this
I think this will become more and more important, as lot's of potential users already have a multi-core cpu and in my opinion it is important to start thinking about and considering these things in early development and not doing hacks after everythings up and running ...


The most extensive tasks to be parallelized are probably:
- ogre rendering (afaik ogre is not yet able to do all the tasks parallel, but yet some things can be done using multithreading)
- physics engine (in order to make this possible, the accesses to the universe - meaning world objects - must be threadsafe)
- networking (only few things so far, but if universe accesses would be threadsafe there would be a lot of potential)
- probably other things too

In my opinion a good way doing this would be using a compiler flag called 'mt' to enable all the threading stuff (as mutexes, threadcreation, etc) in order to not slow down computing on a single core system.

What do you think about that ?

[beni]

Yo greenman. It is true we should have taken this into consideration a lot earlier than we had. However I too think that putting a thread-layer somewhere in between could still be possible.

The advantages of the multi core CPUs should be exploited without question. Also we should not think about a certain thread number, but just create as many threads as feasible. Schedulers will do the rest and the overhead is not that big.
Excluding threading at single core CPUs is a nice idea, but I don't know if it is that important.

I've seen that there are several (or at least one) articles about multi threading in the Ogre Wiki. Let's have a look at it, and if it's about thread safe Ogre or even splitting Ogre into several threads, we should definitely look into it.

To your list we could add AI and the input system.

From a rough view I'd say that there are only two critical meeting points, where all threads have to have consistent information: Changing or viewing the scene.
I remember some stories about strange behavior, when physics act and react on something else that is actually seen on the screen. For similar reasons the other threads need to exchange this information reliably.
So, as long as we can package our code into threads without too much waiting for each other, this is something cool.

[x3n]

this is quite difficult because physics, graphics and orxonox all use the position/rotation of objects... I don't know if we can separate those tasks into multiple threads.

by the way, I've spent much work to make TCL scripts threadable. At the moment we aren't using them, but maybe this will become more important in the future. TCL will be our moding-language to create user-specific scripts and HUD-overlays. But this has yet to be developed. At least multithreading works (you've seen an example at the presentation, namely the telnet server)

[1337]

I agree on most points, especially on x3n's. It really is going to be tricky when half of the threads use the same scene data. But I think it should be possible anyway.

Nevertheless I will continue working on the game states and as a matter fact I will try to think about multithreading as much as it is possible for me.
The main reason I'm doing the game states stuff is that currently, it's not even possible to have a simple main menu without writing hacks into Orxonox.cc
And as I said previously in the other thread: We ARE going to write it again, I promise... It's not that we're all that experienced with writing game engines

[greenman]

I think this task is not extremely difficult, but maybe a little bit extensive...

Steps required to make Objects threadsafe:
- every threadable object needs a mutex for accesses to its variables
- either lock the mutex every time you access a variable and unlock it after access
- or lock it permanently during complex operations

so once we decided which concept to use for multithreading it's just a matter of work ...

what do you think ?

[beni]

Just think about the non critical sections parts first. If we have nothing besides mutex on every variable multi threading is totally useless. Unless we have actual parts which can be made parallel, this wouldn't make sense. I think a lot of things could be parallel when we work with copies of values instead of pointers, but that would totally change the way we have to write code. Or am I wrong here?

[greenman]

I think if mutexes make the objects threadsafe then everything working with the objects could be parallel i.e. ai || network || physics || input

only on things like level changes we would have to stop/pause all threads until the change is finished

[x3n]

ok, but then every position vector (and every other relevant variable) needs a mutex... each tick() of each object may change them. I don't think that's the way we should do this.
maybe it works with creating a copy of all relevant variables and let the physics engine work with them. but this would be bad for perfomance...
there's another option I can think of: instead of puting the whole physics engine into it's own thread, we could just outsource some tasks. physics engine (in the main thread) will use the results in the next tick. This could also be used by the AI. but I don't know if this works.

[greenman]

i would say we don't have a mutex per each variable but just for each object because some variables have dependencies on the others of the object and they should probably be changed 'atomic'.

i don't know what the overhead for this solution would be, but like that it would be possible to do virtually everything parallel and we wouldn't have that many locks

[beni]

It could work with shared variables and outsourcing expensive information.

I would propose that we check out already existing (and working) concepts before discussing concepts, concentrating on the wrong things.

I guess there are articles and other forum discussions where this subject is dealt with with enough generalization so we could use it for Orxonox as well.

[1337]

i would say we don't have a mutex per each variable but just for each object because some variables have dependencies on the others of the object and they should probably be changed 'atomic'.

i don't know what the overhead for this solution would be, but like that it would be possible to do virtually everything parallel and we wouldn't have that many locks

As far as I can 'see' into multiple threads, mutexes will be the least of our concerns. Things like objects that exist at t0 and don't exist at t1, where t0 and t1 are times in different turns of a thread, are only one example of how difficult multithreaded programming actually is.

[1337]

I totally agree with Beni. Google has helped me in a lot of things, mostly when working with Ogre. And multithreading is every project's issue, so there actually is something on the web:

Something general about multithreaded game engines:
http://arstechnica.com/news.ars/post/20050324-4733.html

Another, different approach:
http://harkal.sylphis3d.com/2006/02/16/ ... -machines/

A very interesting discussion, but quite lengthy (only read the first page):
http://forums.tweakguides.com/showthread.php?t=3009

Comparing three different approaches, very interesting:
http://mooproductions.blogspot.com/2006 ... nning.html

A must to read, also compares the three approaches, but more thoroughly:
http://www.gamasutra.com/features/20060 ... n_01.shtml

An interview with the UT3 engine lead, talking about what should actually be multithreaded:
http://www.anandtech.com/cpuchipsets/sh ... i=2377&p=3

Multithreaded programming without locks:
http://en.wikipedia.org/wiki/Lock-free_ ... algorithms

A few threads in the OGRE forum (only read the first two)
http://www.ogre3d.org/phpBB2/viewtopic. ... 6f4e2718c6
http://www.ogre3d.org/phpBB2/viewtopic.php?t=21578
http://www.ogre3d.org/phpBB2/viewtopic.php?t=26496


(and that all that originated from the first half of my initial google search for multithreaded game engines...)

Btw: Shouldn't take more than one or two hours to get through the articles and discussions (took me a little bit longer, since there's a lot of not so useful texts out there)

[1337]

To give a very little summary on my readings:
- Multithreading a game is something very hard to do
- There are always simple approaches that will yield maybe 20% in the best case
- I would prefer function parallelism over data parallelism since the latter seems to be a lot harder
- Multithreading only makes sense with parts of the game that are not highly sequential (what a surprise). So multithreading our game logic would be a very bad idea, but physics and AI could yield quite a boost.
- It is not such a good idea to already think about N threads in orxonox, because that's way out of our league (probably only possible with data parallelism). We will have to stick with a fixed or maximum number of threads (4 or so without minor ones like tcl).
- It will be a real pain in the... X3n could tell a story or two about the tcl threads...

I hope I haven't demotivated everyone with all the crying and posting lots of heavy articles. But please, take the time to read some, esp. the interview with Tim Sweeney about UT3.

[beni]

Thank you very much for your effort. I will read those articles when I get to it after my exams. Looks quite good at first sight.

I don't know how often you guys have worked with threads, but my experience with threads were quite traumatizing at best. So I never thought that it is going to be easy. All I know is that the concept must be really good, otherwise some really strange errors may occur which are practically unreproducible and unsolvable.

I'm looking forward however to see what we're be able to establish in Orxonox.

[1337]

Something I'd like to add: Currently (at least on my box), rendering is using up about 99% of the time. So we cannot reference the current code when it comes down to synchronisation. We would have to first find out where the bottlenecks actually will be, since we don't have them for now.