3d Кривая Гильберта для разреженной геометрии - PullRequest
Новая
       23

3d Кривая Гильберта для разреженной геометрии

3 голосов
/ 31 июля 2011

У меня есть 3d-массив, содержащий не кубическую ограничивающую рамку с разреженной геометрией.

Геометрия массива [x] [y] [z] содержит значение 0, если (x, y, z) является частью вычислительной области, а в противном случае 1.

Пытаясь изменить порядок вычислений, я хотел бы обойти это пространство, используя кривую Гильберта.

Контекст оптимизирует глобальный доступ к памяти в связанной с памятью программе GPU.

Как я могу это реализовать?

Обновление : Я просто хочу пройти через непустые ячейки, так как я буду хранить только те (в массиве) вместе со списком смежности, который отслеживает 19 соседних узлов элемента.

Вычисление просто копирование между двумя массивами: 

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

Это фаза распространения разреженного метода решетчатого Больцмана, где физическая интерпретация направляет «жидкие частицы» из соседнего узла.

Чем последовательнее значения в adjacency_map; мы надеемся, что более объединенные обращения к памяти мы получим.

ядро ​​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]];
}

Ответы [ 2 ]

3 голосов
/ 02 августа 2011

Кривая Гильберта была бы высоким порядком. Кажется, трудно найти формулировку, которая позволила бы произвольный доступ к индексам точек на кривой.

A Мортоновское упорядочение , однако, было бы разумным и имеет некоторые из тех же приятных свойств, что и кривая заполнения пространства. Существует также процедура произвольного доступа для нахождения числа Мортона N-мерной точки.

То, что вы могли бы рассмотреть, это двухэтапный процесс:

  1. Примените шаг сжатия потока к вашим данным, чтобы выбрать элементы тома, которые вы хотите обработать

  2. Сортировать эти сжатые данные, используя их Индексы Мортона в качестве ключа сортировки .

Вы можете использовать thrust как для сжатия потока, так и для сортировки значения ключа.

Это должно привести к созданию списка элементов тома в порядке, обеспечивающем смежность. Тем не менее, накладные расходы на реорганизацию данных могут доминировать над стоимостью исходного нерегулярного шаблона доступа.

1 голос
/ 31 июля 2011

Это звучит совершенно невозможно.

Вы уже исключили kdtree или octree?

Описания kdtree (глава 21.2) и octree (глава 21.8) в числовых рецептах вполне понятны: http://apps.nrbook.com/rollover/index.html

...