Thesis (MEng)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: In this thesis we set out to design an algorithm for solving the all-pairs fixed-radius nearest
neighbours search problem for a massively parallel heterogeneous system. The all-pairs
search problem is stated as follows: Given a set of N points in d-dimensional space, find
all pairs of points within a horizon distance of one another. This search is required
by any nonlocal or meshless numerical modelling method to construct the neighbour list
of each mesh point in the problem domain. Therefore, this work is applicable to a wide
variety of fields, ranging from molecular dynamics to pattern recognition and geographical
information 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, the
distance to each other mesh point and compare with the horizon value to determine if the
points are neighbours. This can be a very computationally intensive procedure, especially
if the neighbourhood needs to be updated at every time step to account for changes in
material configuration. The problem also becomes more complex if the analysis is done
in parallel.
Furthermore, GPU computing has become very popular in the last decade. Most of the
fastest supercomputers in the world today employ GPU processors as accelerators to CPU
processors. It is also believed that the next-generation exascale supercomputers will be heterogeneous. Therefore the focus is on how to develop a neighbour searching algorithm
that will take advantage of next-generation hardware.
In this thesis we propose a CPU - multi GPU algorithm, which is an extension of the
fixed-grid method, for the fixed-radius nearest neighbours search on massively parallel
systems. / AFRIKAANSE OPSOMMING: In hierdie tesis het ons die ontwerp van ’n algoritme vir die oplossing van die alle-pare
vaste-radius naaste bure soektog probleem vir groot skaal parallele heterogene stelsels
aangepak. Die alle-pare soektog probleem is as volg gestel: Gegewe ’n stel van N punte
in d-dimensionele ruimte, vind al die pare van punte wat binne ’n horison afstand van
mekaar af is. Die soektog word deur enige nie-lokale of roosterlose numeriese metode
benodig om die bure-lys van alle rooster-punte in die probleem te kry. Daarom is hierdie
werk van toepassing op ’n wye verskeidenheid van velde, wat wissel van molekulêre dinamika
tot patroon herkenning en geografiese inligtingstelsels. Hier is ons fokus op nie-lokale
soliede meganika metodes.
Die basiese metode vir die oplossing van die alle-pare soektog is om vir elke rooster-punt,
die afstand na elke ander rooster-punt te bereken en te vergelyk met die horison lente,
om dus so te bepaal of die punte bure is. Dit kan ’n baie berekenings intensiewe proses
wees, veral as die probleem by elke stap opgedateer moet word om die veranderinge in
die materiaal konfigurasie daar te stel. Die probleem word ook baie meer kompleks as die
analise in parallel gedoen word.
Verder het GVE’s (Grafiese verwerkings eenhede) baie gewild geword in die afgelope
dekade. Die meeste van die vinnigste superrekenaars in die wêreld vandag gebruik GVE’s as versnellers te same met SVE’s (Sentrale verwerkings eenhede). Dit is ook van mening
dat die volgende generasie exa-skaal superrekenaars GVE’s sal implementeer. Daarom is
die fokus op hoe om ’n bure-lys soektog algoritme te ontwikkel wat gebruik sal maak van
die volgende generasie hardeware.
In hierdie tesis stel ons ’n SVE - veelvoudige GVE algoritme voor, wat ’n verlenging
van die vaste-rooster metode is, vir die vaste-radius naaste bure soektog op groot skaal
parallele stelsels.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/96144 |
| Date | 12 1900 |
| Creators | Pols, LeRoi Vincent |
| Contributors | Turner, Dan Z., Stellenbosch University. Faculty of Engineering. Department of Civil Engineering. |
| Publisher | Stellenbosch : Stellenbosch University |
| Source Sets | South African National ETD Portal |
| Language | en_ZA |
| Detected Language | Unknown |
| Type | Thesis |
| Format | xv, 55 p. ill. |
| Rights | Stellenbosch University |
Page generated in 0.0027 seconds