Construction et interrogation d'arbres R parallèles basés sur GPU

Un arbre R est une structure de données destinée à organiser et interroger des données multidimensionnelles non uniformes et chevauchantes. La parallélisation efficace de l'arbre R est un problème important en raison des applications sociétales telles que les systèmes d'information géographique (SIG), les systèmes de gestion de bases de données spatiales et la mise en page VLSI qui utilisent des arbres R pour des tâches d'analyse spatiale telles que le superposition de cartes. Comme les unités de traitement graphique (GPU) ont émergé comme des plateformes de calcul puissantes, ces applications liées aux arbres R nécessitent des algorithmes de construction et de recherche d'arbres R efficaces sur GPU. Ce problème est difficile à relever à la fois en raison (i) de la topologie non linéaire de la structure d'arbre elle-même et (ii) de l'architecture inhabituelle à instruction unique et plusieurs fils (SIMT) des GPU modernes qui nécessitent une ingénierie soigneuse d'un ensemble de questions. Par conséquent, les meilleures parallélisations actuelles d'arbres R sur GPU ont un accroissement limité d'environ 20 fois. Nous présentons une conception de structure de données économiquement efficace et un algorithme de construction de bas en haut non trivial pour les arbres R sur GPU. Cela a permis d'obtenir le premier accroissement démontré de 226 fois dans la construction parallèle d'un arbre R sur un GPU par rapport à l'exécution à un cœur sur un CPU. Nous présentons également des algorithmes de recherche d'arbres R innovants qui sont conçus pour surmonter les limitations architecturales et de ressources des GPU. Le meilleur de ces algorithmes donne un accroissement de 91 fois à 180 fois sur un arbre R avec 16384 objets de base pour des tailles de requêtes allant de 2k à 16k.