research-article

Cloning Agent-based Simulation on GPU

Authors:

Stephen John TurnerAuthors Info & Claims

SIGSIM PADS '15: Proceedings of the 3rd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

Pages 173 - 182

https://doi.org/10.1145/2769458.2769470

Published: 10 June 2015 Publication History

Abstract

Simulation cloning is an efficient way to analyze multiple configurations in a parameter exploration task. This paper presents a generic approach to perform incremental agent-based simulation cloning and discusses its implementation on GPU. Compared with the incremental cloning of parallel and distributed simulation (PADS), cloning agent-based simulation (ABS) has new challenges due to the unique way how ABS is executed. In this paper, to support incremental cloning, mechanisms for both actively and passively cloning agents are proposed. A scheme to maintain the correct context of each cloned ABS instance is developed. In addition, a strategy to restrain the propagation of passive cloning in order to maximize computation sharing amongst cloned ABS instances is also investigated. The implementation of our proposed approach on GPU supports concurrent execution of agents within each simulation instance as well as concurrent execution of multiple simulation instances. Performance of the proposed approach is evaluated and analyzed using a case study of an agent-based evacuation simulation on a NVIDIA Quadro 2000 GPU. Our experiment results demonstrate that cloning can significantly speed up the overall parameter exploration task. The proposed approach achieves 2.4 to 5.1 times speedup for parameter exploration tasks containing 8 to 125 simulation instances that evaluate different parameter configurations.

References

[1]

C. Alexopoulos. A comprehensive review of methods for simulation output analysis. In Proceedings of the 38th conference on Winter simulation, (Monterey, CA, USA, December 03-06, 2006), pages 168--178. IEEE, 2006.

Digital Library

[2]

A. Bestavros and B. Wang. Multi-version speculative concurrency control with delayed commit. Technical report, Boston University Computer Science Department, 1993.

Digital Library

[3]

B. Calvez and G. Hutzler. Parameter space exploration of agent-based models. In Proceedings of the 9th international conference on Knowledge-Based Intelligent Information and Engineering Systems, (Melbourne, Australia, September 14-16, 2005), pages 633--639. Springer, 2005.

Digital Library

[4]

D. Chen, S. J. Turner, W. Cai, B. P. Gan, and M. Y. H. Low. Incremental HLA-based distributed simulation cloning. In Proceedings of the 36th conference on Winter simulation, (Washington, DC, USA, December 5-8, 2004), pages 386--394. Winter Simulation Conference, 2004.

Digital Library

[5]

D. Chen, S. J. Turner, W. Cai, B. P. Gan, and M. Y. H. Low. Algorithms for HLA-based distributed simulation cloning. ACM Transactions on Modeling and Computer Simulation (TOMACS), 15(4):316--345, 2005.

Digital Library

[6]

D. Chen, S. J. Turner, B. P. Gan, and W. Cai. HLA-based distributed simulation cloning. In Proceedings of 8th IEEE International Symposium on Distributed Simulation and Real-Time Applications, (Budapest, Hungary, October 21-23, 2004), pages 244--247. IEEE, 2004.

Digital Library

[7]

D. Chen, S. J. Turner, B. P. Gan, W. Cai, and J. Wei. A decoupled federate architecture for distributed simulation cloning. In Proceedings of the 15th European Simulation Symposium, (Delft, the Netherlands, October 26-29, 2003), pages 131--140. SCS European Publishing House, 2003.

[8]

D. Chen, S. J. Turner, B. P. Gan, W. Cai, J. Wei, and N. Julka. Alternative solutions for distributed simulation cloning. Simulation, 79(5-6):299--315, 2003.

[9]

W. J. Davis. On-line simulation: Need and evolving research requirements. In Handbook of simulation, pages 465--516. Wiley-Interscience, 1998.

[10]

J. Decraene, M. Y.-H. Low, F. Zeng, S. Zhou, and W. Cai. Automated modeling and analysis of agent-based simulations using the CASE framework. In Proceedings of 11th International Conference on Control Automation Robotics & Vision (ICARCV) (Singapore, Singapore, December 7-10, 2010), pages 346--351. IEEE, 2010.

[11]

A. L. Espindola, D. Girardi, T. J. Penna, C. T. Bauch, A. S. Martinez, and B. C. Cabella. Exploration of the parameter space in an agent-based model of tuberculosis spread: emergence of drug resistance in developing vs developed countries. International Journal of Modern Physics C, 23(06):1--9, 2012.

[12]

P. W. Glynn and P. Heidelberger. Analysis of parallel replicated simulations under a completion time constraint. ACM Transactions on Modeling and Computer Simulation (TOMACS), 1(1):3--23, 1991.

Digital Library

[13]

A. P. Goldberg. Virtual time synchronization of replicated processes. In Proceedings of the 6th Workshop on Parallel and distributed simulation (Newport Beach, CA, USA, January 20-22, 1992), pages 107--116. SCS Simulation Series, 1992.

[14]

D. Helbing and P. Molnar. Social force model for pedestrian dynamics. Physical review E, 51(5):4282, 1995.

[15]

M. Hybinette and R. M. Fujimoto. Cloning parallel simulations. ACM Transactions on Modeling and Computer Simulation (TOMACS), 11(4):378--407, 2001.

Digital Library

[16]

G. Kunz, D. Schemmel, J. Gross, and K. Wehrle. Multi-level parallelism for time-and cost-efficient parallel discrete event simulation on gpus. In Proceedings of the 2012 ACM/IEEE/SCS 26th Workshop on Principles of Advanced and Distributed Simulation, (Zhangjiajie, China, July 15-19, 2012), pages 23--32. IEEE, 2012.

Digital Library

[17]

X. Li, W. Cai, and S. J. Turner. Efficient neighbor searching for agent-based simulation on GPU. In Proceedings of 18th IEEE International Symposium on Distributed Simulation and Real-Time Applications, (Toulouse, France, October 1-3, 2014), pages 87--96. IEEE/ACM, 2014.

Digital Library

[18]

S. Luke. The ECJ Owner's Manual. Technical report, ECJ Evolutionary Computation Library, George Mason University, 2010.

[19]

NVIDIA. NVIDIA CUDA programming guide. Technical report, http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html. {Online, last accessed: March 2015}.

[20]

H. Park and P. A. Fishwick. A GPU-based application framework supporting fast discrete-event simulation. Simulation, 86(10):613--628, 2009.

Digital Library

[21]

H. Park and P. A. Fishwick. An analysis of queuing network simulation using GPU-based hardware acceleration. ACM Transactions on Modeling and Computer Simulation (TOMACS), 21(3):1--22, 2011.

Digital Library

[22]

M. Steinberger, M. Kenzel, B. Kainz, and D. Schmalstieg. Scatteralloc: Massively parallel dynamic memory allocation for the GPU. In Proceedings of Innovative Parallel Computing, (San Jose, CA, USA, May 13-14, 2012), pages 1--10. IEEE, 2012.

[23]

W. Tang and Y. Yao. A GPU-based discrete event simulation kernel. Simulation, 89(11):1335--1354, 2013.

Digital Library

[24]

T. Terano. Exploring the vast parameter space of multi-agent based simulation. In Proceedings of the 2006 international conference on Multi-agent-based simulation (Hakodate, Japan, May 8-12, 2006), pages 1--14. Springer, 2006.

Digital Library

[25]

V. Volkov. Better performance at lower occupancy. In Proceedings of the GPU Technology Conference (San Jose, CA, USA, September 20-23, 2010), volume 10. NVIDIA, 2010.

[26]

J. Von Neumann. Probabilistic logics and the synthesis of reliable organisms from unreliable components. Automata studies, 34:43--98, 1956.

[27]

M. Wagner, W. Cai, and M. H. Lees. Emergence by strategy: flocking boids and their fitness in relation to model complexity. In Proceedings of the 2013 Winter Simulation Conference (Washington, DC, USA, December 8-11, 2013), pages 1479--1490. IEEE, 2013.

Digital Library

[28]

S. Widmer, D. Wodniok, N. Weber, and M. Goesele. Fast dynamic memory allocator for massively parallel architectures. In Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units, pages 120--126. ACM, 2013.

Digital Library

[29]

F. Zeng, J. Decraene, M. Y. H. Low, S. Zhou, and W. Cai. Evolving optimal and diversified military operational plans for computational red teaming. Systems Journal, 6(3):499--509, 2012.

Cited By

Xiao JAndelfinger PEckhoff DCai WKnoll A(2019)A Survey on Agent-based Simulation Using Hardware AcceleratorsACM Computing Surveys10.1145/329104851:6(1-35)Online publication date: 28-Jan-2019
https://dl.acm.org/doi/10.1145/3291048
Yoginath SPerumalla K(2018)Scalable Cloning on Large-Scale GPU Platforms with Application to Time-Stepped Simulations on GridsACM Transactions on Modeling and Computer Simulation10.1145/315866928:1(11-26)Online publication date: 31-Jan-2018
https://dl.acm.org/doi/10.1145/3158669
Li XCai WTurner S(2017)Cloning Agent-Based SimulationACM Transactions on Modeling and Computer Simulation10.1145/301352927:2(1-24)Online publication date: 27-May-2017
https://dl.acm.org/doi/10.1145/3013529

Index Terms

Cloning Agent-based Simulation on GPU
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Single instruction, multiple data
2. Computing methodologies
  1. Modeling and simulation
    1. Simulation types and techniques
      1. Massively parallel and high-performance simulations

Recommendations

Cloning Agent-Based Simulation
Special Issue on PADS 2015

Simulation cloning is an efficient way to analyze multiple configurations in a parameter exploration task. A simulation model usually contains a set of tunable parameters for exploring different configurations of a system. To evaluate different design ...
Efficient simulation of agent-based models on multi-GPU and multi-core clusters
SIMUTools '10: Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques

An effective latency-hiding mechanism is presented in the parallelization of agent-based model simulations (ABMS) with millions of agents. The mechanism is designed to accommodate the hierarchical organization as well as heterogeneity of current state-...
Efficient Neighbor Searching for Agent-Based Simulation on GPU
DS-RT '14: Proceedings of the 2014 IEEE/ACM 18th International Symposium on Distributed Simulation and Real Time Applications

This paper introduces a strategy to accelerate neighbor searching in agent-based simulations on GPU platforms. Because of their autonomous nature, agents can be processed by threads concurrently on GPU, and the overall simulation can be accelerated ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSIM PADS '15: Proceedings of the 3rd ACM SIGSIM Conference on Principles of Advanced Discrete Simulation

June 2015

300 pages

ISBN:9781450335836

DOI:10.1145/2769458

General Chair:
Simon J.E. Taylor
Brunel University London, UK
,
Program Chairs:
Navonil Mustafee
University of Exeter, UK
,
Young-Jun Son
University of Arizona, USA

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGSIM-PADS '15

Sponsor:

SIGSIM

SIGSIM-PADS '15: SIGSIM Principles of Advanced Discrete Simulation

June 10 - 12, 2015

London, United Kingdom

Acceptance Rates

SIGSIM PADS '15 Paper Acceptance Rate 35 of 60 submissions, 58%;

Overall Acceptance Rate 398 of 779 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
156
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xiao JAndelfinger PEckhoff DCai WKnoll A(2019)A Survey on Agent-based Simulation Using Hardware AcceleratorsACM Computing Surveys10.1145/329104851:6(1-35)Online publication date: 28-Jan-2019
https://dl.acm.org/doi/10.1145/3291048
Yoginath SPerumalla K(2018)Scalable Cloning on Large-Scale GPU Platforms with Application to Time-Stepped Simulations on GridsACM Transactions on Modeling and Computer Simulation10.1145/315866928:1(11-26)Online publication date: 31-Jan-2018
https://dl.acm.org/doi/10.1145/3158669
Li XCai WTurner S(2017)Cloning Agent-Based SimulationACM Transactions on Modeling and Computer Simulation10.1145/301352927:2(1-24)Online publication date: 27-May-2017
https://dl.acm.org/doi/10.1145/3013529

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten