GANHO DE DESEMPENHO DO FEMA UTILIZANDO PROGRAMAÇÃO PARALELA E ÁRVORES DE PARTICIONAMENTO ESPACIAL
Palavras-chave:
FEMa, GPU, Kd-Tree, K-NNResumo
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
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.