Using common graphics hardware for multi-agent traffic simulation with CUDA

ABSTRACT

Today's graphics processing units (GPU) have tremendous resources when it comes to raw computing power. The simulation of large groups of agents in transport simulation has a huge demand of computation time. Therefore it seems reasonable to try to harvest this computing power for traffic simulation. Unfortunately simulating a network of traffic is inherently connected with random memory access. This is not a domain that the SIMD (single instruction, multiple data) architecture of GPUs is known to work well with. In this paper the authors will try to achieve a speedup by computing multi-agent traffic simulations on the graphics device using NVIDIAs CUDA framework.

REFERENCES

• 1: ATI FireStream www page. Firestream: DAAMIT GPGPU framework, accessed 08/2008.
• 2: B. Bustos, O. Deussen, S. Hiller, and D. Keim. A graphics hardware accelerated algorithm for nearest neighbor search, 2006.
• 3: N. Cetin. Large-scale parallel graph-based simulations. Master's thesis, Swiss Federal Institute of Technology (ETH) Zürich, Switzerland, 2005.
• 4: N. Cetin, A. Burri, and K. Nagel. Parallel queue model approach to traffic microsimulations. In In Proceedings of Swiss Transportation Research Conference, 2002.
• 5: Shuai Che , Michael Boyer , Jiayuan Meng , David Tarjan , Jeremy W. Sheaffer , Kevin Skadron, A performance study of general-purpose applications on graphics processors using CUDA, Journal of Parallel and Distributed Computing, v.68 n.10, p.1370-1380, October, 2008 [doi>10.1016/j.jpdc.2008.05.014]
• 6: R. D. Chiara, U. Erra, V. Scarano, and M. Tatafiore. Massive simulation using GPU of a distributed behavioral model of a flock with obstacle avoidance. In B. Girod, M. A. Magnor, and H.-P. Seidel, editors, VMV, pages 233--240. Aka GmbH, 2004.
• 7: CUDA www page. CUDA: NVIDIA GPGPU framework, accessed 08/2008.
• 8: R. M. D'Souza, M. Lysenko, and K. Rahmani. Sugarscape on steroids: simulating over a million agents at interactive rates. In Proceedings of Agent2007 conference, Chicago, IL., 2007.
• 9: DYNAMIT/MITSIM www page. http://mit.edu/its, accessed 2008.
• 10: E. Elsen, V. Vishal, M. Houston, V. Pande, P. Hanrahan, and E. Darve. N-body simulations on GPUs, Jun 2007.
• 11: T. Hamada and T. Iitaka. The chamomile scheme: An optimized algorithm for n-body simulations on programmable graphics processing units, Mar 2007.
• 12: P. Harish and P. J. Narayanan. Accelerating large graph algorithms on the GPU using CUDA. In S. Aluru, M. Parashar, R. Badrinath, and V. K. Prasanna, editors, HiPC, volume 4873 of Lecture Notes in Computer Science, pages 197--208. Springer, 2007.
• 13: M. Harris. CUDA workshop pre-ISC2008, dresden, Juni 2008.
• 14: Mark J. Harris , Greg Coombe , Thorsten Scheuermann , Anselmo Lastra, Physically-based visual simulation on graphics hardware, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1198555.1198791]
• 15: Bingsheng He , Ke Yang , Rui Fang , Mian Lu , Naga Govindaraju , Qiong Luo , Pedro Sander, Relational joins on graphics processors, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376670]
• 16: K. Hegeman, N. A. Carr, and G. S. P. Miller. Particle-based fluid simulation on the GPU. In V. N. Alexandrov, D. G. van Albada, Peter, and J. Dongarra, editors, International Conference on Computational Science (4), volume 3994 of Lecture Notes in Computer Science, pages 228--235, 2006.
• 17: Jens Krüger , Rüdiger Westermann, Linear algebra operators for GPU implementation of numerical algorithms, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 18: W. Liu, B. Schmidt, G. Voss, and W. Müller-Wittig. Molecular dynamics simulations on commodity GPUs with CUDA. pages 185--196. 2007.
• 19: P. Micikevicius. General parallel computation on commodity graphics hardware: Case study with the all-pairs shortest paths problem. In H. R. Arabnia, editor, PDPTA, pages 1359--1365. CSREA Press, 2004.
• 20: Kalyan S. Perumalla, Efficient Execution on GPUs of Field-Based Vehicular Mobility Models, Proceedings of the 22nd Workshop on Principles of Advanced and Distributed Simulation, p.154, June 03-06, 2008 [doi>10.1109/PADS.2008.36]
• 21: Kalyan S. Perumalla , Brandon G. Aaby, Data parallel execution challenges and runtime performance of agent simulations on GPUs, Proceedings of the 2008 Spring simulation multiconference, April 14-17, 2008, Ottawa, Canada
• 22: B. Raney and K. Nagel. An improved framework for large-scale multi-agent simulations of travel behaviour. In P. Rietveld, B. Jourquin, and K. Westin, editors, Towards better performing European Transportation Systems, page 42. Routledge, London, 2006.
• 23: D. Robilliard, V. Marion-Poty, and C. Fonlupt. Population parallel gp on the G80 GPU. In EuroGP, pages 98--109, 2008.
• 24: M. Schatz, C. Trapnell, A. Delcher, and A. Varshney. High-throughput sequence alignment using graphics processing units. BMC Bioinformatics, 8(1), 2007.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Parallel

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures