Comments 21
Спасибо, интересная статья, вам повезло с задачей, которая под CUDA реализуется практически идеально. У нас вот начальство радостно желает применить это хоть куда-то (видимо исходя из модных трендов), с трудом получается убедить, что не все йогурты одинаково полезны алгоритмы легко и с выигрышем реализуемы на видеокартах.
Использование CUDA в данном случае было моей инициативой, повезло что ее не «зарезали» сразу, пока не было результатов.
Да, убедить иногда очень сложно, какие-то здравые аргументы, что если картинка не влезает в память и ее придется свопить, а это очень медленно — не принимались…
Разные технологии существуют для того, чтобы применять их в нужных случаях.
Да, убедить иногда очень сложно, какие-то здравые аргументы, что если картинка не влезает в память и ее придется свопить, а это очень медленно — не принимались…
Разные технологии существуют для того, чтобы применять их в нужных случаях.
а не проще ли осуществлять не перебор точек пространства, а точек границы?
т.е. создаетm массив 36*36*36 a[i][j][k] = i*i + j*j + k*k;
а потом для каждой точки границы перебираются точки пространства и им проставляются значения, если они не больше необходимого.
т.е. создаетm массив 36*36*36 a[i][j][k] = i*i + j*j + k*k;
а потом для каждой точки границы перебираются точки пространства и им проставляются значения, если они не больше необходимого.
по сути, примерно это и происходит, за счет использования близких кубиков к границе. к сожалению, вопрос о заполнении не всех точек пространства даже не стоит — результирующую карту расстояний «кушает» другое приложение, которому нужны значения во всех точках. Но так или иначе заполнение оставшихся кубиков существенно быстрее, чем файловые операции для них.
прикинем
размер 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 мегабайт для выделения непосредственно координат точек) и «элементарная операция» — сравнение двух чисел.
размер 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 мегабайт для выделения непосредственно координат точек) и «элементарная операция» — сравнение двух чисел.
о, вот теперь осознал Вашу идею. проэкспериментирую завтра — в теории звучит очень хорошо, на практике пока несколько смущает:
в 4 раза меньше операций, да это несомненно плюс.
но большая часть операций — запись, соответственно тут встанет вопрос об эффективности переноса такого алгоритма на видеокарту, даже если забыть про синхронизацию потоков — запись затратна.
а ускорение на основном процессоре в 4 раза все равно не даст нужного времени.
когда попробую — расскажу о результатах.
спасибо за идею!
в 4 раза меньше операций, да это несомненно плюс.
но большая часть операций — запись, соответственно тут встанет вопрос об эффективности переноса такого алгоритма на видеокарту, даже если забыть про синхронизацию потоков — запись затратна.
а ускорение на основном процессоре в 4 раза все равно не даст нужного времени.
когда попробую — расскажу о результатах.
спасибо за идею!
я на самом деле ошибся. надо пробежаться по матрице размером 72*72*72, т.е. количество операций — в два раза больше.
но все равно, имхо, это должно дать выигрыш.
но все равно, имхо, это должно дать выигрыш.
количество операций получается в 2*2*2 раза больше, то есть все-таки в (грубо) 2 раза больше чем в моем варианте.
однако на CPU Ваша идея работает быстрее, все-таки не любит он много вещественной арифметики.
однако на CPU Ваша идея работает быстрее, все-таки не любит он много вещественной арифметики.
проверить не мешает: сравнение как элементарная операция сама по себе проще, при том же, алгоритм тоже можно упростить правильным обходом окружающих точек пространства с отсечением лишних.
ну а ваш алгоритм тоже можно оптимизировать в этой строке:
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]);
табличными вычислениями.
ну а ваш алгоритм тоже можно оптимизировать в этой строке:
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]);
табличными вычислениями.
А почему не использовать R-деревья? Может быть у них есть какой нибудь недостаток?
Начинаю читать статью, а в плеере включается Massive Attack — Teardrop. Мистика, не иначе )
Перезалейте картинки пжлст!
Заметил что вы суммируете нулевым тредом. Есть способ быстрее — параллельная редукция. Гляньте SDK семпл reduction, там все просто. Примерно так:
результат в sMins[0]
удачи, отличная статья!
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]
удачи, отличная статья!
Я, конечно, слоупок, но может быть кто-нибудь и ответит (:
В названии статьи фигурирует «точная 3D карта расстояний», хотя она вроде точная только в пределах GUARANTEED_DIST.
>* Вторая (разумная) — использовать индексы на начальное и конечное размещение точек для каждого кубика, эти индексы могут пересекаться, и за счет грамотного их вычисления можно сэкономить еще в 2 раза по объему памяти.
Не совсем понятно, что значит начальное и конечное размещение точек.
В названии статьи фигурирует «точная 3D карта расстояний», хотя она вроде точная только в пределах GUARANTEED_DIST.
>* Вторая (разумная) — использовать индексы на начальное и конечное размещение точек для каждого кубика, эти индексы могут пересекаться, и за счет грамотного их вычисления можно сэкономить еще в 2 раза по объему памяти.
Не совсем понятно, что значит начальное и конечное размещение точек.
Sign up to leave a comment.
Быстрое вычисление точной 3D карты расстояний с использованием технологии CUDA