nach oben

International Journal of Parallel Programming

Erschienen in:

19.01.2016

Parallelization Strategies for Spatial Agent-Based Models

verfasst von: Nuno Fachada, Vitor V. Lopes, Rui C. Martins, Agostinho C. Rosa

Erschienen in: International Journal of Parallel Programming | Ausgabe 3/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Agent-based modeling (ABM) is a bottom-up modeling approach, where each entity of the system being modeled is uniquely represented as an independent decision-making agent. Large scale emergent behavior in ABMs is population sensitive. As such, the number of agents in a simulation should be able to reflect the reality of the system being modeled, which can be in the order of millions or billions of individuals in certain domains. A natural solution to reach acceptable scalability in commodity multi-core processors consists of decomposing models such that each component can be independently processed by a different thread in a concurrent manner. In this paper we present a multithreaded Java implementation of the PPHPC ABM, with two goals in mind: (1) compare the performance of this implementation with an existing NetLogo implementation; and, (2) study how different parallelization strategies impact simulation performance on a shared memory architecture. Results show that: (1) model parallelization can yield considerable performance gains; (2) distinct parallelization strategies offer specific trade-offs in terms of performance and simulation reproducibility; and, (3) PPHPC is a valid reference model for comparing distinct implementations or parallelization strategies, from both performance and statistical accuracy perspectives.

Vorheriger Artikel A Wait-Free Hash Map

Nächster Artikel Restart Optimization for Transactional Memory with Lazy Conflict Detection

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

In shared memory architectures, LPs are usually represented by threads, which communicate via synchronized access to shared variables. In distributed memory scenarios, LPs are commonly represented by processes, which communicate via message passing.

Predator–Prey for High-Performance Computing.

Single instruction, multiple data.

http://openmp.org/.

A non-terminating simulation is one for which there is no natural event to specify the length of a run [32].

Controller synchronization points (i.e. calls to ControllerSync()) are discussed in Sect. 3.2.3.

Aaby, B., Perumalla, K., Seal, S.: Efficient simulation of agent-based models on multi-GPU and multi-core clusters. In: Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques, pp. 1–10. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering) (2010)

Axtell, R., Axelrod, R., Epstein, J.M., Cohen, M.D.: Aligning simulation models: a case study and results. Comput. Math. Organ. Theory 1(2), 123–141 (1996). doi:10.1007/BF01299065 CrossRef

Berryman, M.: Review of software platforms for agent based models. Technical report DSTO-GD-0532, Land Operations Division, Defence Science and Technology Organisation, PO Box 1500, Edinburgh, South Australia 5111, Australia (2008)

Brugger, C., Weithoffer, S., Schryver, C.d., Wasenmüller, U., Wehn, N.: On parallel random number generation for accelerating simulations of communication systems. Adv. Radio Sci. 12, 75–81 (2014). doi:10.5194/ars-12-75-2014. http://www.adv-radio-sci.net/12/75/2014/

Chen, D., Wang, L., Zomaya, A., Dou, M., Chen, J., Deng, Z., Hariri, S.: Parallel simulation of complex evacuation scenarios with adaptive agent models. IEEE Trans. Parall. Distrib. 26(3), 847–857 (2015). doi:10.1109/TPDS.2014.2311805 CrossRef

Coakley, S., Gheorghe, M., Holcombe, M., Chin, S., Worth, D., Greenough, C.: Exploitation of high performance computing in the FLAME agent-based simulation framework. In: Proceedings of the 14th International Conference on High Performance Computing and Communications, pp. 538–545. Liverpool, UK (2012). doi:10.1109/HPCC.2012.79

Coddington, P.D.: Random number generators for parallel computers. Northeast Parallel Architecture Center (1997), Paper 13. http://surface.syr.edu/npac/13/

Collier, N., North, M.: Repast HPC: A platform for large-scale agent-based modeling. In: W. Dubitzky, K. Kurowski, B. Schott (eds.) Large-Scale Computing Techniques for Complex System Simulations, Chap. 5, pp. 81–109. Wiley, New York (2011). doi:10.1002/9781118130506.ch5

Cosenza, B., Cordasco, G., De Chiara, R., Scarano, V.: Distributed load balancing for parallel agent-based simulations. In: 19th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), pp. 62–69 (2011). doi:10.1109/PDP.2011.22

10.

D’Souza, R., Lysenko, M., Marino, S., Kirschner, D.: Data-parallel algorithms for agent-based model simulation of tuberculosis on graphics processing units. In: Proceedings of the 2009 Spring Simulation Multiconference, SpringSim’09, pp. 21:1–21:12. Society for Computer Simulation International, San Diego, CA, USA (2009)

11.

D’Souza, R., Lysenko, M., Rahmani, K.: Sugarscape on steroids: simulating over a million agents at interactive rates. In: Proceedings of Agent 2007 Conference, Chicago, USA (2007)

12.

Dyer, D.W.: Uncommons Maths (2012). http://maths.uncommons.org/

13.

Edmonds, B., Hales, D.: Replication, replication and replication: some hard lessons from model alignment. J. Artif. Soc. Soc. Simul. 6(4), 11 (2003). http://jasss.soc.surrey.ac.uk/6/4/11.html

14.

Fachada, N.: Agent-based simulation of the immune system. Master’s thesis, Instituto Superior Técnico, Universidade Técnica de Lisboa, Lisboa (2008)

15.

Fachada, N., Lopes, V.V., Martins, R.C., Rosa, A.C.: Towards a standard model for research in agent-based modeling and simulation. PeerJ Comput. Sci. 1, e36 (2015). doi:10.7717/peerj-cs.36 CrossRef

16.

Fachada, N., Lopes, V.V., Rosa, A.: Simulating antigenic drift and shift in influenza A. In: Proceedings of the 2009 ACM symposium on Applied Computing, SAC’09, pp. 2093–2100. ACM, New York, NY, USA (2009). doi:10.1145/1529282.1529744

17.

Gamma, E., Helm, R., Johnson, R., Vlissides, J.: Design patterns: elements of reusable object-oriented software. Pearson Education, New York (1994)MATH

18.

Gibbons, J.D., Chakraborti, S.: Nonparametric statistical inference. Statistics: Textbooks & Monographs, 5th edn. Chapman and Hall/CRC, Boca Raton (2010)

19.

Glass, K., Livingston, M., Conery, J.: Distributed simulation of spatially explicit ecological models. SIGSIM Simul. Dig. 27(1), 60–63 (1997). doi:10.1145/268823.268902 CrossRef

20.

Göetz, B., Peierls, T., Bloch, J., Bowbeer, J., Holmes, D., Lea, D.: Java Concurrency in Practice. Addison-Wesley, Cambridge (2006)

21.

Goldsby, M.E., Pancerella, C.M.: Multithreaded agent-based simulation. In: Proceedings of the 2013 Winter Simulation Conference: Simulation: Making Decisions in a Complex World. WSC’13, pp. 1581–1591. IEEE Press, Washington, DC, USA (2013)

22.

Gong, Z., Tang, W., Bennett, D.A., Thill, J.C.: Parallel agent-based simulation of individual-level spatial interactions within a multicore computing environment. Int. J. Geogr. Inf. Sci. 27(6), 1152–1170 (2013). doi:10.1080/13658816.2012.741240 CrossRef

23.

Gosling, J., Joy, B., Steele, G., Bracha, G., Buckley, A.: The Java Language Specification (Java SE 8). Oracle Corporation, Redwood City (2014)

24.

Grimm, V., Berger, U., DeAngelis, D., Polhill, J., Giske, J., Railsback, S.: The ODD protocol: a review and first update. Ecol. Model. 221(23), 2760–2768 (2010)CrossRef

25.

Gulyás, L., Szabó, A., Legéndi, R., Máhr, T., Bocsi, R., Kampis, G.: Tools for large scale (distributed) agent-based computational experiments. In: Proceedings of The Computational Social Science Society of the Americas (2011)

26.

Gulyás, L., Szemes, G., Kampis, G., de Back, W.: A modeler-friendly API for ABM partitioning. In: Proceedings of the ASME 2009 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, pp. 219–226. San Diego, CA, USA (2009)

27.

Hill, D.R.C., Mazel, C., Passerat-Palmbach, J., Traore, M.K.: Distribution of random streams for simulation practitioners. Concurr. Comput. Pract. Exp. 25(10), 1427–1442 (2013). doi:10.1002/cpe.2942 CrossRef

28.

Husselmann, A., Hawick, K.: Spatial agent-based modelling and simulations—a review. Res. Lett. Inf. Math. Sci. 7, 101–111 (2008)

29.

Isaac, A.G.: The ABM template models: A reformulation with reference implementations. J. Artif. Soc. Soc. Simulat. 14(2), 5 (2011). http://jasss.soc.surrey.ac.uk/14/2/5.html

30.

Keenan, M., Komarov, I., D’Souza, R.M., Riolo, R.: Novel graphics processing unit-based parallel algorithms for understanding species diversity in forests. In: Proceedings of the 2012 Symposium on High Performance Computing. Society for Computer Simulation International (2012)

31.

Kruskal, W.H., Wallis, W.A.: Use of ranks in one-criterion variance analysis. J. Am. Stat. Assoc. 47(260), 583–621 (1952). doi:10.1080/01621459.1952.10483441 CrossRefMATH

32.

Law, A.M.: Simulation Modeling and Analysis, 5th edn. McGraw-Hill, Columbus (2015)

33.

Lenoski, D.E., Weber, W.D.: Scalable Shared-Memory Multiprocessing. Elsevier, Amsterdam (1991)

34.

Luke, S., Cioffi-Revilla, C., Panait, L., Sullivan, K., Balan, G.: MASON: a multiagent simulation environment. Simulation 81(7), 517–527 (2005). doi:10.1177/0037549705058073 CrossRef

35.

Lysenko, M., D’Souza, R.: A framework for megascale agent based model simulations on graphics processing units. J. Artif. Soc. Soc. Simul. 11(4), 10 (2008). http://jasss.soc.surrey.ac.uk/11/4/10.html

36.

Lytinen, S.L., Railsback, S.F.: The evolution of agent-based simulation platforms: a review of NetLogo 5.0 and ReLogo. In: Proceedings of the Fourth International Symposium on Agent-Based Modeling and Simulation (2012)

37.

Macal, C., North, M.: Tutorial on agent-based modelling and simulation. J. Simul. 4(3), 151–162 (2010)CrossRef

38.

Merlone, U., Sonnessa, M., Terna, P.: Horizontal and vertical multiple implementations in a model of industrial districts. J. Artif. Soc. Soc. Simul. 11(2), 5 (2008). http://jasss.soc.surrey.ac.uk/11/2/5.html

39.

Müller, B., Balbi, S., Buchmann, C.M., de Sousa, L., Dressler, G., Groeneveld, J., Klassert, C.J., Le, Q.B., Millington, J.D., Nolzen, H., Parker, D.C., Polhill, J.G., Schlüter, M., Schulze, J., Schwarz, N., Sun, Z., Taillandier, P., Weise, H.: Standardised and transparent model descriptions for agent-based models: current status and prospects. Environ. Model. Softw. 55, 156–163 (2014). doi:10.1016/j.envsoft.2014.01.029 CrossRef

40.

Nikolai, C., Madey, G.: Tools of the trade: a survey of various agent based modeling platforms. J. Artif. Soc. Soc. Simul. 12(2), 2 (2009). http://jasss.soc.surrey.ac.uk/12/2/2.html

41.

North, M., Collier, N., Vos, J.: Experiences creating three implementations of the repast agent modeling toolkit. ACM Trans. Model. Comput. Simul. 16(1), 1–25 (2006)CrossRef

42.

North, M.J., Collier, N.T., Ozik, J., Tatara, E.R., Macal, C.M., Bragen, M., Sydelko, P.: Complex adaptive systems modeling with Repast Simphony. Complex Adapt. Syst. Model. 1(1), 1–26 (2013). doi:10.1186/2194-3206-1-3 CrossRef

43.

Parry, H.R., Bithell, M.: Large scale agent-based modelling: a review and guidelines for model scaling. In: Heppenstall, A.J., Crooks, A.T., See, L.M., Batty, M. (eds.) Agent-Based Models Geogr. Syst., pp. 271–308. Springer, Netherlands (2012)CrossRef

44.

Perumalla, K.S.: Computational spectrum of agent model simulation. In: Cakaj, S. (ed.) Modeling Simulation and Optimization—Focus on Applications, Numerical Analysis and Scientific Computing, Chap. 12, pp. 185–204. InTech (2010)

45.

Railsback, S., Lytinen, S., Jackson, S.: Agent-based simulation platforms: review and development recommendations. Simulation 82(9), 609–623 (2006)CrossRef

46.

Reynolds, C.W.: Flocks, herds and schools: a distributed behavioral model. SIGGRAPH Comput. Graph. 21(4), 25–34 (1987). doi:10.1145/37402.37406 CrossRef

47.

Richmond, P., Coakley, S., Romano, D.: Cellular level agent based modelling on the graphics processing unit. In: International Workshop on High Performance Computational Systems Biology, 2009. HIBI’09. pp. 43–50 (2009)

48.

Richmond, P., Walker, D., Coakley, S., Romano, D.: High performance cellular level agent-based simulation with FLAME for the GPU. Brief Bioinform. 11(3), 334–347 (2010). doi:10.1093/bib/bbp073 CrossRef

49.

Scheutz, M., Schermerhorn, P.: Adaptive algorithms for the dynamic distribution and parallel execution of agent-based models. J. Parallel Distrib. Comput. 66(8), 1037–1051 (2006)CrossRefMATH

50.

Shook, E., Wang, S., Tang, W.: A communication-aware framework for parallel spatially explicit agent-based models. Int. J. Geogr. Inf. Sci. 27(11), 2160–2181 (2013). doi:10.1080/13658816.2013.771740 CrossRef

51.

Srinivasan, A., Mascagni, M., Ceperley, D.: Testing parallel random number generators. Parallel Comput. 29(1), 69–94 (2003). doi:10.1016/S0167-8191(02)00163-1 MathSciNetCrossRef

52.

Steele, Jr., G.L., Lea, D., Flood, C.H.: Fast splittable pseudorandom number generators. In: OOPSLA ’14 Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages and Applications, pp. 453–472 (2014). doi:10.1145/2660193.2660195

53.

Takahashi, T., Mizuta, H.: Efficient agent-based simulation framework for multi-node supercomputers. In: Proceedings of the 38th conference on Winter simulation, pp. 919–925. Winter Simulation Conference (2006)

54.

Tang, W., Bennett, D.: Parallel agent-based modeling of spatial opinion diffusion accelerated using graphics processing units. Ecol. Model. 222(19), 3605–3615 (2011). doi:10.1016/j.ecolmodel.2011.08.016 CrossRef

55.

Tang, W., Jia, M.: Global sensitivity analysis of a large agent-based model of spatial opinion exchange: a heterogeneous multi-GPU acceleration approach. Ann. Assoc. Am. Geogr. 104(3), 485–509 (2014). doi:10.1080/00045608.2014.892342 CrossRef

56.

Tang, W., Wang, S.: HPABM: a hierarchical parallel simulation framework for spatially-explicit agent-based models. Trans. GIS 13(3), 315–333 (2009). doi:10.1111/j.1467-9671.2009.01161.x CrossRef

57.

Tobias, R., Hofmann, C.: Evaluation of free Java-libraries for social-scientific agent based simulation. J. Artif. Soc. Soc. Simul. 7(1), 6 (2004). http://jasss.soc.surrey.ac.uk/7/1/6.html

58.

The Power Challenge technical report: Technical report, Silicon Graphics, Inc., Mountain View (1994)

59.

Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103–111 (1990). doi:10.1145/79173.79181 CrossRef

60.

Vigueras, G., Orduña, J.M., Lozano, M., Cecilia, J.M., García, J.M.: Accelerating collision detection for large-scale crowd simulation on multi-core and many-core architectures. Int. J. High Perform. Comput. Appl. (2013). doi:10.1177/1094342013476119

61.

Voss, A., You, J.Y., Yen, E., Chen, H.Y., Lin, S., Turner, A., Lin, J.P.: Scalable social simulation: investigating population-scale phenomena using commodity computing. In: 2010 IEEE Sixth International Conference on e-Science (e-Science), pp. 1–8. Brisbane, QLD, Australia (2010). doi:10.1109/eScience.2010.46

62.

Wang, J., Rubin, N., Wu, H., Yalamanchili, S.: Accelerating simulation of agent-based models on heterogeneous architectures. In: Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units, GPGPU-6, pp. 108–119. ACM, Houston, Texas, USA (2013). doi:10.1145/2458523.2458534

63.

Wang, K., Shen, Z.: A GPU based trafficparallel simulation module of artificial transportation systems. In: 2012 IEEE International Conference on Service Operations and Logistics, and Informatics (SOLI), pp. 160–165. Suzhou, China (2012). doi:10.1109/SOLI.2012.6273523

64.

Wei, G., Bogdan, P., Marculescu, R.: Efficient modeling and simulation of bacteria-based nanonetworks with BNSim. IEEE J. Select. Areas Commun. 31(12), 868–878 (2013). doi:10.1109/JSAC.2013.SUP2.12130019 CrossRef

65.

Wilensky, U.: NetLogo (1999). http://ccl.northwestern.edu/netlogo/

66.

Wilensky, U.: NetLogo heatbugs model (2004). http://ccl.northwestern.edu/netlogo/models/Heatbugs

67.

Wilensky, U., Rand, W.: Making models match: replicating an agent-based model. J. Artif. Soc. Soc. Simul. 10(4), 2 (2007). http://jasss.soc.surrey.ac.uk/10/4/2.html

68.

Yang, X.J., Liao, X.K., Lu, K., Hu, Q.F., Song, J.Q., Su, J.S.: The TianHe-1A supercomputer: its hardware and software. J. Comput. Sci. Technol. 26(3), 344–351 (2011). doi:10.1007/s02011-011-1137-8 CrossRef

69.

Yokokawa, M., Shoji, F., Uno, A., Kurokawa, M., Watanabe, T.: The K computer: Japanese next-generation supercomputer development project. In: Proceedings of the 17th IEEE/ACM International Symposium on Low-Power Electronics and Design, pp. 371–372 (2011). doi:10.1109/ISLPED.2011.5993668

Titel: Parallelization Strategies for Spatial Agent-Based Models
verfasst von: Nuno Fachada
Vitor V. Lopes
Rui C. Martins
Agostinho C. Rosa
Publikationsdatum: 19.01.2016
Verlag: Springer US
Erschienen in: International Journal of Parallel Programming / Ausgabe 3/2017
Print ISSN: 0885-7458
Elektronische ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-015-0399-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2017

Restart Optimization for Transactional Memory with Lazy Conflict Detection

Panda: A Compiler Framework for Concurrent CPUGPU Execution of 3D Stencil Computations on GPU-accelerated Supercomputers

RT-CUDA: A Software Tool for CUDA Code Restructuring

Scalable Loop Self-Scheduling Schemes for Large-Scale Clusters and Cloud Systems

A Parallel Approach for the Generation of Unstructured Meshes with Billions of Elements on Distributed-Memory Supercomputers

Porting the PLASMA Numerical Library to the OpenMP Standard