An efficient GPU acceptance-rejection algorithm for the selection of the next reaction to occur for Stochastic Simulation Algorithms

Neri Mickael, Denis Mestivier
Institut Jacques Monod, CNRS UMR 7592, Universite Paris Diderot, Paris Cite Sorbonne, Paris, France
arXiv:1404.0027 [cs.CE], (28 Mar 2014)


   author={Mickael}, N. and {Mestivier}, D.},

   title={"{An efficient GPU acceptance-rejection algorithm for the selection of the next reaction to occur for Stochastic Simulation Algorithms}"},

   journal={ArXiv e-prints},




   keywords={Computer Science – Computational Engineering, Finance, and Science, Computer Science – Distributed, Parallel, and Cluster Computing},




   adsnote={Provided by the SAO/NASA Astrophysics Data System}


Download Download (PDF)   View View   Source Source   



MOTIVATION: The Stochastic Simulation Algorithm (SSA) has largely diffused in the field of systems biology. This approach needs many realizations for establishing statistical results on the system under study. It is very computationnally demanding, and with the advent of large models this burden is increasing. Hence parallel implementation of SSA are needed to address these needs. At the very heart of the SSA is the selection of the next reaction to occur at each time step, and to the best of our knowledge all implementations are based on an inverse transformation method. However, this method involves a random number of steps to select this next reaction and is poorly amenable to a parallel implementation. RESULTS: Here, we introduce a parallel acceptance-rejection algorithm to select the K next reactions to occur. This algorithm uses a deterministic number of steps, a property well suited to a parallel implementation. It is simple and small, accurate and scalable. We propose a Graphics Processing Unit (GPU) implementation and validate our algorithm with simulated propensity distributions and the propensity distribution of a large model of yeast iron metabolism. We show that our algorithm can handle thousands of selections of next reaction to occur in parallel on the GPU, paving the way to massive SSA. AVAILABILITY: We present our GPU-AR algorithm that focuses on the very heart of the SSA. We do not embed our algorithm within a full implementation in order to stay pedagogical and allows its rapid implementation in existing software. We hope that it will enable stochastic modelers to implement our algorithm with the benefits of their own optimizations.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: