Implementação Paralela em C+CUDA de um Categorizador Multi-Rótulo de Texto Baseado no Algoritmo k-NN
Resumo
Em problemas de categorização automática de texto com um grande número de rótulos, as bases de dados de treinamento são grandes, o que pode tornar proibitivo o tempo de categorização para sistemas on-line. Neste trabalho avaliamos a implementação paralela em C+CUDA (Compute Unified Device Architecture) de um categorizador multi-rótulo de texto baseado no algoritmo k-NN (k-Nearest Neighbors). Nós implementamos este algoritmo de duas formas: seqüencial em C e paralela em C+CUDA. Nossos resultados experimentais mostram que, com o uso de GPUs (Graphics Processing Units) e C+CUDA, são possíveis ganhos de desempenho da ordem de 65 vezes o desempenho seqüencial alcançado com CPUs.Referências
F. D. Comité, R. Gilleron, and M. Tommasi, “Learning Multilabel Alternating Decision Tree from Texts and Data”, Lecture Notes in Computer Science 2734, 2003, pp. 35–49.
A. F. De Souza, F. Pedroni, E. Oliveira, P. M. Ciarelli, W. F. Henrique, L. Veronese, and C. Badue, “Automated Multi-label Text Categorization with VGRAM Weightless Neural Networks”, Neurocomputing 72(10-12), 2009, pp. 2209-2217.
S. Ding, J. He, H. Yah, and T. Suel, “Using Graphics Processors for High Performance IR Query Processing”, 18th Iinternational Conference on World Wide Web (WWW’08), 2008, pp. 421-430.
DNRC, “Ranking das Juntas Comerciais segundo Movimento de Constituição, Alteração e Extinção e Cancelamento de Empresas ”, Departamento Nacional de Registro do Comércio (DNRC), http://www.dnrc.gov.br/Estatisticas/ranking_2008.htm, último acesso em 09/07/2009.
A. Elisseeff and J. Weston, “A Kernel Method for Multilabelled Classification”, Advances in Neural Information Processing Systems 14, 2002, pp. 681–687.
S. Gao, W. Wu, C.-H. Lee, and T.-S. Chua, “A MFoM Learning Approach to Robust Multiclass Multi-label Text Categorization”, Proceedings of the 21st International Conference on Machine Learning, 2004, pp. 329–336.
V. Garcia, E. Debreuve, and M. Barlaud, “Fast k Nearest Neighbor Search Using GPU”, Computer Vision and Pattern Recognition Workshops, 2008, pp. 1–6.
N. Govindaraju, J. Gray, R. Kumar, and D. Manocha, “GPUTeraSort: High Performance Graphics Co-Processor Sorting for Large Database Management”, 26th ACM SIGMOD International Conference on Management of Data, 2006, pp. 325-336.
T. R. Halfhill, “Parallel Processing with CUDA: Nvidia's High-Performance Computing Platform Uses Massive Multithreading”, Microprocessor, January 2008.
IBGE, “Classificação Nacional de Atividades Econômicas - Fiscal (CNAE-Fiscal)”, Instituto Brasileiro de Geografia e Estatística (IBGE), Rio de Janeiro, RJ, 2003.
D. Luebke, M. Harris, J. Krüger, T. Purcell, N. Govindaraju, I. Buck, C. Woolley, A. Lefohn, “GPGPU: general purpose computation on graphics hardware”, International Conference on Computer Graphics and Interactive Techniques, ACM SIGGRAPH 2004, Course Notes, 2004.
D. Luebke, “GPU Computing: The Democratization of Parallel Computing”, 13th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’08), Course Notes, 2008.
C. D. Manning, P. Raghavan, and H. Schütze, “An Introduction to Information Retrieval”, Cambridge University Press, Cambridge, England, 2008.
MF, “Cadastro Sincronizado Nacional (CSN)”, Ministério da Fazenda, https://www16.receita.fazenda.gov.br/CadSinc/, último acesso em 06/07/2009.
NILC, “Diadorim: A Lexical Database for Brazilian Portuguese”, Núcleo Interinstitucional de Lingüística Computacional (NILC), http://www.nilc.icmc.usp.br/nilc/tools/intermed.htm, último acesso em 06/07/2009.
NVIDIA, “NVIDIA CUDA: Compute Unified Device Architecture - Programming Guide 2.0”, 2008.
NVIDIA, “Technical Brief: NVIDIA GeForce GTX 200 GPU Architectural Overview”, 2008.
NVIDIA, “CUDA CUBLAS Library”, 2008.
J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Krüger, A. E. Lefohn, and T. Purcell, "A Survey of General-Purpose Computation on Graphics Hardware", Computer Graphics Forum 26(1), 2007, pp. 80-113.
J. Owens, “Data-Parallel Algorithms and Data Structures”, Tutorial on http://gpgpu.org/feed High Performance Computing with CUDA, International Conference for High Performance Computing, Networking, Storage and Analysis, http://gpgpu.org/static/sc2007/SC07_CUDA_4_DataParallel_Owens.pdf, último acesso em 09/07/2009.
R. E. Schapire and Y. Singer, “BoosTexter: a Boosting-Based System for Text Categorization”, Machine Learning 39(2/3), 2000, pp. 135–168.
F. Sebastiani, “Machine Learning in Automated Text Categorization”, ACM Computing Surveys 34(1), 2002, pp. 1-47.
N. Ueda and K. Saito, “Parametric Mixture Models for Multilabel Text”, Advances in Neural Information Processing Systems 15, 2003, pp. 721–728.
M.-L. Zhang and Z.-H. Zhou, “ML-kNN: A Lazy Learning Approach to Multi-Label Learning”, Pattern Recognition 40(7), 2007, pp. 2038–2048.
A. F. De Souza, F. Pedroni, E. Oliveira, P. M. Ciarelli, W. F. Henrique, L. Veronese, and C. Badue, “Automated Multi-label Text Categorization with VGRAM Weightless Neural Networks”, Neurocomputing 72(10-12), 2009, pp. 2209-2217.
S. Ding, J. He, H. Yah, and T. Suel, “Using Graphics Processors for High Performance IR Query Processing”, 18th Iinternational Conference on World Wide Web (WWW’08), 2008, pp. 421-430.
DNRC, “Ranking das Juntas Comerciais segundo Movimento de Constituição, Alteração e Extinção e Cancelamento de Empresas ”, Departamento Nacional de Registro do Comércio (DNRC), http://www.dnrc.gov.br/Estatisticas/ranking_2008.htm, último acesso em 09/07/2009.
A. Elisseeff and J. Weston, “A Kernel Method for Multilabelled Classification”, Advances in Neural Information Processing Systems 14, 2002, pp. 681–687.
S. Gao, W. Wu, C.-H. Lee, and T.-S. Chua, “A MFoM Learning Approach to Robust Multiclass Multi-label Text Categorization”, Proceedings of the 21st International Conference on Machine Learning, 2004, pp. 329–336.
V. Garcia, E. Debreuve, and M. Barlaud, “Fast k Nearest Neighbor Search Using GPU”, Computer Vision and Pattern Recognition Workshops, 2008, pp. 1–6.
N. Govindaraju, J. Gray, R. Kumar, and D. Manocha, “GPUTeraSort: High Performance Graphics Co-Processor Sorting for Large Database Management”, 26th ACM SIGMOD International Conference on Management of Data, 2006, pp. 325-336.
T. R. Halfhill, “Parallel Processing with CUDA: Nvidia's High-Performance Computing Platform Uses Massive Multithreading”, Microprocessor, January 2008.
IBGE, “Classificação Nacional de Atividades Econômicas - Fiscal (CNAE-Fiscal)”, Instituto Brasileiro de Geografia e Estatística (IBGE), Rio de Janeiro, RJ, 2003.
D. Luebke, M. Harris, J. Krüger, T. Purcell, N. Govindaraju, I. Buck, C. Woolley, A. Lefohn, “GPGPU: general purpose computation on graphics hardware”, International Conference on Computer Graphics and Interactive Techniques, ACM SIGGRAPH 2004, Course Notes, 2004.
D. Luebke, “GPU Computing: The Democratization of Parallel Computing”, 13th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS’08), Course Notes, 2008.
C. D. Manning, P. Raghavan, and H. Schütze, “An Introduction to Information Retrieval”, Cambridge University Press, Cambridge, England, 2008.
MF, “Cadastro Sincronizado Nacional (CSN)”, Ministério da Fazenda, https://www16.receita.fazenda.gov.br/CadSinc/, último acesso em 06/07/2009.
NILC, “Diadorim: A Lexical Database for Brazilian Portuguese”, Núcleo Interinstitucional de Lingüística Computacional (NILC), http://www.nilc.icmc.usp.br/nilc/tools/intermed.htm, último acesso em 06/07/2009.
NVIDIA, “NVIDIA CUDA: Compute Unified Device Architecture - Programming Guide 2.0”, 2008.
NVIDIA, “Technical Brief: NVIDIA GeForce GTX 200 GPU Architectural Overview”, 2008.
NVIDIA, “CUDA CUBLAS Library”, 2008.
J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Krüger, A. E. Lefohn, and T. Purcell, "A Survey of General-Purpose Computation on Graphics Hardware", Computer Graphics Forum 26(1), 2007, pp. 80-113.
J. Owens, “Data-Parallel Algorithms and Data Structures”, Tutorial on http://gpgpu.org/feed High Performance Computing with CUDA, International Conference for High Performance Computing, Networking, Storage and Analysis, http://gpgpu.org/static/sc2007/SC07_CUDA_4_DataParallel_Owens.pdf, último acesso em 09/07/2009.
R. E. Schapire and Y. Singer, “BoosTexter: a Boosting-Based System for Text Categorization”, Machine Learning 39(2/3), 2000, pp. 135–168.
F. Sebastiani, “Machine Learning in Automated Text Categorization”, ACM Computing Surveys 34(1), 2002, pp. 1-47.
N. Ueda and K. Saito, “Parametric Mixture Models for Multilabel Text”, Advances in Neural Information Processing Systems 15, 2003, pp. 721–728.
M.-L. Zhang and Z.-H. Zhou, “ML-kNN: A Lazy Learning Approach to Multi-Label Learning”, Pattern Recognition 40(7), 2007, pp. 2038–2048.
Publicado
28/10/2009
Como Citar
VERONESE, Lucas; SOUZA, Alberto F. De; BADUE, Claudine; OLIVEIRA, Elias.
Implementação Paralela em C+CUDA de um Categorizador Multi-Rótulo de Texto Baseado no Algoritmo k-NN. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 10. , 2009, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2009
.
p. 145-152.
DOI: https://doi.org/10.5753/wscad.2009.17403.
