Strategy and algorithms for the parallel solution of the nearest neighborhood problem in shared-memory processors

被引:0
|
作者
Santiago Tapia-Fernández
Pablo Hiroshi Alonso-Miyazaki
Ignacio Romero
Angel García-Beltrán
机构
[1] Universidad Politécnica de Madrid (UPM),Department of Electrical Engineering
[2] Universidad Politécnica de Madrid (UPM),ETSII
[3] IMDEA Materials Institute,Department of Mechanical Engineering
来源
Engineering with Computers | 2022年 / 38卷
关键词
Neighborhood problem; Regular grid; Hash table; Mesh-free methods;
D O I
暂无
中图分类号
学科分类号
摘要
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.
引用
收藏
页码:1669 / 1679
页数:10
相关论文
empty
未找到相关数据