GANHO DE DESEMPENHO DO FEMA UTILIZANDO PROGRAMAÇÃO PARALELA E ÁRVORES DE PARTICIONAMENTO ESPACIAL

  • Carlos Adriano Miranda Universidade do Oeste Paulista - Unoeste
  • Silvio Carro Universidade do Oeste Paulista - Unoeste
  • Danillo Roberto Pereira Faculdade de Informática de Presidente Prudente (FIPP) – Unoeste
Palavras-chave: FEMa, GPU, Kd-Tree, K-NN

Resumo

O presente estudo apresenta a  utilização de estruturas de dados e GPU como uma melhoria de desempenho do algoritmo de classificação FEMa. Primeiramente, à partir de um datasets  é criada uma árvore de partição binária do tipo Kd-Tree e após sua construção, aplicado o algoritmo de busca dos K vizinhos mais próximos (K-NN) na Kd-Tree para cada amostra de teste apresentada na fase de classificação. Após ter o resultado da busca das amostras mais próximas, é feita a etapa de classificação do FEMa aplicando uma base dos Métodos dos Elementos Finitos (FEM), para trazer o resultado. Outra abordagem é utilizar códigos CUDA no algoritmo do FEMa, para que o mesmo seja paralelizado e executado em GPU’s, para obter um ganho de desempenho no tempo de execução.

Downloads

Não há dados estatísticos.

Biografia do Autor

Danillo Roberto Pereira, Faculdade de Informática de Presidente Prudente (FIPP) – Unoeste

Possui graduação em Ciência da Computação pela FCT-UNESP (2006) ; mestrado em Ciência da Computação pela UNICAMP (2009); e doutorado pela UNICAMP. Tem experiência na área de Ciência da Computação, com ênfase em Geometria Computacional, Computação Gráfica e Visão Computacional. lattes.cnpq.br/0122307432250869

Referências

AMARIS, M. et al. A Simple BSP-based Model to Predict Execution Time in GPU Applications. 2015 Ieee 22nd International Conference On High Performance Computing (hipc), [s.l.], p.285-294, dez. 2015. IEEE. http://dx.doi.org/10.1109/hipc.2015.34.

BENTLEY, J. L. Multidimensional binary search trees used for associative searching. Communications Of The ACM, [s.l.], v. 18, n. 9, p.509-517, set. 1975. http://dx.doi.org/10.1145/361002.361007.

FARIAS, M. A. Operações booleanas entre objetos delimitados por surfels usando constrained BSP-trees. 2006. Dissertação (Mestrado) - Curso de Computação, Instituto de Informática, Universidade Federal do Rio Grande do Sul, Rio Grande do Sul, 2006. Cap. 2. Disponível em: http://hdl.handle.net/10183/7081. Acesso em: 20 set. 2017.

FOLEY, T.; SUGERMAN, J. KD-tree acceleration structures for a GPU raytracer. In: ACM SIGGRAPH/ EUROGRAPHICS CONFERENCE ON GRAPHICS HARDWARE, 5., 2005, Los Angeles, Ca, Usa. Proceeding. Los Angeles, California: Acm, 2005. p. 15 - 22. Disponível em: https://graphics.stanford.edu/papers/ gpu_kdtree/kdtree.pdf. Acesso em: 13 set. 2017. https://doi.org/10.1145/1071866.1071869

GARCIA, V.; DEBREUVE, E.; BARLAUD, M.. Fast k nearest neighbor search using GPU. 2008 Ieee Computer Society Conference On Computer Vision And Pattern Recognition Workshops, [s.l.], p.1-6, jun. 2008. IEEE. http://dx.doi.org/10.1109/cvprw.2008.4563100.

IZE, T.; WALD, I.; PARKER, S. G.. Ray tracing with the BSP tree. 2008 Ieee Symposium On Interactive Ray Tracing, [s.l.], p.159-166, ago. 2008. IEEE. https://doi.org/10.1109/RT.2008.4634637.

JIANG, H.; HALLSTROM, J. O.. Fast, Accurate Event Classification on Resource-Lean Embedded Sensors. Acm Transactions On Autonomous And Adaptive Systems, [s.l.], v. 8, n. 2, p.1-22, 1 jul. 2013. http://dx.doi.org/10.1145/2491465.2491470

MUJA, Marius; LOWE, David. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration. Proceedings Of The Fourth International Conference On Computer Vision Theory And Applications, Lisboa, Portugal, p.5-8, fev. 2009. VISAPP 2009. Disponível em: http://www.cs.ubc.ca/~lowe/papers/09muja.pdf. Acesso em: 13 set. 2017.

NAYLOR, B. F.. A tutorial on Binary Space Partitioning Trees. In: MEHTA, D. P.; SAHNI, S. (Ed.). Handbook of data structures and applications. [S. l.]: Chapman & Hall/crc, 2005. https://doi.org/10.1201/9781420035179.ch20

PEREIRA, Danillo Roberto. Representação e Cálculo Eficiente da Iluminação Global na Síntese de Imagem. 2009. Dissertação (Mestrado) - Curso de Ciência da Computação, Instituto de Computação, Universidade Estadual de Campinas, Campinas, 2009. Cap. 4. Disponível em: http://www.liv.ic. unicamp.br/~danillorp/Links/dissertacao.pdf. Acesso em: 08 set. 2017.

PEREIRA, D. R. et al. FEMa: A Finite Element Machine for Fast Learning - SUBMITTED - UNDER REVIEW. 1

PRATX, G.; XING, L. GPU computing in medical physics: A review. Medical Physics, [S.l.], v. 38, n. 5, p.2685-2697, 9 maio 2011. http://dx.doi.org/10.1118/1.3578605.

SAMET, H. The Design and Analysis of Spatial Data Structures. [S. l.]: Addison-wesley Publishing Company, Inc, 1994. 493 p. Disponível em: https://cdn.preterhuman.net/texts/math/Data_Structure_And_Algorithms/The Design and Analysis of Spatial Data Structures - Hanan Samet.pdf. Acesso em: 13 set. 2017.

SHAMONIN, D. et al. Fast parallel image registration on CPU and GPU for diagnostic classification of Alzheimer's disease. Frontiers In Neuroinformatics, [s.l.], v. 7, p.237-345, 2013. http://dx.doi.org/10.3389/fninf.2013.00050.

SUTHAHARAN, Shan. Big Data Classification: Problems and Challenges in Network Intrusion Prediction with Machine Learning. Acm Sigmetrics Performance Evaluation Review, [s.l.], v. 41, n. 4, p.70-73, 17 abr. 2014. https://doi.org/10.1145/2627534.2627557.

VASCONCELLOS, J. F. A. et al. Algoritmo Paralelo para Árvore Geradora usando GPU. WSCAD 2017 . In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO, 18., 2017, Campinas. Anais [...]. Campinas: SBC,2017.

ZHANG, N.; CHEN, Y.-S.; WANG, J.-li. Image parallel processing based on GPU. 2nd International Conference on Advanced Computer Control, [s.l.], 2010. IEEE.

Publicado
2019-07-31
Como Citar
Adriano Miranda , C., Carro, S., & Pereira, D. R. (2019). GANHO DE DESEMPENHO DO FEMA UTILIZANDO PROGRAMAÇÃO PARALELA E ÁRVORES DE PARTICIONAMENTO ESPACIAL. Colloquium Exactarum. ISSN: 2178-8332, 11(2), 46-55. Recuperado de http://revistas.unoeste.br/index.php/ce/article/view/3166

Outros artigos do(s) mesmo(s) autor(es)