Courbe de Hilbert 3D pour une géométrie clairsemée

Question

J'ai un tableau 3d contenant la boîte englobante non cubique d'une géométrie clairsemée.

La géométrie de la matrice [x] [y] [z] contient la valeur 0 si (x, y, z) est située dans le domaine de calcul et sinon 1.

Dans une tentative pour réorganiser les calculs Je souhaite aime parcourir cet espace en utilisant une courbe de Hilbert.

Le contexte optimise l'accès global à la mémoire dans un programme GPU lié à la mémoire.

Comment puis-je l'implémenter?

Mise à jour: Je veux juste traverser les cellules non vides, comme je ne conserverons les (dans un tableau), avec une liste de contiguïté qui garde la trace de 19 noeuds voisins d'un élément.

Le calcul est simple copie entre deux réseaux:

dst[i] = src[adjacency_map[i]] 

Ceci est la phase de propagation d'un procédé clairsemé Lattice Boltzmann, où l'interprétation physique est streaming « » particules de fluide à partir d'un site voisin.

Plus les valeurs dans adjacency_map sont séquentielles; les accès à la mémoire plus coalesced, nous l'espérons.

noyau OpenCL:

__kernel void propagation(__global double *dst, __global double *source, 
          __global const int *adjacency_map, const uint max_size) 
{ 
    size_t l = get_global_id(0); 

    if(l > max_size) 
     return; 

    dst[l] = src[adjacency_map[l]]; 
} 

Answer 1

Une courbe de Hilbert serait un défi de taille. Il semble difficile de trouver une formulation permettant un accès aléatoire aux indices des points de la courbe.

Un Morton ordering, cependant, serait raisonnable, et a quelques-unes des mêmes propriétés intéressantes car c'est aussi une courbe de remplissage d'espace. Il y a aussi une procédure d'accès aléatoire pour trouver le nombre de Morton d'un point N-dimensionnel.

Ce que vous pourriez envisager est un processus en deux étapes:

1. Appliquer une étape de compactage du flux de données pour sélectionner les éléments de volume que vous souhaitez traiter

2. Trier cette données compactées, en utilisant leur Morton indices as the sorting key.

Vous pouvez utiliser thrust pour le compactage de flux et le tri de valeurs-clés.

Ceci devrait produire une liste d'éléments de volume dans un ordre qui favorise la contiguïté. Cela dit, les frais généraux de réorganisation des données peuvent dominer le coût du modèle d'accès irrégulier initial.

Answer 2

Cela semble tout à fait impossible.

Avez-vous déjà exclu un kdtree ou un octree?

Les descriptions de kdtree (chapitre 21.2) et octree (chapitre 21.8) dans les recettes numériques sont tout à fait compréhensible: http://apps.nrbook.com/rollover/index.html