Быстрое вычисление точной 3D карты расстояний с использованием технологии CUDA

[GraD_Kh]

Спасибо, интересная статья, вам повезло с задачей, которая под CUDA реализуется практически идеально. У нас вот начальство радостно желает применить это хоть куда-то (видимо исходя из модных трендов), с трудом получается убедить, что не все йогурты одинаково полезны алгоритмы легко и с выигрышем реализуемы на видеокартах.

[sic]

Использование CUDA в данном случае было моей инициативой, повезло что ее не «зарезали» сразу, пока не было результатов.

Да, убедить иногда очень сложно, какие-то здравые аргументы, что если картинка не влезает в память и ее придется свопить, а это очень медленно — не принимались…

Разные технологии существуют для того, чтобы применять их в нужных случаях.

[GraD_Kh]

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

[zikher]

а не проще ли осуществлять не перебор точек пространства, а точек границы?
т.е. создаетm массив 36*36*36 a[i][j][k] = i*i + j*j + k*k;
а потом для каждой точки границы перебираются точки пространства и им проставляются значения, если они не больше необходимого.

[sic]

по сути, примерно это и происходит, за счет использования близких кубиков к границе. к сожалению, вопрос о заполнении не всех точек пространства даже не стоит — результирующую карту расстояний «кушает» другое приложение, которому нужны значения во всех точках. Но так или иначе заполнение оставшихся кубиков существенно быстрее, чем файловые операции для них.

[zikher]

прикинем
размер 3Д-картинки для простоты возьмем 512*512*512
размер кубика — 32*32*32 =.
т.е. кубиков — 16*16*16 = 4 096. Используются из них порядка 1/4 = 1 024 кубика.
первый прогон — прогон границы, расчет достижимых от данной границы кубиков — практически не затратен.
второй прогон — обсчет «ближайших» точек границы. для каждого кубика будет порядка (2*32)*(2*32) = 4 096 точек границы, расстояние до которых надо рассчитать (вот тут могу ошибиться).
итого:
1 024 кубика * 32 768 точек в кубике * 4 096 точек границы для обсчета = 2^37 операций вида
(x*x + y*y + z*z)

количество точек границы = порядка 2*512 на каждом уровне, т.е. около 2*512*512 всего. изначальный расчет матрицы расстояний не затратен далее для каждой точки необходимо по матрице размером 36*36*36 = 46 656 пробежаться (округлим вверх до 65 536), сравнив расстояния до нужной точки, и поправив его при необходимости.

итого: 2*512*512*65 536 — в четыре раза меньше.

теперь еще стоит заметить, что первый вариант требует кучу памяти для соответствия точка границы-блок и в качестве «элементарной операции» там стоит вычисление расстояния от точки до точки, а во втором — минимум памяти (ну разве что дополнительные около (2*512*512)*32 = 16 мегабайт для выделения непосредственно координат точек) и «элементарная операция» — сравнение двух чисел.

[sic]

о, вот теперь осознал Вашу идею. проэкспериментирую завтра — в теории звучит очень хорошо, на практике пока несколько смущает:
в 4 раза меньше операций, да это несомненно плюс.
но большая часть операций — запись, соответственно тут встанет вопрос об эффективности переноса такого алгоритма на видеокарту, даже если забыть про синхронизацию потоков — запись затратна.
а ускорение на основном процессоре в 4 раза все равно не даст нужного времени.
когда попробую — расскажу о результатах.

спасибо за идею!

[zikher]

я на самом деле ошибся. надо пробежаться по матрице размером 72*72*72, т.е. количество операций — в два раза больше.
но все равно, имхо, это должно дать выигрыш.

[sic]

количество операций получается в 2*2*2 раза больше, то есть все-таки в (грубо) 2 раза больше чем в моем варианте.
однако на CPU Ваша идея работает быстрее, все-таки не любит он много вещественной арифметики.

[zikher]

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

ну а ваш алгоритм тоже можно оптимизировать в этой строке:
float dist = (x — new_border[3*j] )*(x — new_border[3*j] )
+ (y — new_border[3*j+1])*(y — new_border[3*j+1])
+ (z — new_border[3*j+2])*(z — new_border[3*j+2]);

табличными вычислениями.

[akuznetsov]

А почему не использовать R-деревья? Может быть у них есть какой нибудь недостаток?

[sic]

можно, но смысл? кубики проще, считаются быстрее, и для данной задачи этого достаточно.

[nukie]

Начинаю читать статью, а в плеере включается Massive Attack — Teardrop. Мистика, не иначе )

[sic]

а, вот теперь знаю, как эта тема называется :)

[Toshas]

Перезалейте картинки пжлст!

[sic]

а, ну вот опять… подскажите, куда можно png отправить, чтоб они не попортились?

[akzhan]

habrastorage.org/

[Toshas]

Заметил что вы суммируете нулевым тредом. Есть способ быстрее — параллельная редукция. Гляньте SDK семпл reduction, там все просто. Примерно так:

if (threadIdx.x < halfData) sMins[j] = (sMins[j] < sMins[j+halfData]) ? sMins[j] : sMins[j+halfData]; __syncthreads();
if (threadIdx.x < halfData/2) sMins[j] = (sMins[j] < sMins[j+halfData/2]) ? sMins[j] : sMins[j+halfData/2]; __syncthreads();
//...
//после того как число в условии станет 32 можно уже не делать __syncthreads
if (threadIdx.x < 32) sMins[j] = (sMins[j] < sMins[j+32]) ? sMins[j] : sMins[j+32];
if (threadIdx.x < 16) sMins[j] = (sMins[j] < sMins[j+16]) ? sMins[j] : sMins[j+16];
if (threadIdx.x < 8) sMins[j] = (sMins[j] < sMins[j+8]) ? sMins[j] : sMins[j+8];
if (threadIdx.x < 4) sMins[j] = (sMins[j] < sMins[j+4]) ? sMins[j] : sMins[j+4];
if (threadIdx.x < 2) sMins[j] = (sMins[j] < sMins[j+2]) ? sMins[j] : sMins[j+2];
if (threadIdx.x < 1) sMins[j] = (sMins[j] < sMins[j+1]) ? sMins[j] : sMins[j+1];

результат в sMins[0]

удачи, отличная статья!

[sic]

спасибо!

да, этот способ я видел в nvidia sdk. изначально было так и написано, но на время расчета это никак не влияло, возможно подвох в том что распараллеливание операции "<" не дает такого существенного выигрыша, нежели арифметических операций.

[red1ynx]

Я, конечно, слоупок, но может быть кто-нибудь и ответит (:

В названии статьи фигурирует «точная 3D карта расстояний», хотя она вроде точная только в пределах GUARANTEED_DIST.

>* Вторая (разумная) — использовать индексы на начальное и конечное размещение точек для каждого кубика, эти индексы могут пересекаться, и за счет грамотного их вычисления можно сэкономить еще в 2 раза по объему памяти.

Не совсем понятно, что значит начальное и конечное размещение точек.