Kadur
27.05.11, 14:42
A few years ago hardware designers started running into problems getting more performance out of processors. The average personal computer's clock speed hasn’t gone up much since 2005. Instead they have been busy increasing transistor count and giving us more CPU cores to work with. These days everyone but a few Pentium 4 users (time to upgrade guys) have 2-4 cores available to them and there are a few 6-core systems floating about. Each core usually has 2 hardware threads available so for a quad-core Intel CPU that is 8 hardware threads available for concurrent use.
This means that to make games that do more or run faster you have to start thinking of parallel solutions to problems, something that is very, very difficult for games in general because of their nature and constantly shifting shared data. You don’t want 2 separate threads changing the same value in the game because the end result can pretty much be random, so changes like that has to be protected by "critical sections", a part of code only one thread can access at once, the others have to sit and wait for it to finish so if you do this a lot even your 8-core CPU might end up running slower than a single-core one. That is why to get good multi-threaded performance you want to solve problems in ways that touches shared data as little as possible or not at all.
Ok, this is making my head hurt. I'm about to make a reply to the thread asking what this means for me as a player...
The AI tasks are now running their processing in parallel The AI tasks run roughly twice as fast and overall in the game this results in a 25% increase in performance over latest Semper Fi on my quad-core. Note that this number is not final because we still have optimizations to do and FTM is currently doing quite a bit of extra AI and other processing. Anyways keep reading for more details if you are interested in the technical side of this! If you don’t care about multi-threading I got another fun little fix we recently did: The Kiel Canal is now in the game.
No locking please!
It's always much harder to introduce things like multi-threading support to an existing game because nobody thought of those particular problems when algorithms were thought out so unless you want to rewrite everything you need to look for spots that have no shared modified data and run those in parallel. This isn’t very common, however the AI in HoI works in a way that makes this doable: The AI agents do not modify any game state directly (except their own), instead they queue up any commands they want run in a lock-free queue structure which means that other threads do not have to wait and this queue is then executed in serially in order afterward. This works well because the biggest part of AI processing is deciding what to do, not actually doing it.
Future Games
In future games like Crusader Kings 2 I’ve had the luxury of not having to add multi-threading afterward, so the core processing things are built with this in mind. It's not as good as if our engine was built from the ground up for MT support but it makes things much easier than adding in support later. The model we follow there is also based around limiting any locks and works by splitting up tasks with shared data like this:
I'll use a simplified example from CK2, before we would have a single Character::DailyUpdate function run serially for each character for anything that needed to be done on a daily basis, now this is split up in 3 steps:
step 1: Character::DailyUpdateOnlyChangeSafePrivateAndCache (run in parallel)
step 2: Character::DailyUpdateSelfDontReadOthers (run in parallel)
step 3: Character::DailyUpdateSerial (run serially)
In step 1 a character is free to look at the public data of any other character and modify its secret internal data only. In step 2 the character is free to modify its public data, but not read any data from other characters. If it needs to decide something based on another characters data it would have to store this data in its secret internal data as part of step 1. Finally step 3 is run in serial for any algorithms too complex or slow to split up in the above way.
This means that we don’t need any locks at all that slow things down while guaranteeing that we always get the same results from calculations no matter what order characters are processed. Processing wise it is perhaps not 100% optimal but strikes a good balance between 1) being easy to use (important for developers to get stuff done) and 2) not wasting lots of memory by duplicating all states that multiple threads need to modify.
http://forum.paradoxplaza.com/forum/showthread.php?538546-For-the-Motherland-Developer-Diary-9-No-more-free-lunch-in-the-bunker
This means that to make games that do more or run faster you have to start thinking of parallel solutions to problems, something that is very, very difficult for games in general because of their nature and constantly shifting shared data. You don’t want 2 separate threads changing the same value in the game because the end result can pretty much be random, so changes like that has to be protected by "critical sections", a part of code only one thread can access at once, the others have to sit and wait for it to finish so if you do this a lot even your 8-core CPU might end up running slower than a single-core one. That is why to get good multi-threaded performance you want to solve problems in ways that touches shared data as little as possible or not at all.
Ok, this is making my head hurt. I'm about to make a reply to the thread asking what this means for me as a player...
The AI tasks are now running their processing in parallel The AI tasks run roughly twice as fast and overall in the game this results in a 25% increase in performance over latest Semper Fi on my quad-core. Note that this number is not final because we still have optimizations to do and FTM is currently doing quite a bit of extra AI and other processing. Anyways keep reading for more details if you are interested in the technical side of this! If you don’t care about multi-threading I got another fun little fix we recently did: The Kiel Canal is now in the game.
No locking please!
It's always much harder to introduce things like multi-threading support to an existing game because nobody thought of those particular problems when algorithms were thought out so unless you want to rewrite everything you need to look for spots that have no shared modified data and run those in parallel. This isn’t very common, however the AI in HoI works in a way that makes this doable: The AI agents do not modify any game state directly (except their own), instead they queue up any commands they want run in a lock-free queue structure which means that other threads do not have to wait and this queue is then executed in serially in order afterward. This works well because the biggest part of AI processing is deciding what to do, not actually doing it.
Future Games
In future games like Crusader Kings 2 I’ve had the luxury of not having to add multi-threading afterward, so the core processing things are built with this in mind. It's not as good as if our engine was built from the ground up for MT support but it makes things much easier than adding in support later. The model we follow there is also based around limiting any locks and works by splitting up tasks with shared data like this:
I'll use a simplified example from CK2, before we would have a single Character::DailyUpdate function run serially for each character for anything that needed to be done on a daily basis, now this is split up in 3 steps:
step 1: Character::DailyUpdateOnlyChangeSafePrivateAndCache (run in parallel)
step 2: Character::DailyUpdateSelfDontReadOthers (run in parallel)
step 3: Character::DailyUpdateSerial (run serially)
In step 1 a character is free to look at the public data of any other character and modify its secret internal data only. In step 2 the character is free to modify its public data, but not read any data from other characters. If it needs to decide something based on another characters data it would have to store this data in its secret internal data as part of step 1. Finally step 3 is run in serial for any algorithms too complex or slow to split up in the above way.
This means that we don’t need any locks at all that slow things down while guaranteeing that we always get the same results from calculations no matter what order characters are processed. Processing wise it is perhaps not 100% optimal but strikes a good balance between 1) being easy to use (important for developers to get stuff done) and 2) not wasting lots of memory by duplicating all states that multiple threads need to modify.
http://forum.paradoxplaza.com/forum/showthread.php?538546-For-the-Motherland-Developer-Diary-9-No-more-free-lunch-in-the-bunker