Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Programmable graphics processing units (GPUs) have emerged as excellent computational platforms for certain general-purpose applications. The data parallel execution capabilities of GPUs specifically point to the potential for effective use in simulations of agent-based models (ABM). In this paper, the computational efficiency of ABM simulation on GPUs is evaluated on representative ABM benchmarks. The runtime speed of GPU-based models is compared to that of traditional CPU-based implementation, and also to that of equivalent models in traditional ABM toolkits (Repast and NetLogo). As expected, it is observed that, GPU-based ABM execution affords excellent speedup on simple models, with better speedup on models exhibiting good locality and fair amount of computation per memory element. Execution is two to three orders of magnitude faster with a GPU than with leading ABM toolkits, but at the cost of decrease in modularity, ease of programmability and reusability. At a more fundamental level, however, the data parallel paradigm is found to be somewhat at odds with traditional model-specification approaches for ABM. Effective use of data parallel execution, in general, seems to require resolution of modeling and execution challenges. Some of the challenges are identified and related solution approaches are described.

REFERENCES

• 1: Michael J. North , Charles M. Macal, Managing Business Complexity: Discovering Strategic Solutions with Agent-Based Modeling and Simulation, Oxford University Press, Inc., New York, NY, 2007
• 2: GPGPU. General Purpose Computation Using Graphics Hardware. 2005; http://www.gpgpu.org.
• 3: Matt Pharr , Randima Fernando, GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation (Gpu Gems), Addison-Wesley Professional, 2005
• 4: Ian Buck , Tim Foley , Daniel Horn , Jeremy Sugerman , Kayvon Fatahalian , Mike Houston , Pat Hanrahan, Brook for GPUs: stream computing on graphics hardware, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 5: Owens, J. D., et al. A Survey of General-Purpose Computation on Graphics Hardware. in Eurographics. 2005.
• 6: Intel-Corporation. Intel Multi-core Technology. 2007; http://www.intel.com/multi-core.
• 7: Top 500 Supercomputing Sites. 2007; http://top500.org.
• 8: N. Courty , S. R. Musse, Simulation of large crowds in emergency situations including gaseous phenomena, Proceedings of the Computer Graphics International 2005, p.206-212, June 02-04, 2005
• 9: Reynolds, C. Big Fast Crowds on PS3. 2006; www.research.scea.com/pscrowd.
• 10: Tomov, S., et al., Benchmarking and Implementation of Probability-based Simulations on Programmable Graphics Cards. Computers and Graphics, 2005. 29(1).
• 11: Walter, B., et al. UAV Swarm Control: Calculating Digital Phermone Fields with the GPU. in IITSEC. 2005.
• 12: Verdesca, M., et al. Using Graphics Processor Units to Accelerate OneSAF: A Case Study in Technology Transition. in IITSEC. 2005.
• 13: Moya, L. and A. Tolk, Towards A Taxonomy of Agents and Multi-Agent Systems, in Agent-Directed Simulation Symposium. 2007, ACM: Norfolk, VA, USA.
• 14: Neumann, R. and F. Strack, The Automatic Transfer of Mood between Persons. Journal of Personality and Social Psychology, 2000. 79(2): p. 211--223.
• 15: Hess, J. D., J. J. Kacen, and J. Kim, Mood-management Dynamics: The Interrelationship between Moods and Behaviors. British Journal of Mathematical and Statistical Psychology, 2006. 59(2): p. 347--378.
• 16: Gardner, M., Mathematical Games: The fantastic combinations of John Conway's new solitaire game "Life", in Scientific American. 1970. p. 120--123.
• 17: Schelling, T., Micromotives and Macrobehavior. 1978: W. W. Norton
• 18: Michael J. North , Nicholson T. Collier , Jerry R. Vos, Experiences creating three implementations of the repast agent modeling toolkit, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.16 n.1, p.1-25, January 2006 [doi>10.1145/1122012.1122013]
• 19: Wilensky, U., NetLogo. 1999, Center for Connected Learning and Computer-Based Modeling, Northwestern University: Evanston, IL.
• 20: Randima Fernando , Mark J. Kilgard, The Cg Tutorial: The Definitive Guide to Programmable Real-Time Graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2003
• 21: Kalyan S. Perumalla, Discrete-event Execution Alternatives on General Purpose Graphical Processing Units (GPGPUs), Proceedings of the 20th Workshop on Principles of Advanced and Distributed Simulation, p.74-81, May 24-26, 2006 [doi>10.1109/PADS.2006.15]
• 22: NVIDIA. NVIDIA CUDA. 2007; http://developer.nvidia.com/cuda.
• 23: Shubhabrata Sengupta , Mark Harris , Yao Zhang , John D. Owens, Scan primitives for GPU computing, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, August 04-05, 2007, San Diego, California
• 24: Epstein, J., Modeling Civil Violence: An Agent-based Computational Approach. PNAS, 2002. 99(3): p. 7243--7250.
• 25: Nutaro, J., Parallel Discrete Event Simulation with Application to Continuous Systems, in Department of Electrical and Computer Engineering. 2003, University of Arizona: Tucson, AZ. p. 182.
• 26: Perumalla, K. S., Model Execution, in Handbook of Dynamic System Modeling. 2007, CRC Press.
• 27: Richard M. Fujimoto, Parallel and Distribution Simulation Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 28: Kalyan S. Perumalla, Parallel and distributed simulation: traditional techniques and recent advances, Proceedings of the 38th conference on Winter simulation, December 03-06, 2006, Monterey, California

INDEX TERMS

Keywords:
agent-based simulation, emergent behavior, graphical processing units, large-scale simulation, parallel simulation