Operações Paralelas sobre Bases Massivas de Strings
Resumo
Este trabalho analisa operações básicas comumente utilizadas em algoritmos de recuperação de dados textuais com o intuito de se beneficiar da arquitetura paralela CUDA da NVIDIA. Quatro operações diferentes foram implementadas e comparadas com suas implementações em CPU: busca exata e aproximada de strings, substituição de caracteres e cálculo de frequência de termos. Diferentes testes foram realizados variando o tamanho da base de dados, o tamanho da palavra procurada e o número de ocorrências da mesma na base. Foi possível obter uma melhora de desempenho na maioria dos cenários analisados. Uma das operações foi usada para buscar palavras no banco de dados do Diário Oficial da União, sendo possível obter um speedup de 13 vezes quando comparado com a solução online em CPU.
Palavras-chave:
busca paralela de strings, GPGPU
Referências
Charalampos S Kouzinopoulos and Konstantinos G Margaritis. String matching on a multicore gpu using cuda. In Informatics, 2009. PCI’09. 13th Panhellenic Conference on, pages 14–18. IEEE, 2009.
Raymond Tay. Demonstration of Exact String Matching Algorithms using CUDA. Unpublished work.
Yu Liu, Longjiang Guo, Jinbao Li, Meirui Ren, and Keqin Li. Parallel algorithms for approximate string matching with k mismatches on cuda. In Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International, pages 2414–2422. IEEE, 2012.
Svetlin A Manavski and Giorgio Valle. Cuda compatible gpu cards as efficient hardware accelerators for smith-waterman sequence alignment. BMC bioinformatics, 9(Suppl 2):S10, 2008.
Naga K Govindaraju, Brandon Lloyd, Wei Wang, Ming Lin, and Dinesh Manocha. Fast computation of database operations using graphics processors. In Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pages 215–226. ACM, 2004.
Wenbin Fang, Bingsheng He, Qiong Luo, and Naga K Govindaraju. Mars: Accelerating mapreduce with graphics processors. Parallel and Distributed Systems, IEEE Transactions on, 22(4):608–620, 2011.
Peter Wittek and S´andor Dar´anyi. Accelerating text mining workloads in a mapreduce-based dis tributed gpu environment. Journal of Parallel and Distributed Computing, 2012.
Donald E Knuth, James H Morris, Jr, and Vaughan R Pratt. Fast pattern matching in strings. SIAM journal on computing, 6(2):323–350, 1977.
Jorma Tarhio and Esko Ukkonen. Boyer-moore approach to approximate string matching. In SWAT 90, pages 348–359. Springer, 1990.
Christopher D Manning, Prabhakar Raghavan, and Hinrich Schutze. Introduction to information retrieval, volume 1. Cambridge University Press Cambridge, 2008.
Imprensa Nacional. Diário oficial da união, July 2013.
Dan A Alcantara, Andrei Sharf, Fatemeh Abbasinejad, Shubhabrata Sengupta, Michael Mitzenmacher, John D Owens, and Nina Amenta. Real-time parallel hashing on the gpu. In ACM Transactions on Graphics (TOG), volume 28, page 154. ACM, 2009.
TR Lynam, CLA Clarke, and GV Cormack. Information extraction with term frequencies. In Proceedings of the first international conference on Human language technology research, pages 1–4. Association for Computational Linguistics, 2001.
Jason Sanders and Edward Kandrot. CUDA by example: an introduction to general-purpose GPU programming. Addison-Wesley Professional, 2010.
Peter Bakkum and Kevin Skadron. Accelerating sql database operations on a gpu with cuda. In Proceedings of the 3rd Workshop on General-Purpose Computation on Graphics Processing Units, pages 94–103. ACM, 2010.
Knuth, Donald E.; Morris, JR, James H.; Pratt, Vaughan R. Fast pattern matching in strings. SIAM journal on computing, v. 6, n. 2, p. 323-350, 1977.
Boyer, Robert S.; Moore, J. Strother. A fast string searching algorithm. Communications of the ACM, v. 20, n. 10, p. 762-772, 1977.
Aho, Alfred V.; Corasick, Margaret J. Efficient string matching: an aid to bibliographic search. Communications of the ACM, v. 18, n. 6, p. 333-340, 1975.
Commentz-Walter, Beate. A string matching algorithm fast on the average. Springer Berlin Heidelberg, 1979.
Karp, Richard M.; Rabin, Michael O. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, v. 31, n. 2, p. 249-260, 1987.
NVIDIA CUDA Compute Unified Device Architecture - CUDA C Programming Guide, 2012
Raymond Tay. Demonstration of Exact String Matching Algorithms using CUDA. Unpublished work.
Yu Liu, Longjiang Guo, Jinbao Li, Meirui Ren, and Keqin Li. Parallel algorithms for approximate string matching with k mismatches on cuda. In Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International, pages 2414–2422. IEEE, 2012.
Svetlin A Manavski and Giorgio Valle. Cuda compatible gpu cards as efficient hardware accelerators for smith-waterman sequence alignment. BMC bioinformatics, 9(Suppl 2):S10, 2008.
Naga K Govindaraju, Brandon Lloyd, Wei Wang, Ming Lin, and Dinesh Manocha. Fast computation of database operations using graphics processors. In Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pages 215–226. ACM, 2004.
Wenbin Fang, Bingsheng He, Qiong Luo, and Naga K Govindaraju. Mars: Accelerating mapreduce with graphics processors. Parallel and Distributed Systems, IEEE Transactions on, 22(4):608–620, 2011.
Peter Wittek and S´andor Dar´anyi. Accelerating text mining workloads in a mapreduce-based dis tributed gpu environment. Journal of Parallel and Distributed Computing, 2012.
Donald E Knuth, James H Morris, Jr, and Vaughan R Pratt. Fast pattern matching in strings. SIAM journal on computing, 6(2):323–350, 1977.
Jorma Tarhio and Esko Ukkonen. Boyer-moore approach to approximate string matching. In SWAT 90, pages 348–359. Springer, 1990.
Christopher D Manning, Prabhakar Raghavan, and Hinrich Schutze. Introduction to information retrieval, volume 1. Cambridge University Press Cambridge, 2008.
Imprensa Nacional. Diário oficial da união, July 2013.
Dan A Alcantara, Andrei Sharf, Fatemeh Abbasinejad, Shubhabrata Sengupta, Michael Mitzenmacher, John D Owens, and Nina Amenta. Real-time parallel hashing on the gpu. In ACM Transactions on Graphics (TOG), volume 28, page 154. ACM, 2009.
TR Lynam, CLA Clarke, and GV Cormack. Information extraction with term frequencies. In Proceedings of the first international conference on Human language technology research, pages 1–4. Association for Computational Linguistics, 2001.
Jason Sanders and Edward Kandrot. CUDA by example: an introduction to general-purpose GPU programming. Addison-Wesley Professional, 2010.
Peter Bakkum and Kevin Skadron. Accelerating sql database operations on a gpu with cuda. In Proceedings of the 3rd Workshop on General-Purpose Computation on Graphics Processing Units, pages 94–103. ACM, 2010.
Knuth, Donald E.; Morris, JR, James H.; Pratt, Vaughan R. Fast pattern matching in strings. SIAM journal on computing, v. 6, n. 2, p. 323-350, 1977.
Boyer, Robert S.; Moore, J. Strother. A fast string searching algorithm. Communications of the ACM, v. 20, n. 10, p. 762-772, 1977.
Aho, Alfred V.; Corasick, Margaret J. Efficient string matching: an aid to bibliographic search. Communications of the ACM, v. 18, n. 6, p. 333-340, 1975.
Commentz-Walter, Beate. A string matching algorithm fast on the average. Springer Berlin Heidelberg, 1979.
Karp, Richard M.; Rabin, Michael O. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, v. 31, n. 2, p. 249-260, 1987.
NVIDIA CUDA Compute Unified Device Architecture - CUDA C Programming Guide, 2012
Publicado
23/10/2013
Como Citar
BRITO, Caio José dos Santos; COSTA, Lucas Galindo; TEIXEIRA, João Marcelo X. N.; TEICHRIEB, Veronica.
Operações Paralelas sobre Bases Massivas de Strings . In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 14. , 2013, Porto de Galinhas.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 77-83.
DOI: https://doi.org/10.5753/wscad.2013.16776.
