The computing capabilities of current multi-core and many-core architectures have been used in crowd simulations for both enhancing crowd rendering and simulating continuum crowds. However, improving the scalability of crowd simulation systems by exploiting the inherent parallelism of these architectures is still an open issue. In this paper, we propose different parallelization strategies for the collision check procedure that takes place in agent-based simulations. These strategies are designed for exploiting the parallelism in both multi-core and many-core architectures like graphic processing units (GPUs). As for the many-core implementations, we analyse the bottlenecks of a previous GPU version of the collision check algorithm, proposing a new GPU version that removes the bottlenecks detected. In order to fairly compare the GPU with the multi-core implementations, we propose a parallel CPU version that uses read--copy update (RCU), a new synchronization method which significantly improves performance. We perform a comparison study of these different implementations. On the one hand, the comparison study shows the first performance evaluation of RCU in a real user-space application with complex data structures. On the other hand, the comparison shows that the GPU greatly accelerates the collision test with respect to any other implementation optimized for multi-core CPUs. In addition, we analyse the efficiency of the different implementations taking into account the theoretical performance and power consumption of each platform. The evaluation results show that the GPU-based implementation consumes less energy and provides a minimum speedup of 45× with respect to any of the CPU-based implementations. Since interactivity is a hard constraint in crowd simulations, this acceleration of the collision check process represents a significant improvement in the overall system throughput and response time. Therefore, the simulations are significantly accelerated, and the system throughput and scalability are improved.
NVIDIA Corporation (2008). Particles Example. NVIDIA CUDA SDK.
2.
BleiweissA (2008) GPU accelerated pathfinding. In: 23rd SIGGRAPH/EUROGRAPHICS symposium on graphics hardware (GH ‘08), Sarajevo, Bosnia, 20–21 June 2008, pp. 65–74. Aire-la-Ville: Eurographics Association.
3.
CourtyNMusseSR (2005) Simulation of large crowds in emergency situations including gaseous phenomena. In: computer graphics international (CGI ‘05), New York, USA, 22–24 June 2005, pp. 206–212. Piscataway: IEEE Press.
4.
DesnoyersM (2009) Userspace RCU library: What linear multiprocessor scalability means for your application. In: linux plumbers conference, Portland, Oregon, USA, 23--25 September 2009.
5.
ErraUFrolaBScaranoVCouzinI (2009) An efficient GPU implementation for large scale individual-based simulation of collective behavior. In: international workshop on high performance computational systems biology (HiBi ‘09), Trento, Italy, 14--16th October 2009, pp. 51–58. USA, IEEE.
6.
GajinovVZyulkyarovFUnsalOSCristalAAyguadeEHarrisT (2009) Quaketm: parallelizing a complex sequential application using transactional memory. In: 23rd international conference on supercomputing (ICS ‘09), New York, USA, 8–12 June 2009, pp. 126–135. New York: ACM Press.
7.
GoswamiPSchlegelPSolenthalerBPajarolaR (2010) Interactive SPH simulation and rendering on the GPU. In: SIGGRAPH/EUROGRAPHICS symposium on computer animation (SCA ‘10), Madrid, Spain, 2–4 July 2010, pp. 55–64. Aire-la-Ville: Eurographics Association.
8.
GuySJChhuganiJKimCSatishNLinMManochaD (2009) Clearpath: highly parallel collision avoidance for multi-agent simulation. In: SIGGRAPH/EUROGRAPHICS symposium on computer animation (SCA ‘09), New Orleans, USA, 1–2 August 2009, pp. 177–187. New York: ACM Press.
9.
HaradaTTanakaMKoshizukaSKawaguchiY (2007) Real-time rigid body simulation using GPUs. IPSJ SIG Technical Reports13: 79--84.
10.
HartTEMcKenneyPEBrownAD (2006) Making lockless synchronization fast: Performance implications of memory reclamation. In: 20th IEEE international parallel and distributed processing symposium, Rhodes, Greece, 25–29 April 2006, Piscataway: IEEE Press.
11.
HelbingDFarkasIVicsekT (2000) Simulating dynamical features of escape panic. Nature407: 487--490.
12.
HeraultABilottaGDalrympleRA (2010) SPH on GPU with CUDA. Journal of Hydraulic Research48: 74--79.
13.
KimDHeoJPHuhJKimJYoonSE (2009) HPCCD: Hybrid parallel continuous collision detection using CPUs and GPUs. Computer Graphics Forum28(7): 1791--1800.
14.
LattaL (2004) Building a million particle system. In: game developers conference (GDC ‘04), San Jose, California, USA, 22–26 March 2004.
15.
LauterbachCGarlandMSenguptaSLuebkeDManochaD (2009) Fast BVH construction on GPUs. Computer Graphics Forum28(2): 375--384.
16.
LauterbachCMoQManochaD (2010) Gproximity: Hierarchical GPU-based operations for collision and distance queries. Computer Graphics Forum29(2): 419--428.
17.
LozanoMMorilloPOrduñaJMCaveroVViguerasG (2009) A new system architecture for crowd simulation. Journal of Network and Computer Applications32(2): 474--482.
18.
LysenkoMD'SouzaRM (2008) A framework for megascale agent based model simulations on graphics processing units. Journal of Artificial Societies and Social Simulation11(4): 10.
19.
McKenneyPESlingwineJD (1998) Read-copy update: Using execution history to solve concurrency problems. In: 18th international conference on parallel and distributed computing systems (PDCS ‘98), Las Vegas, USA, 12--14 September 2005, pp. 509–518. IASTED Acta Press.
[Owens et∼al.(2007)Owens, John, Luebke, David, Govindaraju, Naga, Harris, Mark, Kruger, Jens, Lefohn, Aaron, Purcell, and Timothy]OwensJDLuebkeDGovindarajuNHarrisMKrügerJLefohnA. (2007) A survey of general-purpose computation on graphics hardware. Computer Graphics Forum26(1): 80--113.
22.
[Perumalla and Aaby(2008)]PerumallaKSAabyBG (2008) Data parallel execution challenges and runtime performance of agent simulations on GPUs. In: 2008 spring simulation multiconference (SpringSim ‘08), Ottawa, Canada, 14–17 April 2008, pp. 116–123. New York: ACM Press.
23.
[Peter et∼al.(2004)Peter, Mark, and Rudiger]PeterKMarkSRudigerW (2004) Uberflow: a GPU-based particle engine. In: 19th SIGGRAPH/EUROGRAPHICS symposium on graphics hardware (GH ‘04), Grenoble, France, 29–30 August 2004, pp. 115–112. New York: ACM Press.
24.
[Pratas et∼al.(2009)Pratas, Trancoso, Stamatakis, and Sousa]PratasFTrancosoPStamatakisASousaL (2009) Fine-grain parallelism using multi-core, Cell/BE, and GPU systems: Accelerating the phylogenetic likelihood function. In: 38th international conference on parallel processing (ICPP ‘09), Vienna, Austria, 22–25 September 2009, pp. 9–17. Piscataway: IEEE Press.
25.
[Reynolds(2006)]ReynoldsC (2006) Big fast crowds on PS3. In: 1st ACM/SIGGRAPH symposium on videogames, Boston, MA, USA, 29–30 July 2006, pp. 113–121. New York: ACM Press.
26.
[Reynolds(1987)]ReynoldsCW (1987) Flocks, herds and schools: A distributed behavioral model. SIGGRAPH Computer Graphics21(4): 25--34.
27.
[Satish et∼al.(2009)Satish, Harris, and Garland]SatishNHarrisMGarlandM (2009) Designing efficient sorting algorithms for manycore GPUs. In: 2009 IEEE international symposium on parallel and distributed processing (IPDPS ‘09), Rome, Italy, 23–29 May 2009, pp. 1–10. Piscataway: IEEE Press.
28.
[Sundell and Tsigas(2008)]SundellHTsigasP (2008) Lock-free deques and doubly linked lists. Journal of Parallel and Distributed Computing68(7): 1008--1020.
29.
[Teschner et∼al.(2003)Teschner, Heidelberger, Mueller, Pomeranets, and Gross]TeschnerMHeidelbergerBMuellerMPomeranetsDGrossM (2003) Optimized spatial hashing for collision detection of deformable objects. In: vision, modeling, and visualization conference (VMV ‘03), München, Germany, AKA Gmbh, 19–21 November 2003, pp. 47–54. Eurographics Association.
30.
[van∼den Berg et∼al.(2008)van∼den Berg, Lin, and Manocha]van den BergJLinMCManochaD (2008) Reciprocal velocity obstacles for real-time multi-agent navigation. In: IEEE international conference on robotics and automation (ICRA ‘08), Pasadena, California, USA, 19–23 May 2008, pp. 1928–1935. Piscataway: IEEE Press.
31.
[Vigueras et∼al.(2010)Vigueras, Lozano, Ordu na, and Grimaldo]ViguerasGLozanoMOrduñaJMGrimaldoF (2010 a ) A comparative study of partitioning methods for crowd simulations. Journal of Applied Soft Computing10(1): 225--235.
32.
[Vigueras et∼al.(2008)Vigueras, Lozano, Perez, and Ordu na]ViguerasGLozanoMPerezCOrduñaJ (2008) A scalable architecture for crowd simulation: Implementing a parallel action server. In: 37th international conference on parallel processing (ICPP ‘08), Portlan, Oregon, USA, 8–12 September 2008,pp. 430–437. Los Alamitos, USA: IEEE Press.
33.
[Vigueras et∼al.(2010)Vigueras, Ordu na, and Lozano]ViguerasGOrduñaJLozanoM (2010 b ) A GPU-based multi-agent system for real-time simulations. In: 8th international conference on practical applications of agents and multiagent systems (PAAMS ‘10), Salamanca, Spain, 26--28 April 2010, vol. 70, pp. 15--24. New York: Springer.
34.
[Vigueras et∼al.(2011)Vigueras, Ordu na, Lozano, and Chrysanthou]ViguerasGOrduñaJMLozanoMChrysanthouY (2011) A distributed visualization system for crowd simulation. Integrated Computer-Aided Engineering18(4): 1008--1020.
35.
[Vigueras et∼al.(2010)Vigueras, Ordu na, Lozano, Cecilia, and Garc]ViguerasGOrduñaJMLozanoMCeciliaJMGarcíaJM (2010 c) Improving the GPU-based collision check procedure for distributed crowd simulations. In: 19th international conference on parallel architectures and compilations techniques (PACT ‘10), Vienna, Austria, 11–15 September 2010.
36.
[Xu et∼al. (2009) Xu, R.∼Kirk, and Jenkins]XuCRKirkSJenkinsS (2009) Tiling for performance tuning on different models of GPUs. In: 2nd international symposium on information science and engineering (ISISE ‘09), Shanghai, China, 26–28 December 2009, pp. 500–504. Washington, USA: IEEE Computer Society.
37.
[Zhou et∼al. (2008) Zhou, Hou, Wang, and Guo]ZhouKHouQWangRGuoB (2008) Real-time KD-tree construction on graphics hardware. ACM Transactions on Graphics27(5): 1--11.
38.
[Zyulkyarov et∼al. (2009) Zyulkyarov, Gajinov, Unsal, Cristal, Ayguadà Harris, and Valero]ZyulkyarovFGajinovVUnsalOSCristalAAyguadéEHarrisT. (2009) Atomic quake: using transactional memory in an interactive multiplayer game server. In: 14th ACM/SIGPLAN symposium on principles and practice of parallel programming (PPoPP ‘09), Raleigh, North Carolina, USA, 14–18 February 2009, pp. 25–34. New York: ACM Press.
