A performance improvement to FEMa applying parallel programming and binary partition space tree
Keywords:
FEMa, GPU, Kd-Tree, K-NNAbstract
This paper presents an application with data structures and GPU to get better performances in FEMa algorithm. At first, a binary partition Kd-Tree is constructed from a dataset, after his building, the search algorithm of the K nearest neighbours (K-NN) is applied in the Kd-Tree to all sample in the test dataset. After get the result of nearest samples search, the step of classification begin applying the Finite Element Method basis to get the result. Another approach is to utilize cuda codes in algorithm, so that it can be parallelized and run in GPU to obtain a gain of performance in the code runtime.
Downloads
References
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.