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.
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