并行Agent仿真研究综述
|
摘要
作为一种研究复杂系统的有效途径,基于Agent的建模仿真方法得到了广泛应用,但随着应用规模和复杂度的增加,仿真运行速度成为制约其应用的一个重要因素。并行Agent仿真通过将Agent模型分配到多个处理单元上同时运行来减少仿真运行时间,是提高仿真运行速度的一个直接手段。根据基于Agent的建模仿真的基本思想,分析了并行Agent仿真区别于传统的并行离散事件仿真的新特点,着重从时间同步协议、负载均衡、通信优化三方面阐述了并行Agent仿真的研究现状,并对基于通用目的图形处理器的并行Agent仿真进行了讨论。最后对并行Agent仿真未来的研究方向进行了展望。
As an effective approach to study complex systems,the method of Agent-based Modeling and Simulation(ABMS) is used widely in many research fields,but as the scale and complexity of its applications enlarge,the execution speed becomes an obstacle to implement ABMS.Parallel Agent-based Simulation(PABS) aims at reducing the execution time through executing concurrently the Agent models distributed on different process units,which is a direct approach to improve the execution speed.According to the principles of ABMS,the new characteristics of PABS that are different from Parallel Discrete Event Simulation were proposed.The overview about PABS was elaborated from the aspects of time synchronization algorithms,load balancing and communication optimizing.PABS based on general purpose graphics processing units was discussed.At last,some future research directions about PABS were proposed.
As an effective approach to study complex systems,the method of Agent-based Modeling and Simulation(ABMS) is used widely in many research fields,but as the scale and complexity of its applications enlarge,the execution speed becomes an obstacle to implement ABMS.Parallel Agent-based Simulation(PABS) aims at reducing the execution time through executing concurrently the Agent models distributed on different process units,which is a direct approach to improve the execution speed.According to the principles of ABMS,the new characteristics of PABS that are different from Parallel Discrete Event Simulation were proposed.The overview about PABS was elaborated from the aspects of time synchronization algorithms,load balancing and communication optimizing.PABS based on general purpose graphics processing units was discussed.At last,some future research directions about PABS were proposed.
引文
[1]Charles M Macal,Michael J North.Agent-Based Modeling and Simulation[C]//Proceedings of the 2009 Winter Simulation Conference.Austin,USA:IEEE Press,2009:86-98.
[2]R Cirillo,T Overbye.Evaluating the Potential Impact of Transmission Constraints on the Operation of a Competitive Electricity Market in Illinois[R].USA:Argonne National Laboratory,ANL-06/16,2006.
[3]Charles M Macal,Michael J North,Gail Pieper,Cheryl Drugan.Agent-based Modeling and Simulation for Exascale Computing[J].SciDAC Review(S1935-0570),2008,3(2):34-41.
[4]Richard M Fujimoto.Parallel And Distributed Simulation Systems[C]//Proceedings of the 2001 Winter Simulation Conference.Arlington,USA:IEEE Press,2001:147-157.
[5]A M Uhrmacher,K Gugler.Distributed,Parallel Simulation of Multiple,Deliberative Agents[C]//Proceedings of the 14th Workshop on Parallel and Distributed Simulation(PADS’00).Bologna,Italy:ACM Press,2000:101-110.
[6]Brian Logan,Georgios Theodoropoulos.The distributed simulation of multi-agent systems[J].Proceedings of the IEEE Special Issue on Agent-oriented Software Approaches in Distributed Modeling and Simulation(S0018-9219),2001,89(2):174-185.
[7]Michael Lees,Brian Logan,Rob Minson,Ton Oguara,Georgios Theodoropoulos.Distributed Simulation of MAS[C]//Proceedings of the Joint Workshop on Multi-Agent and Multi-Agent-Based Simulation'04.New York,USA:Springer Press,2004:21-30.
[8]Wooldridge M J,Jennings N R.Intelligent agents:Theory and Practice[J].Knowledge Engineering Reviews(S0269-8889),1995,10(2):115-152.
[9]李群,王维平,朱一凡,雷永林,梅珊.仿真模型设计与执行[M].北京:电子工业出版社,2009.
[10]丁浩,杨小平.SWARM—一个支持人工生命建模的面向对象模拟平台[J].系统仿真学报,2002,14(5):569-572.
[11]姜昌华,韩伟,胡幼华.Repast—一个多Agent仿真平台[J].系统仿真学报,2006,18(8):2319-2322.
[12]Seth Tisue,Uri Wilensky.NetLogo:Design and Implementation of aMulti-Agent Modeling Environment[C]//Proceedings of Agent 2004.Chicago,USA:University of Chicago,2004:161-184.
[13]Sean Luke,Claudio Cioffi-Revilla,Liviu Panait,Keith Sullivan.MASON:A New Multi-Agent Simulation Tookit[C]//Proceedings of the 2004Swarm Fest Workshop.Ann Arbor,USA:University of Michigan,2004.
[14]Shengnan Wu.Agent-Based Discrete Event Simulation Modeling AndEvolutionary Real-Time Decision Making For Large-Scale Systems[D].Pittsburgh,USA:University of Pittsburgh,2008.
[15]Benjamin Dubiel,Omer Tsimhoni.Integrating Agent Based ModelingInto A Discrete Event Simulation[C]//Proceedings of the 2005Winter Simulation Conference.Orlando,USA:IEEE Press,2005:1029-1037.
[16]Stephan Onggo.Running Agent-based Models on a Discrete-EventSimulator[R].UK:Lancaster University,2008.
[17]Patrick F Riley,George F Riley.SPADES—A Distributed AgentSimulation Enviroment With Software-In-The-Loop Execution[C]//Proceedings of the 2003 Winter Simulation Conference.New Orleans,USA:IEEE Press,2003:817-825.
[18]Maria Hybinette,Eileen Kraemer,Yin Xiong,Glenn Matthews,JaimAhmed.SASSY:A Design For A Scalable Agent-Based SimulationSystem Using A Distributed Discrete Event Infrastructure[C]//Proceedings of the 2006 Winter Simulation Conference.Monterey,USA:IEEE Press,2006:926-933.
[19]George Vulov,Tianhao He,Maria Hybinette.Quantitative AssessmentOf An Agent-Based Simulation On A Time Warp Executive[C]//Proceedings of the 2008 Winter Simulation Conference.Florida,USA:IEEE Press,2008:1068-1076.
[20]M Lees,B Logan,G Theodoropoulos.Adaptive optimistic synchronisationfor multi-agent simulation[C]//Proceedings of the 5th EUROSIMCongress on Modelling and Simulation.Paris,France:EUROSIM,2004:77-82.
[21]M Lees,B Logan,C Dan,T Oguara,G Theodoropoulos.Decision-theoretic throttling for optimistic simulations of multi-agent system[C]//Proceedings of the Ninth IEEE International Symposium onDistributed Simulation and Real Time Applications(DS-RT 2005).Montreal,Canada:IEEE Press,2005:171-178.
[22]Michael Lees,Brian Logan,Chen Dan,Ton Oguara,GeorgiosTheodoropoulos.Analysing the Performance of Optimistic SynchronisationAlgorithms in Simulations of Multi-Agent Systems[C]//Proceedingsof the 20th Workshop on Principles of Advanced and DistributedSimulation(PADS'06).Singapore:IEEE Press,2006:37-44.
[23]Matthias Scheutz,Paul Schermerhorn.Adaptive Algorithms for theDynamic Distribution and Parallel Execution of Agent-Based Models[J].Journal of Parallel and Distributed Computing(S0743-7315),2006,66(8):1037-1051.
[24]Yongwei Wang,Michael Lees,Wentong Cai,Suiping Zhou,MalcolmYoke Hean Low.Cluster Based Partitioning For Agent-Based CrowdSimulations[C]//Proceedings of the 2009 Winter SimulationConference.Austin,USA:IEEE Press,2009:1047-1058.
[25]Dac Phuong Ho.The Duy Bui and Nguyen Luong Do.DividingAgents on the Grid for Large Scale Simulation[C]//Proceedings ofPRIMA 2008.Hanoi,Vietnam:Springer Press,2008:222-230.
[26]Y C Jianga,Z Y Xiab,Y P Zhonga,S Y Zhanga.An adaptiveadjusting mechanism for agent distributed blackboard architecture[J].Microprocessors and Microsystems(S0141-9331),2005,29(8):9-20.
[27]Myeong-Wuk Jang,Gul Agha.Agent framework services to reduceagent communication overhead in large-scale agent-based simulations[J].Simulation Modeling Practice and Theory(S1569-190X),2006,14(6):679-694.
[28]Lihua Wang,Stephen John Turner,Fang Wang.Interest Managementin Agent-based Distributed Simulations[C]//Proceedings of theSeventh IEEE International Symposium on Distributed Simulationand Real-Time Applications(DS-RT'03).Delft,Netherlands:IEEEPress,2003:20-27.
[29]Tianhao He,Maria Hybinette.A Comparison of Interest ManagerMechanisms for Agent-Based Simulations using a Time WarpExecutive[C]//Proceedings of 22nd Workshop on Principles ofAdvanced and Distributed Simulation.Rome,Italy:ACM Press,2008:157-162.
[30]Nick Collier.Repast HPC Manual[R].USA:Argonne NationalLaboratory,2010.
[31]张舒,禇艳利,赵开勇,张钰勃.GPU高性能运算之CUDA[M].北京:中国水利水电出版社,2009.
[32]吴恩华.图形处理器用于通用计算的技术、现状及其挑战术[J].软件学报,2004,15(10):1493-1504.
[33]Michael C Schatz,Cole Trapnell,Arthur L Delcher,AmitabhVarshney.High-throughput sequence alignment using GraphicsProcessing Units[J].BMC Bioinformatics(S1471-2105),2007,8(10):http://www.biomedcentral.com/1471-2105/8/474.
[34]Sam S Stone,Justin P Haldar,Stephanie C Tsao,Wen-mei Wu,Zhi-PeiLiang,Bradley P Sutton.Accelerating Advanced MRI Reconstructions onGPUs[C]//Proceedings of the 5th International Conference onComputing Frontiers.Ischia,Italy:ACM Press,2008:261-272.
[35]Erich Elsen,Patrick LeGresley,Eric Darve.Large calculation of theflow over a hypersonic vehicle using a GPU[J].Journal ofComputational Physics(S0021-9991),2008,227(24):10148-10161.
[36]刘伟峰,王永胜,张天雷,张兵.使用GPU模拟地震波传播的性能研究[J].系统仿真学报,2009,21(S1):170-174.
[37]陈飞国,葛蔚,李静海.复杂多相流动分子动力学模拟在GPU上的实现[J].中国科学B辑:化学,2008,38(12):1120-1128.
[38]Kalyan S Perumalla.Discrete-event Execution Alternatives onGeneral Purpose Graphical Processing Units(GPGPUs)[C]//Proceedings of the 20th Workshop on Principles of Advanced andDistributed Simulation.Singapore:ACM Press,2006:74-81.
[39]Hyungwook Park,Paul A Fishwick.A GPU-Based ApplicationFramework Supporting Fast Discrete-Event Simulation[J].SIMULATION(S0037-5497),2010,86(10):613-628.
[40]Kalyan S Perumalla,Brandon G Aaby.Data Parallel ExecutionChallenges and Runtime Performance of Agent Simulations on GPUs[C]//Proceedings of the 2008'Spring Simulation Multi-Conference.Ottawa,Canada:SCS,2008:116-123.
[41]David Strippgen,Kai Nagel.Using common graphics hardware formulti-agent traffic simulation with CUDA[C]//Proceedings ofSIMUTools 2009.Rome,Italy:ICST,2009.
[42]NVIDIA Corporation.NVIDIA's Next Generation CUDA ComputeArchitecture:Femi[R].USA:NVIDIA Corporation,2009.
[43]NVIDIA Corporation.NVIDIA CUDA:Compute Unified DeviceArchitectureProgramming Guide 2.0[R].USA:NVIDIA Corporation,2008.
[44]Khronos OpenCL Working Group.The OpenCL Specification(V1.0)[R].USA:Khronos Group,2009.
[45]Hyungwook Park,Paul A Fishwick.A Fast Hybrid Time-synchronous/Event Approach to Parallel Discrete Event Simulation of QueuingNetworks[C]//Proceedings of the 2008 Winter Simulation Conference.Florida,USA:IEEE Press,2008:795-803.
[46]Roshan M D'Souza,Mikola Lysenko,Simeone Marino,Denise Kirschner.Data-Parallel Algorithms for Agent-Based Model Simulation of TuberculosisOn Graphics Processing Units[C]//Proceedings of SpringSim'09—Agent-Directed Simulation(ADS 09).San Diego,USA:SCS,2009.
[47]Trista P Chen,Yen-Kuang Chen.Challenges and Opportunities ofObtaining Performance from Multi-Core CPUs and Many-Core GPUs[C]//Proceedings of ICASSP 2009.Taipei,Taiwan,China:IEEEPress,2009:613-616.
[2]R Cirillo,T Overbye.Evaluating the Potential Impact of Transmission Constraints on the Operation of a Competitive Electricity Market in Illinois[R].USA:Argonne National Laboratory,ANL-06/16,2006.
[3]Charles M Macal,Michael J North,Gail Pieper,Cheryl Drugan.Agent-based Modeling and Simulation for Exascale Computing[J].SciDAC Review(S1935-0570),2008,3(2):34-41.
[4]Richard M Fujimoto.Parallel And Distributed Simulation Systems[C]//Proceedings of the 2001 Winter Simulation Conference.Arlington,USA:IEEE Press,2001:147-157.
[5]A M Uhrmacher,K Gugler.Distributed,Parallel Simulation of Multiple,Deliberative Agents[C]//Proceedings of the 14th Workshop on Parallel and Distributed Simulation(PADS’00).Bologna,Italy:ACM Press,2000:101-110.
[6]Brian Logan,Georgios Theodoropoulos.The distributed simulation of multi-agent systems[J].Proceedings of the IEEE Special Issue on Agent-oriented Software Approaches in Distributed Modeling and Simulation(S0018-9219),2001,89(2):174-185.
[7]Michael Lees,Brian Logan,Rob Minson,Ton Oguara,Georgios Theodoropoulos.Distributed Simulation of MAS[C]//Proceedings of the Joint Workshop on Multi-Agent and Multi-Agent-Based Simulation'04.New York,USA:Springer Press,2004:21-30.
[8]Wooldridge M J,Jennings N R.Intelligent agents:Theory and Practice[J].Knowledge Engineering Reviews(S0269-8889),1995,10(2):115-152.
[9]李群,王维平,朱一凡,雷永林,梅珊.仿真模型设计与执行[M].北京:电子工业出版社,2009.
[10]丁浩,杨小平.SWARM—一个支持人工生命建模的面向对象模拟平台[J].系统仿真学报,2002,14(5):569-572.
[11]姜昌华,韩伟,胡幼华.Repast—一个多Agent仿真平台[J].系统仿真学报,2006,18(8):2319-2322.
[12]Seth Tisue,Uri Wilensky.NetLogo:Design and Implementation of aMulti-Agent Modeling Environment[C]//Proceedings of Agent 2004.Chicago,USA:University of Chicago,2004:161-184.
[13]Sean Luke,Claudio Cioffi-Revilla,Liviu Panait,Keith Sullivan.MASON:A New Multi-Agent Simulation Tookit[C]//Proceedings of the 2004Swarm Fest Workshop.Ann Arbor,USA:University of Michigan,2004.
[14]Shengnan Wu.Agent-Based Discrete Event Simulation Modeling AndEvolutionary Real-Time Decision Making For Large-Scale Systems[D].Pittsburgh,USA:University of Pittsburgh,2008.
[15]Benjamin Dubiel,Omer Tsimhoni.Integrating Agent Based ModelingInto A Discrete Event Simulation[C]//Proceedings of the 2005Winter Simulation Conference.Orlando,USA:IEEE Press,2005:1029-1037.
[16]Stephan Onggo.Running Agent-based Models on a Discrete-EventSimulator[R].UK:Lancaster University,2008.
[17]Patrick F Riley,George F Riley.SPADES—A Distributed AgentSimulation Enviroment With Software-In-The-Loop Execution[C]//Proceedings of the 2003 Winter Simulation Conference.New Orleans,USA:IEEE Press,2003:817-825.
[18]Maria Hybinette,Eileen Kraemer,Yin Xiong,Glenn Matthews,JaimAhmed.SASSY:A Design For A Scalable Agent-Based SimulationSystem Using A Distributed Discrete Event Infrastructure[C]//Proceedings of the 2006 Winter Simulation Conference.Monterey,USA:IEEE Press,2006:926-933.
[19]George Vulov,Tianhao He,Maria Hybinette.Quantitative AssessmentOf An Agent-Based Simulation On A Time Warp Executive[C]//Proceedings of the 2008 Winter Simulation Conference.Florida,USA:IEEE Press,2008:1068-1076.
[20]M Lees,B Logan,G Theodoropoulos.Adaptive optimistic synchronisationfor multi-agent simulation[C]//Proceedings of the 5th EUROSIMCongress on Modelling and Simulation.Paris,France:EUROSIM,2004:77-82.
[21]M Lees,B Logan,C Dan,T Oguara,G Theodoropoulos.Decision-theoretic throttling for optimistic simulations of multi-agent system[C]//Proceedings of the Ninth IEEE International Symposium onDistributed Simulation and Real Time Applications(DS-RT 2005).Montreal,Canada:IEEE Press,2005:171-178.
[22]Michael Lees,Brian Logan,Chen Dan,Ton Oguara,GeorgiosTheodoropoulos.Analysing the Performance of Optimistic SynchronisationAlgorithms in Simulations of Multi-Agent Systems[C]//Proceedingsof the 20th Workshop on Principles of Advanced and DistributedSimulation(PADS'06).Singapore:IEEE Press,2006:37-44.
[23]Matthias Scheutz,Paul Schermerhorn.Adaptive Algorithms for theDynamic Distribution and Parallel Execution of Agent-Based Models[J].Journal of Parallel and Distributed Computing(S0743-7315),2006,66(8):1037-1051.
[24]Yongwei Wang,Michael Lees,Wentong Cai,Suiping Zhou,MalcolmYoke Hean Low.Cluster Based Partitioning For Agent-Based CrowdSimulations[C]//Proceedings of the 2009 Winter SimulationConference.Austin,USA:IEEE Press,2009:1047-1058.
[25]Dac Phuong Ho.The Duy Bui and Nguyen Luong Do.DividingAgents on the Grid for Large Scale Simulation[C]//Proceedings ofPRIMA 2008.Hanoi,Vietnam:Springer Press,2008:222-230.
[26]Y C Jianga,Z Y Xiab,Y P Zhonga,S Y Zhanga.An adaptiveadjusting mechanism for agent distributed blackboard architecture[J].Microprocessors and Microsystems(S0141-9331),2005,29(8):9-20.
[27]Myeong-Wuk Jang,Gul Agha.Agent framework services to reduceagent communication overhead in large-scale agent-based simulations[J].Simulation Modeling Practice and Theory(S1569-190X),2006,14(6):679-694.
[28]Lihua Wang,Stephen John Turner,Fang Wang.Interest Managementin Agent-based Distributed Simulations[C]//Proceedings of theSeventh IEEE International Symposium on Distributed Simulationand Real-Time Applications(DS-RT'03).Delft,Netherlands:IEEEPress,2003:20-27.
[29]Tianhao He,Maria Hybinette.A Comparison of Interest ManagerMechanisms for Agent-Based Simulations using a Time WarpExecutive[C]//Proceedings of 22nd Workshop on Principles ofAdvanced and Distributed Simulation.Rome,Italy:ACM Press,2008:157-162.
[30]Nick Collier.Repast HPC Manual[R].USA:Argonne NationalLaboratory,2010.
[31]张舒,禇艳利,赵开勇,张钰勃.GPU高性能运算之CUDA[M].北京:中国水利水电出版社,2009.
[32]吴恩华.图形处理器用于通用计算的技术、现状及其挑战术[J].软件学报,2004,15(10):1493-1504.
[33]Michael C Schatz,Cole Trapnell,Arthur L Delcher,AmitabhVarshney.High-throughput sequence alignment using GraphicsProcessing Units[J].BMC Bioinformatics(S1471-2105),2007,8(10):http://www.biomedcentral.com/1471-2105/8/474.
[34]Sam S Stone,Justin P Haldar,Stephanie C Tsao,Wen-mei Wu,Zhi-PeiLiang,Bradley P Sutton.Accelerating Advanced MRI Reconstructions onGPUs[C]//Proceedings of the 5th International Conference onComputing Frontiers.Ischia,Italy:ACM Press,2008:261-272.
[35]Erich Elsen,Patrick LeGresley,Eric Darve.Large calculation of theflow over a hypersonic vehicle using a GPU[J].Journal ofComputational Physics(S0021-9991),2008,227(24):10148-10161.
[36]刘伟峰,王永胜,张天雷,张兵.使用GPU模拟地震波传播的性能研究[J].系统仿真学报,2009,21(S1):170-174.
[37]陈飞国,葛蔚,李静海.复杂多相流动分子动力学模拟在GPU上的实现[J].中国科学B辑:化学,2008,38(12):1120-1128.
[38]Kalyan S Perumalla.Discrete-event Execution Alternatives onGeneral Purpose Graphical Processing Units(GPGPUs)[C]//Proceedings of the 20th Workshop on Principles of Advanced andDistributed Simulation.Singapore:ACM Press,2006:74-81.
[39]Hyungwook Park,Paul A Fishwick.A GPU-Based ApplicationFramework Supporting Fast Discrete-Event Simulation[J].SIMULATION(S0037-5497),2010,86(10):613-628.
[40]Kalyan S Perumalla,Brandon G Aaby.Data Parallel ExecutionChallenges and Runtime Performance of Agent Simulations on GPUs[C]//Proceedings of the 2008'Spring Simulation Multi-Conference.Ottawa,Canada:SCS,2008:116-123.
[41]David Strippgen,Kai Nagel.Using common graphics hardware formulti-agent traffic simulation with CUDA[C]//Proceedings ofSIMUTools 2009.Rome,Italy:ICST,2009.
[42]NVIDIA Corporation.NVIDIA's Next Generation CUDA ComputeArchitecture:Femi[R].USA:NVIDIA Corporation,2009.
[43]NVIDIA Corporation.NVIDIA CUDA:Compute Unified DeviceArchitectureProgramming Guide 2.0[R].USA:NVIDIA Corporation,2008.
[44]Khronos OpenCL Working Group.The OpenCL Specification(V1.0)[R].USA:Khronos Group,2009.
[45]Hyungwook Park,Paul A Fishwick.A Fast Hybrid Time-synchronous/Event Approach to Parallel Discrete Event Simulation of QueuingNetworks[C]//Proceedings of the 2008 Winter Simulation Conference.Florida,USA:IEEE Press,2008:795-803.
[46]Roshan M D'Souza,Mikola Lysenko,Simeone Marino,Denise Kirschner.Data-Parallel Algorithms for Agent-Based Model Simulation of TuberculosisOn Graphics Processing Units[C]//Proceedings of SpringSim'09—Agent-Directed Simulation(ADS 09).San Diego,USA:SCS,2009.
[47]Trista P Chen,Yen-Kuang Chen.Challenges and Opportunities ofObtaining Performance from Multi-Core CPUs and Many-Core GPUs[C]//Proceedings of ICASSP 2009.Taipei,Taiwan,China:IEEEPress,2009:613-616.
版权所有：© 2023 中国地质图书馆 中国地质调查局地学文献中心