Scalability of fixed-radius searching in meshless methods for heterogeneous architectures

[摘要] ENGLISH ABSTRACT: In this thesis we set out to design an algorithm for solving the all-pairs fixed-radius nearestneighbours search problem for a massively parallel heterogeneous system. The all-pairssearch problem is stated as follows: Given a set of N points in d-dimensional space, findall pairs of points within a horizon distance of one another. This search is requiredby any nonlocal or meshless numerical modelling method to construct the neighbour listof each mesh point in the problem domain. Therefore, this work is applicable to a widevariety of fields, ranging from molecular dynamics to pattern recognition and geographicalinformation systems. Here we focus on nonlocal solid mechanics methods.The basic method of solving the all-pairs search is to calculate, for each mesh point, thedistance to each other mesh point and compare with the horizon value to determine if thepoints are neighbours. This can be a very computationally intensive procedure, especiallyif the neighbourhood needs to be updated at every time step to account for changes inmaterial configuration. The problem also becomes more complex if the analysis is donein parallel.Furthermore, GPU computing has become very popular in the last decade. Most of thefastest supercomputers in the world today employ GPU processors as accelerators to CPUprocessors. It is also believed that the next-generation exascale supercomputers will be heterogeneous. Therefore the focus is on how to develop a neighbour searching algorithmthat will take advantage of next-generation hardware.In this thesis we propose a CPU - multi GPU algorithm, which is an extension of thefixed-grid method, for the fixed-radius nearest neighbours search on massively parallelsystems.

[发布机构] Stellenbosch University