Parallel Distributed Agent-Based Simulations


An example of adaptive work distribution between processors for parallel agent simulations


About

We focus on agent-based simulations where a large number of agents move in the space, obeying to some simple rules. Since such kind of simulations are computational intensive, it is challenging, for such a contest, to let the number of agents to grow and to increase the quality of the simulation. A fascinating way to answer to this need is by exploiting parallel architectures. In this paper we present a novel distributed load balancing schema for a parallel implementation of such simulations. The purpose of such schema is to achieve an high scalability. Our approach to load balancing is designed to be lightweight and otally distributed: the calculations for the balancing take place at each computational step, and influences the successive step. To the best of our knowledge, our approach is the first distributed load balancing schema in this context. We present both the design and the implementation that allowed us to perform a number of experiments, with up-to 1,000,000 agents. Tests show that, in spite of the fact that the oad balancing algorithm is local, the workload distribution is balanced while the communication overhead is negligible.

Keywords: Distributed Computing, Parallel Algorithms, Behavioral Simulations.

Research aspects

Agent-based Simulations

Simulations based on agents are a class of computational models for simulating the action and interaction of individuals (or collective entities such as organizations or groups) with a view to assessing their effects on the system as a whole. For instance, agent-based simulations can be used to represent biological model like a school of fish, or scenario like pedestrian evacuation, or computational sociology experiments.

Parallel and Distributed Techniques

Such simulations are a natural candidate for parallel implementations. Parallelization techniques are even more important when applied to massively parallel architectures. Distributed and dynamic load balancing straategies represent both a challenge and an opportunity for high performance parallel implementation.

Massive Simulation on HPC hardware

With GEBs (2004), we first implemented the well known boids behavioral model on an nVidia NV35 GPU, thereby exploiting the intrinsically parallel nature of the problem. Today, our purpose is to exploit current multicore and multiprocessor platforms, in order to simulate a massive amount of agents (more than 1,000,000 agents). We aim to implement parallel simulation suited for massively parallel system (e.g. IBM SP6 available at CINECA).

People

Publications

Distributed Load Balancing for Parallel Agent-based Simulations
PDP2011 - 19th Euromicro International Conference on Parallel, Distributed and Network-Based Computing
Ayia Napa, Cyprus, February 9-11th, 2011

paper - abstract - demo video

Images and video

Links

Acknowledgements

The authors gratefully thank for its collaboration in providing some of the computational resources ENEA (Ente per le Nuove Tecnologie, l'Energia e l'Ambiente) Research Center in Portici (Napoli, Italy).

This work has been supported by a ISCRA CINECA.

We would like to thank Craig Reynolds for OpenSteer.