AI Multithreading & Parallelization

When working with parallel programming most of the problems one might encounter are related to race conditions and deadlocks.

Race conditions appear when operations of the multi-task system depend on the order in which the code parts are executed. Race cConditions also arise when several threads of a multi-thread application try to get access to data simultaneously and one thread is performing write operations on that data. This can lead to unexpected results. Deadlock describes a condition where two or more processes are waiting for an event or communication from one of the other processes. Thus all threads involved in this deadlock are blocked and cannot work anymore.

Another problem that might arise is the lack of performance in such a multi-threaded application if there are contention point situations. Bjoern talked about the memory wall related to this: This is when you hit the bandwidth limit of throughput from the memory and latency of accessing memory. You might want to share as little data as possible and minimize the amount of times you synchronize data to improve latency. You have to find the right balance between minimizing sharing and maximizing locality.

Bjoern elaborated on different methods for synchronization. The first one is asynchronous calls, which has the benefit to scale well (with task pools) and has potentially better memory locality. But then you have to take care of determinism and be aware of side effects because it's difficult to get the syncing right. The second system he introduced to us was parallel agents. This system is a little bit more complicated because it not only keeps the idea of task pools (with agents ordered into it), but this also introduces the problem of the ownership management.

Ownership management must be done when agents share data and memory (i.e. objects or entities) and must communicate with each other to regulate the access to that data and memory. A lot of synchronization is necessary at this point. To solve this issue, a two step approach is taken: In the first step, which is the collection stage, the agents only can write private data (read only from objects and/or memory) and request changes to public data. Between the first and the second step, the system determines who can have access to which object. The second step then allows the agents to alter the objects they have been granted.

The advantages of this system is that it guides the parallelization, scaling is possible and has implicit syncing. The cons of the system are that the implementation effort is high. You have a lot of work to do to achieve and implement this system. Also, it has bad locality and it's hard to achieve some kind of determinism. You still have to cope with getting the synchronization right and avoid side effects. And finally, since the access to the data is deferred, you don't have immediate access to the data but must wait until the next frame (if no other agent wants to access the object/data).

The last way to synchronize cited by Bjoern was Data Parallel Systems. This means one might slice the agents and group aspects of them into separate tasks (such as pathfinding, sensing, logic, ...). Basically it works as the parallel agents but breaks them down into separate tasks. The advantage of this system is that lean data structures are used which improves scalability and enables us to scale the system appropriately. It's deterministic and has implicit synchronization while working in an explicit context. On the other side, this system requires quite some implementation efforts and deferring is still necessary. Getting the synchronization right is still an issue.

He concluded his talk stating that we really need to understand both, our game and our target hardware. We must be sure that our code is error-free first before jumping into parallelization (because it would be hard to make the difference to determine if a problem arises due to some problem in the code or in determinism). And finally KISS (Keep It Simple Stupid)...

The Art of Concurrency and AI System Architecture

The contributors of this panel agreed upon the need to have a more general sub-system framework which doesn't grant access to low level threading or to shared data. While we have learned the pros and cons of shared data access (and how to improve that situation), the thread masking is based upon platform dependent threading problems. Each platform has its own approach to parallel processing and thus, the implementation of threading on those platform is platform specific. Masking or hiding this platform dependency from the user might help him to concentrate more on AI than the technical background.

The participants also agreed that one should plan his own AI system with multi-threading in mind. Most often it's problematic, if not impossible, to port an already existing, single-thread oriented AI solution into a multi-threaded environment. When porting, try to not use explicit synchronization. Markus put an emphasis on clean code which will help pin-pointing problems.

Julien went a step further and added that you also should have a clean structure. But then, you don't only have to take a look at the object oriented side of the coin but also take into account the data flow (As a personal note I'd like to direct you to "Object thinking" by David West which treats this topic in an highly interesting way).

"Object thinking" by David West

Advice and Tales from the Trenches

Phil was astonished that there aren't that many students who start small indie companies. It would show their mental capability to create, design, implement, and actually finish a project. It would also show off their skills. Eduardo put emphasis on the fact that this would also help you create a portfolio which proves that you can do your work. Miezko said that the last few percents of a game take fifty to sixty percent of the time.

The speakers also talked about creating for designers. Since designers are not necessarily technical people, it’s better to have a system that allows them to avoid breaking the content too easily and to avoid creating impossible setups or designs. You also should train designers to build self created examples which can be used to show the concept and proof functionality.

Page 4