Parallelization on graphic hardware : contributions to RNA folding and sequence alignment

Guillaume Rizk 1
1 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Résumé : La bioinformatique nécessite l'analyse de grandes quantités de données. Avec l'apparition de nouvelles technologies permettant un séquençage à haut débit à bas coût, la puissance de calcul requise pour traiter les données a énormément augmenté.. Cette thèse examine la possibilité d'utiliser les processeurs graphiques (GPU) pour des applications de bioinformatique. Dans un premier temps, ce travail s'intéresse au calcul des structures secondaires d'ARN. Ce problème est en général calculé par programmation dynamique, avec un algorithme qui pose de sérieux problèmes pour un code GPU. Nous introduisons une nouvelle implémentation tuilée qui fait apparaitre une bonne localité mémoire, permettant ainsi un programme GPU très efficace. Cette modification permet également de vectoriser le code CPU et donc de faire une comparaison honnête des performances entre GPU et CPU. Dans un deuxième temps, ce travail aborde le problème d'alignements de séquences. Nous présentons une parallélisation GPU d'une méthode utilisant une indexation par graines. L' implémentation sur GPU n'étant pas efficace, nous nous tournons vers le développement d'une version CPU. Notre contribution principale est le développement d'un nouvel algorithme éliminant rapidement les nombreux alignements potentiels, basé sur le précalcul de portions de la matrice de programmation dynamique. Ce nouvel algorithme a conduit au développement d'un nouveau programme d'alignement très efficace. Notre travail fournit l'exemple de deux problèmes différents dont seulement un a pu être efficacement parallélisé sur GPU. Ces deux expériences nous permettent d'évaluer l'efficacité des GPU et leur place en bioinformatique.
Type de document :
Thèse
Computer Science [cs]. Université Rennes 1, 2011. English. 〈NNT : 2011REN1S021〉
Liste complète des métadonnées

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

https://tel.archives-ouvertes.fr/tel-00634901
Contributeur : Sébastien Erhel <>
Soumis le : lundi 24 octobre 2011 - 11:47:47
Dernière modification le : vendredi 16 novembre 2018 - 01:25:23
Document(s) archivé(s) le : jeudi 15 novembre 2012 - 10:22:12

Identifiants

  • HAL Id : tel-00634901, version 1

Citation

Guillaume Rizk. Parallelization on graphic hardware : contributions to RNA folding and sequence alignment. Computer Science [cs]. Université Rennes 1, 2011. English. 〈NNT : 2011REN1S021〉. 〈tel-00634901〉

Partager

Métriques

Consultations de la notice

462

Téléchargements de fichiers

316