Work partitioning on parallel and distributed agent-based simulation

Work partitioning is a key challenge with ap- plications in many scientific and technological fields. The problem is very well studied with a rich literature on both distributed and parallel computing architectures. In this paper we deal with the work partitioning problem for parallel and distributed agent-based simulations which aims at (i) balancing the overall load distribution, (ii) minimizing, at the same time, the communication overhead due to agents' inter-dependencies. We introduce a classification taxonomy of work partitioning strategies and present a space-based work partitioning ap- proach, based on a Quad-tree data structure, which enables to: identify a good space partitioning (even when the distribution of agents on the fields is non-uniform) with a limited impact in terms of communication. Being a multi-objective problem, the results are difficult to compare and it is hard to foresee what can be the impact of one solution. For this reason we evaluate our strategy in a real context using a well-known behavior (the boids flocking model), on a distributed agent based simulation framework (D-MASON). The results show that our proposal provides a sensible impact on the performances of the system and scales in terms of the number of logical processors.