A Case Study of Hybrid Dataflow and Shared-Memory Programming Models: Dependency-Based Parallel Game Engine

• Vladimir Gajinov Universitat Politecnica de Catalunya / Barcelona Supercomputing Center
• Igor Eric University of Belgrade
• Saa Stojanovic University of Belgrade
• Veljko Milutinovic University of Belgrade
• Osman Unsal Barcelona Supercomputing Center
• Eduard Ayguadé Universitat Politecnica de Catalunya / Barcelona Supercomputing Center
• Adrián Cristal Artificial Intelligence Research Institute / Spanish National Research Council

Resumo

Recently proposed hybrid dataflow and shared memory programming models combine these two underlying models in order to support a wider range of problems naturally. The effectiveness of such hybrid models for parallel implementations of dense and sparse algebra problems is well known. In this paper, we show another real world example for which hybrid dataflow models provide better support than traditional shared memory models. Specifically, we compare these models using the game engine parallelization as a case study. We show that hybrid dataflow models decrease the complexity of the parallel game engine implementation by eliminating or restructuring the explicit synchronization that is necessary in shared memory implementations. The corresponding implementations also exhibit good scala-bility and better speedup than the shared memory parallel implementations, especially in the case of a highly congested game world that contains a large number of game objects. Ultimately, on an eight core machine we were able to obtain 4.72x speedup compared to the sequential baseline, and to improve 49% over the lock-based parallel implementation based on work-sharing.

Palavras-chave: Games, Engines, Synchronization, Weapons, Complexity theory, Programming, Data models, dataflow, shared memory, game engine