Paralelização Híbrida e em Múltiplos Níveis de um Algoritmo de Contabilização de Frequências de K-mer
Resumo
Este trabalho apresenta um estudo sobre o ganho de desempenho gerado com o aumento do nível de paralelismo de execução de um algoritmo de contabilização de k-mers de dados de amostras genômicas e metagenômicas. O algoritmo foi originalmente desenvolvido para permitir a execução em paralelo da contabilização de k-mers em uma arquitetura manycores de uma GPU. Neste trabalho apresentamos o ganho de desempenho ao implementarmos paralelismo para a execução paralela de módulos do algoritmo em múltiplos núcleos de uma CPU, em múltiplas GPU’s e em múltiplos nós de processamento de uma cluster híbrida.
Referências
Church, P. C., Goscinski, A., Holt, K., Inouye, M., Ghoting, A., Makarychev, K., and Reumann, M. (2011). Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers. In 2011 Annual International Conference of the IEEE Engineering in Medicine and Biology Society, pages 924–927. IEEE.
Coelho, M., Vilasboas, F., and Osthoff, C. (2016). Desenvolvimento de uma versão paralela híbrida para a contabilização da frequência de repetição de k-mers. ERAD-RJ Escola Regional de Alto Desempenho do Rio de Janeiro.
Edwards, R. A., Olson, R., Disz, T., Pusch, G. D., Vonstein, V., Stevens, R., and Overbeek, R. (2012). Real time metagenomics: using k-mers to annotate metagenomes. Bioinformatics, 28(24):3316–3317.
Erbert, M., Rechner, S., and Müller-Hannemann, M. (2017). Gerbil: a fast and memoryefcient k-mer counter with gpu-support. Algorithms for Molecular Biology, 12(1):9.
Fiannaca, A., La Rosa, M., Rizzo, R., and Urso, A. (2015). A k-mer-based barcode DNA classication methodology based on spectral representation and a neural gas network. Articial intelligence in medicine, 64(3):173–84.
Garg, A., Jain, A., and Paul, K. (2013). GGAKE: GPU Based Genome Assembly Using K-Mer Extension. In 2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing, pages 1105–1112. IEEE.
Marçais, G. and Kingsford, C. (2011). A fast, lock-free approach for efcient parallel counting ofoccurrences of k-mers. Bioinformatics (Oxford, England), 27(6):764–70.
Plaza Onate, F., Batto, J.-M., Juste, C., Fadlallah, J., Fougeroux, C., Gouas, D., Pons, N., Kennedy, S., Levenez, F., Dore, J., Ehrlich, S. D., Gorochov, G., and Larsen, M. (2015). Quality control of microbiota metagenomics by k-mer analysis. BMC genomics, 16(1):183.
Vilasboas, F., Osthoff, C., Trelles, O., and Vasconcelos, A. T. (2015). Desenvolvimento de um algoritmo paralelo para contabilização da repetição de k-mers. 3a Conferência Ibero Americana de Computação Aplicada 2015.
Vilasboas, F., Osthoff, C., Trelles, O., and Vasconcelos, A. T. (2016). Otimização de um algoritmo paralelo para contabilização da repetição de k-mers. II Escola Regional de Computação de Alto Desempenho do Rio de Janeiro.
Coelho, M., Vilasboas, F., and Osthoff, C. (2016). Desenvolvimento de uma versão paralela híbrida para a contabilização da frequência de repetição de k-mers. ERAD-RJ Escola Regional de Alto Desempenho do Rio de Janeiro.
Edwards, R. A., Olson, R., Disz, T., Pusch, G. D., Vonstein, V., Stevens, R., and Overbeek, R. (2012). Real time metagenomics: using k-mers to annotate metagenomes. Bioinformatics, 28(24):3316–3317.
Erbert, M., Rechner, S., and Müller-Hannemann, M. (2017). Gerbil: a fast and memoryefcient k-mer counter with gpu-support. Algorithms for Molecular Biology, 12(1):9.
Fiannaca, A., La Rosa, M., Rizzo, R., and Urso, A. (2015). A k-mer-based barcode DNA classication methodology based on spectral representation and a neural gas network. Articial intelligence in medicine, 64(3):173–84.
Garg, A., Jain, A., and Paul, K. (2013). GGAKE: GPU Based Genome Assembly Using K-Mer Extension. In 2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing, pages 1105–1112. IEEE.
Marçais, G. and Kingsford, C. (2011). A fast, lock-free approach for efcient parallel counting ofoccurrences of k-mers. Bioinformatics (Oxford, England), 27(6):764–70.
Plaza Onate, F., Batto, J.-M., Juste, C., Fadlallah, J., Fougeroux, C., Gouas, D., Pons, N., Kennedy, S., Levenez, F., Dore, J., Ehrlich, S. D., Gorochov, G., and Larsen, M. (2015). Quality control of microbiota metagenomics by k-mer analysis. BMC genomics, 16(1):183.
Vilasboas, F., Osthoff, C., Trelles, O., and Vasconcelos, A. T. (2015). Desenvolvimento de um algoritmo paralelo para contabilização da repetição de k-mers. 3a Conferência Ibero Americana de Computação Aplicada 2015.
Vilasboas, F., Osthoff, C., Trelles, O., and Vasconcelos, A. T. (2016). Otimização de um algoritmo paralelo para contabilização da repetição de k-mers. II Escola Regional de Computação de Alto Desempenho do Rio de Janeiro.
Publicado
17/10/2017
Como Citar
VILASBÔAS, Fabricio; COELHO, Micaella; OSTHOFF, Carla; OCAÑA, Kary; VASCONCELOS, Ana Tereza.
Paralelização Híbrida e em Múltiplos Níveis de um Algoritmo de Contabilização de Frequências de K-mer. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 18. , 2017, Campinas.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 100-111.
DOI: https://doi.org/10.5753/wscad.2017.242.
