Perfect Hashing Structures for Parallel ...
Type de document :
Communication dans un congrès avec actes
DOI :
Titre :
Perfect Hashing Structures for Parallel Similarity Searches
Auteur(s) :
Tran, Tuan Tu [Auteur]
Johannes Gutenberg - Universität Mainz = Johannes Gutenberg University [JGU]
Giraud, Mathieu [Auteur]
Bioinformatics and Sequence Analysis [BONSAI]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Varré, Jean-Stéphane [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Bioinformatics and Sequence Analysis [BONSAI]
Johannes Gutenberg - Universität Mainz = Johannes Gutenberg University [JGU]
Giraud, Mathieu [Auteur]
Bioinformatics and Sequence Analysis [BONSAI]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Varré, Jean-Stéphane [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Bioinformatics and Sequence Analysis [BONSAI]
Titre de la manifestation scientifique :
International Workshop on High Performance Computational Biology (HiCOMB 2015) / International Parallel and Distributed Processing Symposium (IPDPS 2015)
Ville :
Hyderabad
Pays :
Inde
Date de début de la manifestation scientifique :
2015
Date de publication :
2015
Mot(s)-clé(s) en anglais :
OpenCL
GPU
parallelism
perfect hash function
read mapper
seed-based heuristics
GPU
parallelism
perfect hash function
read mapper
seed-based heuristics
Discipline(s) HAL :
Informatique [cs]/Bio-informatique [q-bio.QM]
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Résumé en anglais : [en]
Seed-based heuristics have proved to be efficient for studying similarity between genetic databases with billions of base pairs. This paper focuses on algorithms and data structures for the filtering phase in seed-based ...
Lire la suite >Seed-based heuristics have proved to be efficient for studying similarity between genetic databases with billions of base pairs. This paper focuses on algorithms and data structures for the filtering phase in seed-based heuristics, with an emphasis on efficient parallel GPU/manycores implementa- tion. We propose a 2-stage index structure which is based on neighborhood indexing and perfect hashing techniques. This structure performs a filtering phase over the neighborhood regions around the seeds in constant time and avoid as much as possible random memory accesses and branch divergences. Moreover, it fits particularly well on parallel SIMD processors, because it requires intensive but homogeneous computational operations. Using this data structure, we developed a fast and sensitive OpenCL prototype read mapper.Lire moins >
Lire la suite >Seed-based heuristics have proved to be efficient for studying similarity between genetic databases with billions of base pairs. This paper focuses on algorithms and data structures for the filtering phase in seed-based heuristics, with an emphasis on efficient parallel GPU/manycores implementa- tion. We propose a 2-stage index structure which is based on neighborhood indexing and perfect hashing techniques. This structure performs a filtering phase over the neighborhood regions around the seeds in constant time and avoid as much as possible random memory accesses and branch divergences. Moreover, it fits particularly well on parallel SIMD processors, because it requires intensive but homogeneous computational operations. Using this data structure, we developed a fast and sensitive OpenCL prototype read mapper.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- http://www.hicomb.org/papers/HICOMB2015-01.pdf
- Accès libre
- Accéder au document
- HICOMB2015-01.pdf
- Accès libre
- Accéder au document