Nearest Neighbors Search Using Multi-GPU

• Vinícius Nogueira UFMG
• Lucas Amorim UFMG / CEFET-MG
• Igor Baratta UFMG
• Gabriel Pereira UFMG
• Renato Mesquita UFMG

DOI: https://doi.org/10.5753/wscad.2021.18509

Resumo

Meshless methods are increasingly gaining space in the study of electromagnetic phenomena as an alternative to traditional mesh-based methods. One of their biggest advantages is the absence of a mesh to describe the simulation domain. Instead, the domain discretization is done by spreading nodes along the domain and its boundaries. Thus, meshless methods are based on the interactions of each node with all its neighbors, and determining the neighborhood of the nodes becomes a fundamental task. The k-nearest neighbors (kNN) is a well-known algorithm used for this purpose, but it becomes a bottleneck for these methods due to its high computational cost. One of the alternatives to reduce the kNN high computational cost is to use spatial partitioning data structures (e.g., planar grid) that allow pruning when performing the k-nearest neighbors search. Furthermore, many of these strategies employed for kNN search have been adapted for graphics processing units (GPUs) and can take advantage of its high potential for parallelism. Thus, this paper proposes a multi-GPU version of the grid method for solving the kNN problem. It was possible to achieve a speedup of up to 1.99x and up to 3.94x using two and four GPUs, respectively, when compared against the single-GPU version of the grid method.

Referências

Amorim, L., Goveia, T., Mesquita, R., and Baratta, I. (2020). GPU Finite Element Method Computation Strategy Without Mesh Coloring. Journal of Microwaves, Optoelectronics and Electromagnetic Applications, 19:252 – 264.

Amorim, L. P., Mesquita, R. C., Goveia, T. D. S., and Correa, B. C. (2019). Node-to-Node Realization of Meshless Local Petrov Galerkin (MLPG) Fully in GPU. IEEE Access, 7:151539–151557.

Behley, J., Steinhage, V., and Cremers, A. B. (2015). Efficient Radius Neighbor Search in Three-dimensional Point Clouds. In Proceedings IEEE International Conference on Robotics and Automation, volume 2015-June, pages 3625–3630. Institute of Electrical and Electronics Engineers Inc.

Chen, J. S., Hillman, M., and Chi, S. W. (2017). Meshfree Methods: Progress Made after 20 Years. Journal of Engineering Mechanics, 143(4):04017001.

Du, Q., Wang, D., and Zhu, L. (2009). On Mesh Geometry and Stiffness Matrix Conditioning for General Finite Element Spaces. SIAM Journal on Numerical Analysis, 47(2):1421–1444.

Garcia, V., Debreuve, E., Nielsen, F., and Barlaud, M. (2010). K-nearest Neighbor Search: Fast GPU-based Implementations and Application to High-dimensional Feature Matching. In ICIP Proceedings, pages 3757–3760.

Garg, R., Chandra Thakur, H., and Tripathi, B. (2015). A Review of Applications of Meshfree Methods in the area of Heat Transfer and Fluid Flow: MLPG method in particular. International Research Journal of Engineering and Technology, 1(2007):329– 338.

Geuzaine, C. and Remacle, J.-F. (2009). GMSH: A 3-D Finite Element Mesh Generator With Built-in Pre and Post-processing Facilities. International Journal for Numerical Methods in Engineering, 79(11):1309–1331.

Ikuno, S., Fujita, Y., Hirokawa, Y., Itoh, T., Nakata, S., and Kamitani, A. (2013). LargeScale Simulation of Electromagnetic Wave Propagation Using Meshless Time Domain Method With Parallel Processing. IEEE Transactions on Magnetics, 49(5):1613–1616.

Jin, J.-M. (2015). The Finite Element Method in Electromagnetics. John Wiley & Sons.

Johnson, J., Douze, M., and Jégou, H. (2019). Billion-scale Similarity Search With GPUs. IEEE Transactions on Big Data, pages 1–1.

Kamranian, M., Dehghan, M., and Tatari, M. (2017). An Adaptive Meshless Local Petrov–Galerkin Method Based on a Posteriori Error Estimation for the Boundary Layer Problems. Applied Numerical Mathematics, 111:181–196.

Kuan, J. and Lewis, P. (1997). Fast k Nearest Neighbour Search for R-tree Family. In Proceedings of ICICS, 1997 International Conference on Information, Communications and Signal Processing. Theme: Trends in Information Systems Engineering and Wireless Multimedia Communications (Cat. No.97TH8237), pages 924–928. IEEE.

Liang, S., Wang, C., Liu, Y., and Jian, L. (2009). CUKNN: A Parallel Implementation of K-nearest Neighbor on CUDA-enabled GPU. In YC-ICT2009 Proceedings, pages 415–418.

Liu, G. R. (2002). Element Free Methods. CRC, 1 edition.

Liu, G. R. (2009). Meshfree Methods: Moving Beyond the Finite Element Method. CRC Press, 2 edition.

Liu, G. R. (2016). An Overview on Meshfree Methods: For Computational Solid Mechanics. International Journal of Computational Methods, 13(05):1630001.

Masek, J., Burget, R., Karasek, J., Uher, V., and Dutta, M. K. (2015). Multi-GPU Implementation of k-nearest Neighbor Algorithm. In TSP2015 Proceedings, pages 764–767. Institute of Electrical and Electronics Engineers Inc.

Mei, G., Xu, N., and Xu, L. (2016). Improving GPU-accelerated Adaptive IDW Interpolation Algorithm Using Fast kNN Search. SpringerPlus, 5:1–22.

NVIDIA (2020). CUDA C++ PROGRAMMING GUIDE Design Guide. NVIDIA.