Abstract
We consider the problem of simulating spatially distributed entities which can move, see each other, and react accordingly. We provide centralized reference algorithms for both time-stepped and discrete-event simulation. Under reasonable assumptions, we then proceed to distribute the simulation among several nodes by assigning each node a subregion of the simulation space. A main characteristic of our approach is that the subregions do not form a partitioning, but a covering. That is, they partially overlap, hence causing some duplicated computation, which is apparently redundant. The amount of overlapping is a tunable parameter of our algorithms, which affects the overall performance in a non-trivial way. Through an analytical model as well as experimental results we discover a trade-off. Choosing a small overlapping requires to perform frequent synchronizations, which negatively affect performance. However, a large overlapping leads to more duplicated work, which also decreases performance. Balancing the amount of overlapping is then required to optimize performance.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Banks J, Carson J, Nelson BL and Nicol D (2004). Discrete-Event System Simulation, Fourth Edition. Prentice-Hall.
Bartocci E et al. (2010). Shape calculus. A spatial mobile calculus for 3D shapes. Scientific Annals of Computer Science 20: 1–31.
Bittig AT and Uhrmacher AM (2010). Spatial modeling in cell biology at multiple levels. In: Winter Simulation Conference (WSC) 2010. IEEE Computer Society: Washington, DC, pp 608–619.
Degano P, Prandi D, Priami C and Quaglia P (2006). Beta-binders for biological quantitative experiments. Electronic Notes in Theoretical Computer Science 164 (3): 101–117.
Elf J and Ehrenberg M (2004). Spontaneous separation of bi-stable biochemical systems into spatial domains of opposite phases. Systems Biology 1 (2): 230–236.
Gibson MA and Bruck J (2000). Efficient exact stochastic simulation of chemical systems with many species and many channels. Journal of Physical Chemistry A 104 (9): 1876–1889.
Gillespie DT (1977). Exact stochastic simulation of coupled chemical reactions. Journal of Physical Chemistry 81 (25): 2340–2361.
Huang YL, Alexopoulos C, Fujimoto R and Hunter M (2011). On the accuracy of ad hoc distributed simulations for open queueing network. In: Principles of Advanced and Distributed Simulation (PADS) 2011. IEEE Computer Society: Silver Spring, MD.
Jefferson DR (1985). Virtual time. AM Transactions on Programming Languages and Systems 7 (3): 404–425.
Jeschke M et al. (2008). Parallel and distributed spatial simulation of chemical reactions. In: Principles of Advanced and Distributed Simulation (PADS) 2008. IEEE Computer Society, Silver Spring, MD: Washington, DC, pp 51–59.
Preneel B (1993). Analysis and design of cryptographic hash functions PhD Thesis, Katholieke Universiteit Leuven.
John M, Ewald R and Uhrmacher AM (2008). A spatial extension to the π calculus. Electronic Notes in Theoretical Computer Science 194 (3): 133–148.
Leye S, Uhrmacher A and Priami C (2008). A bounded-optimistic, parallel beta-binders simulator. In: Roberts D, El Saddik A, Ferscha A (eds). Distributed Simulation and Real-Time Applications (DS-RT) 2008, IEEE Computer Society: Los Alamitos, CA, pp 139–148.
Liu C and Cai W (2011). Collaborative interest management for peer-to-peer networked virtual environment. In: Principles of Advanced and Distributed Simulation (PADS) 2011. IEEE Computer Society, Silver Spring, MD: Washington, DC, pp 1–10.
Pawlikowski K, Yau V and McNickle D (1994). Distributed stochastic discrete-event simulation in parallel times streams. In: Manivannan M, Tew J (eds). Winter Simulation Conference (WSC) 1994. Society for Computer Simulation International: San Diego, CA, pp 723–730.
Rodriguez JV, Kaandorp J, Dobrzynski M and Blom J (2006). Spatial stochastic modelling of the phosphoenolpyruvate-dependent phosphotransferase (PTS) pathway in escherichia coli. Bioinformatics 22 (15): 1895–1901.
Srinivasan A, Mascagni M and Ceperley D (2003). Testing parallel random number generators. Parallel Computing 29 (1): 69–94.
Takahashi K, Nanda S, Arjunan V and Tomita M (2005). Space in systems biology of signaling pathways: Towards intracellular molecular crowding in silico. FEBS letters 579 (8): 1783–1788.
Tan C (2001). On parallel pseudo-random number generation. In: Alexandrov V, Dongarra J, Juliano B, Renner R, Tan C (eds). Computational Science ICCS 2001. Vol. 2073, Lecture Notes in Computer Science Springer: London, NY, pp 589–596.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zunino, R. On computation and synchronization costs in spatial distributed simulation. J Simulation 6, 193–204 (2012). https://doi.org/10.1057/jos.2012.9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jos.2012.9