基于GPU的一类地理多智能体系统并行仿真研究

系统仿真学报 ›› 2015, Vol. 27 ›› Issue (2): 396-403.

基于GPU的一类地理多智能体系统并行仿真研究

赵元^1,2,3,4, 程家昌², 王璐^2,3,4, 胡月明^2,3,4

1.广东工贸职业技术学院,广州市 510510;
2.华南农业大学信息学院,广州市 510642;
3.国土资源部建设用地再开发重点实验室,广州市 510642;
4.广东省土地利用与整治重点实验室,广州市 510642

收稿日期:2014-01-24 修回日期:2014-04-13 发布日期:2020-09-02
作者简介:赵元(1977-),男,江苏徐州,博士,研究方向为地理信息建模、地理仿真;胡月明(通信作者1964-),男,湖南益阳,博士,教授,研究方向为地理信息系统、土地信息化。
基金资助:
国家自然科学基金委-广东联合基金(U1301253)

GPU-Accelerated Simulation for Class of Multi-Agent Based Models

Zhao Yuan^1,2,3,4, Cheng Jiachang², Wang Lu^2,3,4, Hu Yueming^2,3,4

1. Guangdong College of Industry & Commerce, Guangzhou 510510, China;
2. College of Informatics, South China Agricultural University, Guangzhou 510642, China;
3. Guangdong Province Key Laboratory of Land Use and Consolidation, Guangzhou 510642, China;
4. Key Laboratory of the Ministry of Land and Resources for Construction Land Transformation, Guangzhou 510642, China

Received:2014-01-24 Revised:2014-04-13 Published:2020-09-02

摘要/Abstract

摘要： 针对当前地理多智能体建模存在着计算成本高、配置复杂、运算加速性能不高的问题,以杜能模型为例,提出基于GPU并行技术的一类地理多智能体仿真与优化方法。通过构建空间索引网格的方法,动态维持智能体与空间索引网格的关联关系,提高地理多智能体系统的仿真运行效率。研究结果表明：采用GPU并行技术,能够使多智能体系统的运行性能得到明显提升,对开展大规模数据下的空间系统多智能体仿真建模具有重要意义。

关键词: 空间索引网格, 多智能体系统, 并行计算, GPU

Abstract: A parallel agent-based model of Von Thünen Model was proposed driven by graphics processing units (GPUs). The Von Thünen Model often involved the simulation of large numbers of geographically located individual decision-makers and a massive number of individual-level interactions. This simulation required substantial computational power. GPU-enabled computing resources provided a massively parallel processing platform based on a fine-grained shared memory paradigm. This massively parallel processing platform held considerable promise for meeting the computing requirement of agent-based models of spatial problems. A dynamic relationship table rebuilding method was proposed to enable the use of GPUs for parallel agent-based modeling of the spatial Von Thünen Model. The key algorithm played an important role in best exploiting high-performance resources in GPUs for large-scale spatial simulation. Experiments conducted to examine computing performance show that GPUs provide a computationally efficient alternative to traditional parallel computing architectures and substantially accelerate agent-based models in large-scale spatial space.

Key words: spatial index grid, multi-agent system, parallel computation, GPU

中图分类号:

TP391.9

赵元, 程家昌, 王璐, 胡月明. 基于GPU的一类地理多智能体系统并行仿真研究[J]. 系统仿真学报, 2015, 27(2): 396-403.

Zhao Yuan, Cheng Jiachang, Wang Lu, Hu Yueming. GPU-Accelerated Simulation for Class of Multi-Agent Based Models[J]. Journal of System Simulation, 2015, 27(2): 396-403.

参考文献

[1] Macal C M, North M J.Agent-Based Modeling and Simulation[C]// Winter Simulation Conference, 2009. USA: WSC, 2009.
[2] Otter H S, Van Der Veen A, De Vriend H J. ABLOoM: Location Behaviour, Spatial Patterns, and Agent-Based Modelling [J]. Journal of Artificial Societies and Social Simulation (S1460-7425), 2001, 4(4). (Van Der Veen A, De Vriend H J. ABLOoM: Location Behaviour, Spatial Patterns, and Agent-Based Modelling [J]. Journal of Artificial Societies and Social Simulation (S1460-7425), 2001, 4(4). (http://jasss.soc.surrey.ac.uk/4/4/2.html
[3] 陶海燕, 黎夏, 陈晓翔, 等. 基于多智能体的地理空间分异现象模拟——以城市居住空间演变为例[J]. 地理学报, 2007, 62(6): 579-588.
[4] 陶海燕, 潘茂林, 黎夏, 等. 城市居住空间分异仿真模型框架研究[J]. 系统仿真学报, 2007, 19(21): 5086-5089.
[5] 张鸿辉, 曾永年, 谭荣, 等. 多智能体区域土地利用优化配置模型及其应用[J]. 地理学报, 2011, 66(7): 972-984.
[6] 全泉, 田光进, 沙默泉. 基于多智能体与元胞自动机的上海城市扩展动态模拟[J]. 生态学报, 2011, 31(10): 2875-2887.
[7] 李玮, 毕贵红, 张寿明. 基于Agent动态小世界网络的HIV同性传播仿真研究[J]. 系统仿真学报, 2012, 24(1): 216-222.
[8] 崔喜红, 李强, 李学东, 等. 公共场所疏散引导人静态布局优化算法及其应用[J]. 系统仿真学报, 2008, 20(22): 6285-6289.
[9] 崔喜红, 李强, 陈晋, 等. 基于多智能体技术的公共场所人员疏散模型研究[J]. 系统仿真学报, 2008, 20(4): 1006-1010.
[10] 余文广, 王维平, 李群. 并行Agent仿真研究综述[J]. 系统仿真学报, 2012, 24(2): 245-251.
[11] Lees M, Logan B, Minson R, et al. Distributed Simulation of MAS[M]. Berlin, Germnay: Springer, 2005: 25-36.
[12] Uhrmacher A M, Gugler K.Distributed, parallel simulation of multiple, deliberative agents[C]. USA: IEEE, 2000.
[13] 鄢超波, 赖华贵, 赵千川. 多智能体并行仿真框架[J]. 系统仿真学报, 2010, 22(S1): 191-195.
[14] Tang W, Bennett D A.Parallel Agent-Based Modeling of Spatial Opinion Diffusion Accelerated using Graphics Processing Units[J]. Ecological Modelling (S0304-3800), 2011, 222(19): 3605-3615.
[15] Shook E, Wang S, Tang W.A Communication-Aware Framework for Parallel Spatially Explicit Agent-Based Models[J]. International Journal of Geographical Information Science (S1365-8816), 2013, 11(27): 2160-2181.
[16] Tang W.Parallel Construction of Large Circular Cartograms using Graphics Processing Units[J]. International Journal of Geographical Information Science (S1365-8816), 2013, 11(27): 2182-2206.
[17] Clarke K C.Geocomputation’s Future at the Extremes: High Performance Computing and Nanoclients[J]. Parallel Computing (S0167-8191), 2003, 29(10): 1281-1295.
[18] Tang W, Wang S.HPABM: A Hierarchical Parallel Simulation Framework for Spatially-explicit Agent-based Models[J]. Transactions in GIS (S1467-9671), 2009, 13(3): 315-333.
[19] Li X, Zhang X, Yeh A, et al. Parallel Cellular Automata for Large-Scale Urban Simulation using Load-Balancing Techniques[J]. International Journal of Geographical Information Science (S1365-8816), 2010, 24(6): 803-820.
[20] Gobron S, Devillard F, Heit B.Retina Simulation using Cellular Automata and GPU Programming[J]. Machine Vision and Applications (S0932-8092), 2007, 18(6): 331-342.
[21] Perumalla K S.Discrete-Event Execution Alternatives on General Purpose Graphical Processing Units (GPGPUs)[C]. USA: IEEE Computer Society, 2006.
[22] Perumalla K S, Aaby B G.Data Parallel Execution Challenges and Runtime Performance of Agent Simulations on Gpus[C]. USA: Society for Computer Simulation International, 2008.
[23] D'Souza R M, Lysenko M, Marino S, et al. Data-Parallel Algorithms for Agent-Based Model Simulation of Tuberculosis on Graphics Processing Units[C]. USA: Society for Computer Simulation International, 2009.
[24] Alberts S, Keenan M K, D Souza R M, et al. Data-Parallel Techniques for Simulating a Mega-Scale Agent-Based Model of Systemic Inflammatory Response Syndrome on Graphics Processing Units[J]. Simulation (S0037-5497), 2012, 88(8): 895-907.
[25] Strippgen D, Nagel K.Using Common Graphics Hardware for Multi-Agent Traffic Simulation with CUDA[C]. Belgium: ICST, 2009.
[26] Shook E, Wang S, Tang W.A Communication-Aware Framework for Parallel Spatially Explicit Agent-Based Models[J]. International Journal of Geographical Information Science (S1365-8816), 2013, 11(27): 2160-2181.
[27] Satish N, Harris M, Garland M.Designing Efficient Sorting Algorithms for Manycore GPUs[C]. USA: IEEE Computer Society, 2009.