Abstract
The neighborhood problem appears in many applications of computational geometry, computational mechanics, etc. In all these situations, the main requirement for a competitive implementation is performance, which can only be attained in modern hardware by exploiting parallelism. However, whereas the performance of serial algorithms is fairly predictable, that of parallel methods depends on delicate issues that have a huge impact (cache memory, cache misses, memory alignment, etc.), but are not easy to control. Even if there is not a simple approach to deal with these factors in shared-memory architectures, it is quite convenient to program parallel algorithms where the data are segregated on a per-thread basis. With this objective in mind, we propose a strategy to develop parallel algorithms based on a two-level design, and apply it to efficiently solve the nearest neighborhood problem. At a higher level, the proposed methods orchestrate the parallel algorithm and split the space into cells stored in a hash table; at the lower level, our methods hold serial search algorithms that are completely agnostic to the high-level counterpart. Using this strategy, we have developed a library combining different serial and parallel algorithms, optimized them, and assessed their performance. The analysis carried out allows to better understand the main bottlenecks in the algorithmic solution of the nearest neighborhood problem and come out with very fast implementations that improve existing available software.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Cost S, Salzberg S (1993) A weighted nearest neighbor algorithm for learning with symbolic features. Mach Learn 10:57–78
Huerta A, Belytschko T, Fernández-Méndez S, Timon Rabczuk (2004) Meshfree methods. In: Stein E, de Borst R, Hughes TJR (eds) Encyclopedia of computational mechanics. Wiley, New York
Li S, Liu WK (2004) Meshfree particle methods. Springer, Berlin
Belytschko T, Lu YY, Gu L (1994) Element-free Galerkin methods. Int J Numer Methods Eng 37(2):229–256
Sulsky D, Chen Z, Schreyer HL (1994) A particle method for history-dependent materials. Comput Methods Appl Mech Eng 118:179–196
Bentley JL (1975) Multidimensional binary search trees used for associative searching. Commun ACM
Tapia-Fernández S, Romero I, García-Beltrán Á (2017) A new approach for the solution of the neighborhood problem in meshfree methods. Eng Comput 33(2):239–247
Knuth DE (1997) The art of computer programming, 3rd edn. Addison-Wesley, Reading
(2018) Handbook of data structures and applications. Chapman Hall CRC Computer and Information Science Series
Alexandr A, Piotr I (2008) Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun ACM 51(1):117–122
Malkov YA, Yashunin DA (2020) Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans Pattern Anal Mach Intell 42(4):824–836
Homann H, Laenen F (2018) SOAX: a generic C++ structure of arrays for handling particles in HPC codes. Comput Phys Commun 224:325–332
Faria N, Silva R, Sobral JL (2013) Impact of data structure layout on performance. In: 21st Euromicro international conference on parallel, distributed, and network-based processing, pp 116–120, 2013
Pharr M, Mark WR (2012) ISPC: a SPMD compiler for high-performance CPU programming. In: 2012 innovative parallel computing (InPar), pp 1–13
Alonso-Miyazaki PH, Tapia-Fernandez S. r2bt. https://bitbucket.org/stapia/r2bt
Olliff J, Alford B, Simkins DC (2018) Efficient searching in meshfree methods. Comput Mech 62:1461–1483
IEEE Standard for Floating-Point Arithmetic (2008) IEEE Std 754:1–70
Intel threading building blocks. Available at https://software.intel.com/en-us/tbb-documentation. Last seen: 6th Apr 2020
Zeromq. Available at http://zeromq.org. Last seen: 6th Apr 2020
Open MP. Available at https://www.openmp.org. Last seen: 6th Apr 2020
McMaster Colin L (1978) An analysis of algorithms for the Dutch national flag problem. Commun ACM 21(10):842–846
Mount DM (2010) ANN programming manual. http://www.cs.umd.edu/, version 1.1 edition, 2010
Arya S, Mount DM, Netanyahu NS, Silverman R, Wu AY (1998) An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J ACM 45(6):891–923
Guennebaud G, Jacob B et al (2010) Eigen v3. http://eigen.tuxfamily.org
Stanford Computer Graphics Laboratory. Stanford bunny. http://graphics.stanford.edu/pub/3Dscanrep/bunny.tar.gz
Hozanovic E (2019) Francis runner. https://grabcad.com/library/runner-francis-1
Engwirda D (2016) Conforming restricted Delaunay mesh generation for piecewise smooth complexes. Proc Eng 163:84–96
Engwirda D (2018) Generalised primal-dual grids for unstructured co-volume schemes. J Comput Phys 375:155–176
Aumüller M, Bernhardsson E, Faithfull A (2017) Ann-benchmarks: a benchmarking tool for approximate nearest neighbor algorithms. In: Beecks C, Borutta F, Kröger P, Seidl T (eds) Similarity search and applications. Springer International Publishing, Cham, pp 34–49
Chisnall D (2018) C is not a low-level language. Queue 16(2):18–30
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Tapia-Fernández, S., Alonso-Miyazaki, P.H., Romero, I. et al. Strategy and algorithms for the parallel solution of the nearest neighborhood problem in shared-memory processors. Engineering with Computers 38 (Suppl 2), 1669–1679 (2022). https://doi.org/10.1007/s00366-021-01304-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00366-021-01304-y