Experimenting the GPU delegation principle for MABS: Reynold's Boids as a case study

Experimenting the GPU delegation principle for MABS: Reynold's Boids as a case study

Emmanuel Hermellin
Fabien Michel

LIRMM - Laboratoire Informatique Robotique et Microélectronique de Montpellier Université de Montpellier - CNRS - 161 Rue Ada, 34090 Montpellier, France

Corresponding Author Email: 
{hermellin,fmichel}@lirmm.fr
Page: 
109-132
|
DOI: 
https://doi.org/10.3166/RIA.30.109-132
Received: 
N/A
|
Accepted: 
N/A
|
Published: 
30 April 2016
| Citation
Abstract: 

General-Purpose Computing on Graphics Processing Units (GPGPU) allows to extend the scalability and performances of Multi-Agent Based Simulations (MABS). However, GPGPU requires the underlying program to be compliant with the specific architecture of GPU devices, which is very constraining. In this context, the GPU Environmental Delegation of Agent Perceptions principle has been proposed to ease the use of GPGPU for MABS. The idea is to identify in the model some computations which can be transformed into environmental dynamics and then translated into GPU modules. In this paper, we further trial this principle by testing its feasibility and genericness on a classic ABM, namely Reynolds’s boids. The paper then shows that applying GPU delegation not only speeds up boids simulations but also produces an ABM which is easy to understand, thanks to a clear separation of concerns.

Keywords: 

GPGPU, MABS, Flocking, CUDA.

1. Introduction
2. Les boids de Reynolds
3. Proposition d’un modèle de boids
4. Délégation GPU des perceptions agents
5. Délégation GPU et flocking
6. Expérimentation
7. Discussion autour de la délégation GPU
8. Conclusion et perspectives
  References

Badeig F., Balbo F. (2012). Définition d’un cadre de conception  et d’exécution pour la simu- lation multi-agent.  Revue d’Intelligence Artificielle, vol. 26, no 3, p. 255-280. Consulté sur http://dx.doi.org/10.3166/ria.26.255-280

Beurier G., Simonin O., Ferber J. (2003). Un modèle de système multi-agent pour l’émergence multi-niveau.   Technique et Science Informatiques,  vol. 22, no 4, p. 235–247. Consulté sur http://tsi.revuesonline.com/article.jsp?articleId=4795

Bourgoin M.  (2013). Abstractions performantes pour cartes graphiques.   Thèse de doctorat non publiée, Université Pierre et Marie Curie.

Che S., Boyer M., Meng J., Tarjan D., Sheaffer J. W., Skadron K. (2008). A performance study of general-purpose applications on graphics processors using CUDA. Journal of Parallel and Distributed Computing, vol. 68, no 10, p. 1370-1380.

Grignard A., Taillandier  P., Gaudou B., Vo D., Huynh N., Drogoul A.  (2013). GAMA 1.6: Advancing the Art of Complex Agent-Based Modeling and Simulation.  In G. Boella, E. El- kind, B. Savarimuthu, F. Dignum, M. Purvis (Eds.), Prima 2013: Principles and practice of multi-agent  systems, vol. 8291, p. 117-131. Springer Berlin Heidelberg. Consulté sur http://dx.doi.org/10.1007/978-3-642-44927-7_9

Hermellin E., Michel F., Ferber  J.   (2015). État de l’art sur les simulations multi-agents et le GPGPU. Revue d’Intelligence  Artificielle, vol. 29, no 3-4, p. 425–451. Consulté sur http://dx.doi.org/10.3166/ria.29.425-451

Kubera Y., Mathieu P., Picault S. (2011). Ioda: an interaction-oriented approach for multi-agent based simulations. Autonomous Agents and Multi-Agent  Systems, vol. 23, no 3, p. 303-343. Consulté sur http://dx.doi.org/10.1007/s10458-010-9164-z

Laville G., Mazouzi K., Lang C., Marilleau N., Herrmann B., Philippe L. (2014). MCMAS: A Toolkit to Benefit from Many-Core Architecure in Agent-Based Simulation.  In D. an Mey et al. (Eds.), Euro-par 2013: Parallel  processing workshops, vol. 8374, p. 544-554. Springer Berlin Heidelberg.  Consulté sur http://dx.doi.org/10.1007/978-3-642-54420-0_53

Laville G., Mazouzi K., Lang C., Marilleau N., Philippe L. (2012). Using GPU for Multi-agent Multi-scale Simulations. In Distributed  computing and artificial intelligence, vol. 151, p. 197-204. Springer Berlin Heidelberg.  Consulté sur http://dx.doi.org/10.1007/978-3-642-28765-7_23

Luke S., Cioffi-Revilla C., Panait L., Sullivan K., Balan G. (2005). MASON: A Multiagent

Simulation Environment. Simulation, vol. 81, no 7, p. 517–527.  Consulté sur http://dx.doi.org/10.1177/0037549705058073

Lysenko M., D’Souza R. M. (2008). A Framework for Megascale Agent Based Model Simu- lations on Graphics Processing Units. Journal of Artificial Societies and Social Simulation, vol. 11, no 4, p. 10. Consulté sur http://jasss.soc.surrey.ac.uk/11/4/10.html

Michel F. (2014). Délégation  GPU des perceptions agents : intégration itérative et modulaire du GPGPU dans les simulations multi-agents. Application  sur la plate-forme TurtleKit 3. Revue d’Intelligence Artificielle, vol. 28, no 4, p. 485–510.  Consulté sur http://dx.doi.org/10.3166/ria.28.485-510

Michel F. (2015). Approches environnement-centrées pour la simulation  de systèmes multi- agents. pour un déplacement de la complexité des agents vers l’environnement. Habilitation à diriger  des recherches, Université  de Montpellier.

Michel F., Beurier G., Ferber J.  (2005, november).   The TurtleKit Simulation Platform: Ap- plication to Complex Systems. In A. Akono, E. Tonyé, A. Dipanda, K. Yétongnon (Eds.), Workshops Sessions of the Proceedings of the 1st International  Conference on Signal-Image Technology and Internet-Based  Systems, SITIS 2005, November 27 - December 1, 2005, Yaoundé, Cameroon, p. 122-128. IEEE.

Michel  F., Ferber J., Drogoul A. (2009, 3 June). Multi-Agent Systems and Simulation: a Survey From the Agents Community’s Perspective. In Adelinde Uhrmacher, Danny Weyns (Eds.), Multi-Agent Systems: Simulation and Applications, p. 3–52. CRC Press - Taylor & Francis. Consulté sur http://www.crcpress.com/product/isbn/9781420070231

North M., Tatara E., Collier N., Ozik J. (2007, November).  Visual  agent-based model develop- ment with Repast Simphony.  In Agent 2007 conference on complex interaction  and social emergence, p. 173-192. Argonne, IL, USA, Argonne National Laboratory.

Owens  J. D., Luebke D., Govindaraju N., Harris M., Kruger J., Lefohn A. E. et al.  (2007).

A Survey of General-Purpose Computation on Graphics Hardware. Computer Graphics Forum, vol. 26, no 1, p. 80-113.  Consulté sur http://www.ingentaconnect.com/content/bpl/ cgf/2007/00000026/00000001/art00009

Parry H., Bithell M. (2012). Large scale agent-based modelling:  A review and guidelines for model scaling. In A. J. Heppenstall,  A. T. Crooks, L. M. See, M. Batty (Eds.), Agent- based models of geographical  systems, p. 271-308. Springer Netherlands.   Consulté sur http://dx.doi.org/10.1007/978-90-481-8927-4_14

Payet D., Courdier R., Sébastien N., Ralambondrainy T. (2006). Environment  as support for simplification,  reuse and integration of processes in spatial MAS.  In Proceedings of the

2006 IEEE international conference on information reuse and integration, IRI - 2006: Heu- ristic systems engineering, september 16-18, 2006, waikoloa,  hawaii,  usa, p. 127-131. IEEE Systems, Man, and Cybernetics Society.

Resnick M. (1996). StarLogo: An Environment for Decentralized Modeling and Decentralized Thinking. In Conference companion on human factors in computing systems, p. 11-12.  New York, NY, USA, ACM. Consulté sur http://doi.acm.org/10.1145/257089.257095

Reynolds C. W. (1987). Flocks, Herds and Schools: A Distributed Behavioral Model. In Pro- ceedings of the 14th annual conference on computer graphics and interactive techniques, vol. 21, p. 25-34. New York, NY, USA, ACM.  Consulté sur http://doi.acm.org/10.1145/37401.37406

Ricci A., Piunti M., Viroli M.  (2011). Environment programming in multi-agent  systems: an artifact-based perspective. Autonomous Agents and Multi-Agent  Systems, vol. 23, no 2, p. 158-192. Consulté sur http://dx.doi.org/10.1007/s10458-010-9140-7

Richmond P., Walker D., Coakley S., Romano D. M. (2010). High performance cellular level agent-based simulation with FLAME for the GPU. Briefings in bioinformatics, vol. 11, no 3, p. 334-47. Consulté sur http://bib.oxfordjournals.org/content/11/3/334.short

Sano Y., Kadon Y., Fukuta N. (2014). A Performance Optimization  Support Framework for GPU-based Traffic Simulations with Negotiating Agents. In Proceedings of the 2014 se- venth international workshop on agent-based complex automated negotiations.

Sklar E. (2007). NetLogo, a Multi-agent Simulation Environment. Artificial Life, vol. 13, no 3, p. 303-311.

Vigueras G., Orduña J., Lozano M. (2010). A GPU-Based Multi-agent  System for Real-Time Simulations. In Y. Demazeau, F. Dignum,  J. Corchado, J. Pérez (Eds.), Advances in prac- tical applications of agents and multiagent systems, vol. 70, p. 15-24. Springer Berlin Hei- delberg. Consulté sur http://dx.doi.org/10.1007/978-3-642-12384-9_3

Viroli M., Omicini A., Ricci A.  (2006). Engineering MAS environment with artifacts. InD. Weyns, H. Dyke Parunak, F. Michel (Eds.), Environments for multi-agent systems, vol.3830, p. 62-77. Springer Berlin Heidelberg.

Weyns D., Dyke Parunak H., Michel F., Holvoet T., Ferber J. (2005). Environments for Mul- tiagent Systems State-of-the-Art and Research Challenges. In D. Weyns, H. Dyke Parunak, F. Michel (Eds.), Environments for multi-agent systems, vol. 3374, p. 1-47. Springer Berlin Heidelberg.  Consulté sur http://dx.doi.org/10.1007/978-3-540-32259-7_1

Weyns D., Holvoet T. (2005). On the Role of Environments in Multiagent Systems. In First international workshop, e4mas 2004, p. 127-141. Springer.

Weyns D., Michel F. (2015). Agent Environments for Multi-Agent Systems IV, 4th International Workshop, E4MAS 2014 - 10 Years Later, Paris, France, May 6, 2014, Revised Selected and Invited Papers (vol. 9068). Springer.