Parallel simulation and optimization of CUDA-based real-time huge crowd behavior

doi:10.3724/SP.J.1087.2012.02466

Journal of Computer Applications ›› 2012, Vol. 32 ›› Issue (09): 2466-2469.DOI: 10.3724/SP.J.1087.2012.02466

• Network and distributed techno • Previous Articles Next Articles

Parallel simulation and optimization of CUDA-based real-time huge crowd behavior

HE Yi-hui^*,YE Chen,LIU Zhi-zhong,PENG Wei

Institute of Command Automation,PLA University of Science and Technology,Nanjing Jiangsu 210007,China

Received:2012-02-24 Revised:2012-04-18 Online:2012-09-01 Published:2012-09-01
Contact: Yi-Hui HE

基于CUDA的大规模群体行为实时仿真并行实现及优化

贺毅辉^*,叶晨,刘志忠,彭伟

解放军理工大学指挥自动化学院,南京 210007

通讯作者: 贺毅辉
作者简介:贺毅辉(1973-),男,河北辛集人,教授,主要研究方向:作战仿真、决策支持; 叶晨(1984-),男,江苏无锡人,工程师,硕士研究生,主要研究方向:系统集成与优化; 刘志忠(1980-),男,江西吉安人,讲师,博士,主要研究方向:面向服务计算、人工智能; 彭伟(1982-),男,湖南常德人,讲师,硕士,主要研究方向:作战仿真、系统集成。
基金资助:
江苏省自然科学基金资助项目(BK2010130,BK2011120)

Abstract

Abstract: That the individuals search relevant objects from the environment may cause high time complexity during the crowd simulation. If the crowd should be simulated in real-time, the time complexity of the model needs reducing and the computing capability of the simulation platform needs enhancing. In this paper, the Biods model was studied as a typical case and a solution of how to parallelize and optimize the real-time huge crowd simulation based on Compute Unified Device Architecture (CUDA) was presented. Each individual was correspondent to a logical Graphic Processing Unit (GPU) thread. By discretizing simulation environment, the efficiency of searching the relevant individuals was improved. The individual information was organized into an array with the spatial locality by parallel radix sort in order to improve the utilization of the GPU memory bandwidth. The experiment verifies the solution presented here has improved number of simulation individuals up to about 7.3 times as CPU solution.

Key words: huge crowd behavior, Compute Unified Device Architecture (CUDA), parallel computing, real-time simulation

摘要： 群体仿真中个体从环境中查找相关对象时会导致较高的时间复杂度。要使大规模群体能够实时仿真,必须降低模型运算的时间复杂度或者提高计算平台的能力。通过对Biods模型为典型案例进行研究,提出一种基于统一计算架构(CUDA)的大规模群体行为实时仿真并行实现及优化的方法。实现中将个体与GPU逻辑线程一一对应,通过将仿真环境离散化来提高相关个体查找的效率,通过并行化基数排序法将个体信息组织成具有空间局部性的数组,提高图形处理器(GPU)内存带宽的利用率。通过实验验证了该方法将仿真个体的数量提升到CPU方法的约7.3倍。

关键词: 大规模群体行为, 统一计算架构, 并行计算, 实时仿真

CLC Number:

TP391.9

HE Yi-hui,YE Chen,LIU Zhi-zhong,PENG Wei. Parallel simulation and optimization of CUDA-based real-time huge crowd behavior[J]. Journal of Computer Applications, 2012, 32(09): 2466-2469.

贺毅辉叶晨刘志忠彭伟. 基于CUDA的大规模群体行为实时仿真并行实现及优化[J]. 计算机应用, 2012, 32(09): 2466-2469.

References

[1]MUSSE S R,THALMANN D.A hierarchical model for real time simulation of virtual human crowds[J].IEEE Transactions on Visualization and Computer Graphics,2001,7(2):152-164.
[2]TESCHNER M,HEIDELBERGER B.Optimized spatial hashing for collision detection of deformable objects[C]// Proceedings of Vision,Modeling and Visualization.München,Germany:[s.n],2003:47-54.
[3]SHAO W,TERZOPOULOS D.Autonomous pedestrians[C]// SCA'05:Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer animation.New York:ACM Press,2005:19-28.
[4]REYNOLDS C.Big fast crowds on PS3[C]// Sandbox'06:Proceedings of the 2006 ACM SIGGRAPH Symposium on Videogames.New York:ACM Press,2006:113-121.
[5]QUINN M J,METOYER R A.Parallel implementation of the social forces model[C]// Proceedings of the 2nd International Conference in Pedestrian and Evacuation Dynamics.London:CMS Press,2003:63-74.
[6]CHIARA R D,ERRA U.Massive simulation using GPU of a distributed behavioral model of a flock with obstacle avoidance[C]// Proceedings of Vision,Modeling and Visualization.Stanford:[s.n.],2004:233-240.
[7]RICHMOND P,DANIELA R.High performance cellular level Agent-based simulation with FLAME for the GPU[J].Briefings in Bioinformatics,2010,11(3):334-347.
[8]RICHMOND P,ROMANO D.Agent-based GPU,a real-time 3D simulation and interactive visualisation framework for massive Agent-based modelling on the GPU[C]// Proceedings International Workshop on Super Visualization.New York:ACM Press,2008:185-192.
[9]MAO T,JIANG H.Parallelizing continuum crowds[C]// Proceedings of the 17th ACM Symposium on Virtual Reality Software and Technology.New York:ACM Press,2010:231-234.
[10]NVIDIA.CUDA programming guide:V3.0[EB/OL].[2010-10-10].http://www.nvidia.com/object/cuda_home.html.
[11]KIPFER P,SEGAL M.Uber-flow:A GPU-based particle engine[C]// EGGH-04:Proceedings of ACM SIGGRAPH/Euro Graphics Workshop on Graphics Hardware.New York:ACM Press,2004:115-122.
[12]GRAND S L.Broad-phase collision detection with CUDA[M].Upper Saddle River:Addison Wesley,2007.
[13]SIMON G.CUDA particles[EB/OL].[2010-10-10].http://www.mendeley.com/research/cuda-particles/.
[14]SANDERS J,KANDROT E.CUDA by example:An introduction to general-purpose GPU programming[M].Upper Saddle River:Addison Wesley,2010.
[15]STATISH N,HARRIS M,GARLAND M.Designing efficient sorting algorithms for manycore GPUs[C]// IPDPS'09:Proceedings of the 2009 IEEE International Symposium on Parallel & Distributed Processing.Washington,DC:IEEE Computer Society,2009:1-10.
[16]HARRIS M,SENGUPTA S,OWENS J D.Parallel prefix sum (Scan) with CUDA[M].Upper Saddle River:Addison Wesley,2007.
[17]SENGUPTA S,HARRIS M,ZHANG Y,et al.Scan primitives for GPU computing [C]// GH'07: Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware.Aire-la-Ville Switzerland:Eurographics Association,2007:97-106.

Parallel simulation and optimization of CUDA-based real-time huge crowd behavior

基于CUDA的大规模群体行为实时仿真并行实现及优化

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	Runlian ZHANG, Mi ZHANG, Xiaonian WU, Rui SHU. Differential property evaluation method based on GPU for large-state cryptographic S-boxes [J]. Journal of Computer Applications, 2024, 44(9): 2785-2790.
[2]	Qian LIU, Yangming ZHANG, Dingsheng WAN. Parallel computing algorithm of grid-based distributed Xin’anjiang hydrological model [J]. Journal of Computer Applications, 2023, 43(11): 3327-3333.
[3]	JIANG Songyan, LIAO Xiaojuan, CHEN Guangzhu. Optimal task scheduling method based on satisfiability modulo theory for multiple processors with communication delay [J]. Journal of Computer Applications, 2023, 43(1): 185-191.
[4]	Jingwen CAI, Yongzhuang WEI, Zhenghong LIU. GPU-based method for evaluating algebraic properties of cryptographic S-boxes [J]. Journal of Computer Applications, 2022, 42(9): 2750-2756.
[5]	Xinyuan QIU, Zecong YE, Xiaolong CUI, Zhiqiang GAO. Survey of communication overhead of federated learning [J]. Journal of Computer Applications, 2022, 42(2): 333-342.
[6]	Qidi XU, Zhenghong LIU, Lin ZHENG. Low density parity check code decoding acceleration technology based on GPU [J]. Journal of Computer Applications, 2022, 42(12): 3841-3846.
[7]	XIE Wenbo, WEI Yongzhuang, LIU Zhenghong. Parallel implementation and analysis of SKINNY encryption algorithm using CUDA [J]. Journal of Computer Applications, 2021, 41(4): 1136-1141.
[8]	YANG Xianfeng, GUI Hongjun, FU Chunchang. F-X domain predictive filtering parallel algorithm based on compute unified device architecture [J]. Journal of Computer Applications, 2021, 41(2): 486-491.
[9]	Zhiyang ZENG, Yan CHEN, Ke WANG. Design and implementation of parallel genetic algorithm for cutting stock of circular parts [J]. Journal of Computer Applications, 2020, 40(2): 392-397.
[10]	CUI Yixin, CHEN Xiaodong. Spark framework based optimized large-scale spectral clustering parallel algorithm [J]. Journal of Computer Applications, 2020, 40(1): 168-172.
[11]	HE Xi, WU Yantao, DI Zhenwei, CHEN Jia. GPU-based morphological reconstruction system [J]. Journal of Computer Applications, 2019, 39(7): 2008-2013.
[12]	SHA Zongxuan, XUE Fei, ZHU Jie. Scheduling strategy of cloud robots based on parallel reinforcement learning [J]. Journal of Computer Applications, 2019, 39(2): 501-508.
[13]	WANG Peng, ZHOU Yan. MPI big data processing for high performance applications [J]. Journal of Computer Applications, 2018, 38(12): 3496-3499.
[14]	HAN Litao, LIU Hailong, KONG Qiaoli, YANG Fanlin. Parallel algorithm for hillshading under multi-core computing environment [J]. Journal of Computer Applications, 2017, 37(7): 1911-1915.
[15]	JIAO Jiafeng, LI Yun. Review of typical machine learning platforms for big data [J]. Journal of Computer Applications, 2017, 37(11): 3039-3047.