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
相关论文
共 50 条
  • [21] ALGORITHMS FOR SCALABLE SYNCHRONIZATION ON SHARED-MEMORY MULTIPROCESSORS
    MELLORCRUMMEY, JM
    SCOTT, ML
    ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1991, 9 (01): : 21 - 65
  • [22] Distributed, Shared-Memory Parallel Triangle Counting
    Kanewala, Thejaka Amila
    Zalewski, Marcin
    Lumsdaine, Andrew
    PROCEEDINGS OF THE PLATFORM FOR ADVANCED SCIENTIFIC COMPUTING CONFERENCE (PASC '18), 2017,
  • [23] PARALLEL CHOLESKY FACTORIZATION ON A SHARED-MEMORY MULTIPROCESSOR
    GEORGE, A
    HEATH, MT
    LIU, J
    LINEAR ALGEBRA AND ITS APPLICATIONS, 1986, 77 : 165 - 187
  • [24] Shared-Memory Parallel Maximal Clique Enumeration
    Das, Apurba
    Sanei-Mehri, Seyed-Vahid
    Tirthapura, Srikanta
    2018 IEEE 25TH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING (HIPC), 2018, : 62 - 71
  • [25] A PARALLEL LINKED LIST FOR SHARED-MEMORY MULTIPROCESSORS
    TANG, PY
    YEW, PC
    ZHU, CQ
    PROCEEDINGS : THE THIRTEENTH ANNUAL INTERNATIONAL COMPUTER SOFTWARE & APPLICATIONS CONFERENCE, 1989, : 130 - 135
  • [26] Correctness properties in a shared-memory parallel language
    Caplain, G
    JOURNAL OF THE ACM, 2002, 49 (06) : 785 - 827
  • [27] Design and analysis of algorithms for shared-memory multiprocessors
    Leiserson, CE
    ALGORITHMS AND DATA STRUCTURES, 1999, 1663 : 55 - 55
  • [28] ALGORITHMS FOR LU DECOMPOSITION ON A SHARED-MEMORY MULTIPROCESSOR
    BUONI, JJ
    FARRELL, PA
    RUTTAN, A
    PARALLEL COMPUTING, 1993, 19 (08) : 925 - 937
  • [29] Parallel VLSI test in a shared-memory multiprocessor
    Gil, C
    Ortega, J
    Montoya, MG
    CONCURRENCY-PRACTICE AND EXPERIENCE, 2000, 12 (05): : 311 - 326
  • [30] A MODEL FOR ASYNCHRONOUS SHARED-MEMORY PARALLEL COMPUTATION
    NISHIMURA, N
    SIAM JOURNAL ON COMPUTING, 1994, 23 (06) : 1231 - 1252