Parallel stepwise stochastic simulation: Harnessing GPUs to Explore Possible Futures States of a Chromosome Folding Model Thanks to the Possible Futures Algorithm (PFA)

Abstract : For the sake of software compatibility, simulations are often parallelized without much code rewriting. Performances can be further improved by optimizing codes so that to use the maximum power offered by parallel architectures. While this approach can provide some speed-up, performance of parallelized codes can be strongly limited a priori because traditional algorithms have been designed for sequential technologies. Thus, additional increase of performance should ultimately rely on some redesign of algorithms. Here, we redesign an algorithm that has traditionally been used to simulate the folding proper- ties of polymers. We address the issue of performance in the context of biological applications, more particularly in the active field of chromosome modelling. Due to the strong confinement of chromosomes in the cells, simulation of their motion is slowed down by the laborious search for the next valid states to progress. Our redesign, that we call the Possible Futures Algorithm (PFA), relies on the parallel computation of possible evolutions of the same state, which effectively increases the probability to obtain a valid state at each step. We apply PFA on a GPU-based architecture, allowing us to optimally reduce the latency induced by the computation overhead of possible futures. We show that compared to the initial sequential model the acceptance rate of new states significantly increases without impacting the execution time. In particular, the stronger the confinement of the chromosome, the more efficient PFA becomes, making our approach appealing for biological applications. While most of our results were obtained using Fermi architecture GPUs from NVIDIA, we highlight improved performance on the cutting-edge Kepler architecture K20 GPUs.
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01098546
Contributor : Jonathan Passerat-Palmbach <>
Submitted on : Wednesday, December 31, 2014 - 5:33:11 PM
Last modification on : Tuesday, May 14, 2019 - 10:14:55 AM
Long-term archiving on : Wednesday, April 1, 2015 - 10:06:18 AM

Files

pads2013_frree.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Jonathan Passerat-Palmbach, Jonathan Caux, Yannick Le Pennec, Romain Reuillon, Ivan Junier, et al.. Parallel stepwise stochastic simulation: Harnessing GPUs to Explore Possible Futures States of a Chromosome Folding Model Thanks to the Possible Futures Algorithm (PFA). SIGSIM-PADS’13 - ACM SIGSIM Conference on Principles of Advanced Discrete Simulation (PADS), May 2013, Montreal, Canada. pp.169 - 177, ⟨10.1145/2486092.2486114⟩. ⟨hal-01098546⟩

Share

Metrics

Record views

1654

Files downloads

212