Abstract
The parallel simulation of biochemical reactions is a very interesting problem: biochemical systems are inherently parallel, yet the majority of the algorithms to simulate them, including the well-known and widespread Gillespie SSA, are strictly sequential. Here we investigate, in a general way, how to characterize the simulation of biochemical systems in terms of Discrete Event Simulation. We dissect their inherent parallelism in order both to exploit the work done in this area and to speed-up their simulation. We study the peculiar characteristics of discrete biological simulations in order to select the parallelization technique which provides the greater benefits, as well as to touch its limits. We then focus on reaction-diffusion systems: we design and implement an efficient parallel algorithm for simulating such systems that include both reactions between entities and movements throughout the space.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Fujimoto, R.M.: Parallel discrete event simulation. Comm. ACM 33(10), 30–53 (1990)
Ewing, G.C., McNickle, D., Pawlikowski, L.: Multiple replications in parallel: Distributed generation of data for speeding up quantitative stochastic simulation. In: Proceedings of the 15th Congress of Int. Association for Matemathics and Computer in Simulation, pp. 397–402 (1997)
Glynn, P.W., Heidelberger, P.: Analysis of initial transient deletion for parallel steady-state simulations. SIAM J. Scientific Stat. Computing 13(4), 904–922 (1992)
Newman, M.E.J., Barkema, G.T.: Monte Carlo Methods in Statistical Physics. Oxford University Press, Oxford (2000)
Glynn, P.W., Heidelberger, P.: Analysis of parallel replicated simulations under a completion time constraint. ACM TOMACS 1(1), 3–23 (1991)
Glynn, P.W., Heidelberger, P.: Experiments with initial transient deletion for parallel, replicated steady-state simulations. Management Science 38(3), 400–418 (1992)
Lin, Y.B.: Parallel independent replicated simulation on a network of workstations. ACM SIGSIM Simulation Digest 24(1), 73–80 (1994)
Yau, V.: Automating parallel simulation using parallel time streams. ACM TOMACS 9(2), 171–201 (1999)
Hybinette, M., Fujimoto, R.M.: Cloning parallel simulations. ACM TOMACS 11(4), 378–407 (2001)
Bononi, L., Bracuto, M., D’Angelo, G., Donatiello, L.: Concurrent replication of parallel and distributed simulation. In: Proceedings of the 19th ACM/IEEE/SCS PADS Workshop, pp. 430–436 (2005)
Streltsov, S., Vakili, P.: Parallel replicated simulation of markov chains: implementation and variance reduction. In: Proceedings of the 25th conference on Winter simulation, pp. 430–436 (1993)
Tian, T., Burrage, K.: Parallel implementation of stochastic simulation for large-scale cellular processes. In: Proceedings of of Eighth International Conference on High-Performance Computing in Asia-Pacific Region, pp. 621–626 (2005)
Burrage, K., Burrage, P.M., Hamilton, N., Tian, T.: Computer-intensive simulations for cellular models. In: Parallel Computing in Bioinformatics and Computational Biology, pp. 79–119 (2006)
Schwehm, M.: Parallel stochastic simulation of whole-cell models. In: Proceedings of ICSB, pp. 333–341 (2001)
Mazza, T., Guido, R.: Guidelines for parallel simulation of biological reactive systems. In: Proceedings of NETTAB 2008, Bioinformatics Methods for Biomedical Complex System Applications, pp. 83–85 (2008)
Gillespie, D.: A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. J. Phys. Chem. 22, 403–434 (1976)
Gillespie, D.: Exact stochastic simulation of coupled chemical reactions. Journal of Physical Chemistry 81(25), 2340–2361 (1977)
McCammon, J.A., Harvey, S.C.: Dynamics of Proteins and Nucleic Acids. Cambridge University Press, Cambridge
Andrews, S.S., Bray, D.: Stochastic simulation of chemical reactions with spatial resolution and single molecule detail. Phys. Biol. (1), 137–151 (2004)
Bernstein, D.: Exact stochastic simulation of coupled chemical reactions. PHYSICAL REVIEW E 71 (April 2005)
Elf, J., Ehrenberg, M.: Spontaneous separation of bi-stable biochemical systems into spatial domains of opposite phases. Syst. Biol. 1(2) (December 2004)
Gibson, M., Bruck, J.: Efficient exact stochastic simulation of chemical systems with many species and many channels. J. Phys. Chem. 104, 1876–1889 (2000)
Ferscha, A.: Parallel and Distributed Simulation of Discrete Event Systems. McGraw-Hill, New York (1996)
Chandy, K.M., Misra, J.: Distributed simulation: A case study in design and verification of distributed programs. Comm. ACM 24(11), 198–206 (1981)
Chandy, K.M., Misra, J.: Asynchronous distributed simulation via a sequence of parallel computations. IEEE Trans. on Software Engineering SE-5(5), 440–452 (1979)
Jefferson, D.R.: Virtual time. ACM Transactions on Programming Languages and Computer Systems 7(3), 404–425 (1985)
Holt, R.C.: Some deadlock properties of computer systems. ACM Computing Surveys 4(3), 179–196 (1972)
Cai, W., Turner, S.J.: An algorithm for distributed discrete-event simulation - the ’carrier null message’ approach. In: Proceedings of the SCS Multiconference on Distributed Simulation, vol. 22, pp. 3–8 (1990)
Wood, K.R., Turner, S.J.: A generalized carrier-null method for conservative parallel simulation. In: Proceedings of the 8th PADS Workshop, pp. 50–57 (1994)
Bain, W.L., Scott, D.S.: An algorithm for time synchronization in distributed discret event simulation. In: Proceedings of the SCS Multiconference on Distributed Simulation, vol. 19, pp. 30–33 (1988)
Groselj, B., Tropper, C.: The time-of-next-event algorithm. In: Proceedings of the SCS Multiconference on Distributed Simulation, vol. 19, pp. 25–29 (1988)
Cota, B.A., Sargent, R.G.: A framework for automatic lookahead computation in conservative distributed simulations. In: Proceedings of the SCS Multiconference on Distributed Simulation, vol. 22, pp. 56–59 (1990)
Prakash, A., Ramamoorthy, C.V.: Hierarchical distributed simulations. In: Proceedings of the 8th International Conference on Distributed Computing Systems, pp. 341–348 (1988)
Rukoz, M.: Hierarchical deadlock detection for nested transactions. Distributed Computing 4, 123–129 (1991)
Jeschke, M., Ewald, R., Park, A., Fujimoto, R., Uhrmacher, A.: Parallel and distributed spatial simulation of chemical reactions. In: Proceedings of the 22nd ACM/IEEE/SCS PADS Workshop (2008)
Nicol, D.M.: Parallel discrete-event simulation of fcfs stochastic queueing networks. SIGPLAN Not. 23(9), 124–137 (1988)
Loper, M.L., Fujimoto, R.M.: Pre-sampling as an approach for exploiting temporal uncertainty. In: PADS 2000, pp. 157–164 (2000)
Ridwan, A., Krishnan, A., Dhar, P.: A parallel implementation of gillespie’s direct method. In: Bubak, M., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds.) ICCS 2004. LNCS, vol. 3037, pp. 284–291. Springer, Heidelberg (2004)
Schinazi, R.B.: Predator-prey and host-parasite spatial stochastic models. The Annals of Applied Probability 7(1), 1–9 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dematté, L., Mazza, T. (2008). On Parallel Stochastic Simulation of Diffusive Systems. In: Heiner, M., Uhrmacher, A.M. (eds) Computational Methods in Systems Biology. CMSB 2008. Lecture Notes in Computer Science(), vol 5307. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88562-7_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-88562-7_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88561-0
Online ISBN: 978-3-540-88562-7
eBook Packages: Computer ScienceComputer Science (R0)