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.
Type de document :
Communication dans un congrès
SIGSIM-PADS’13 - ACM SIGSIM Conference on Principles of Advanced Discrete Simulation (PADS), May 2013, Montreal, Canada. pp.169 - 177, 2013, 〈10.1145/2486092.2486114〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01098546
Contributeur : Jonathan Passerat-Palmbach <>
Soumis le : mercredi 31 décembre 2014 - 17:33:11
Dernière modification le : jeudi 20 juillet 2017 - 09:28:30
Document(s) archivé(s) le : mercredi 1 avril 2015 - 10:06:18

Fichiers

pads2013_frree.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

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, 2013, 〈10.1145/2486092.2486114〉. 〈hal-01098546〉

Partager

Métriques

Consultations de
la notice

427

Téléchargements du document

112