Расчеты на GPU

[Debugger]

Занимаюсь эмуляцией физического процесса. Хочется перенести его на GPU.

Есть много (~миллионы) частиц, у каждой из которых N (~тысячи) параметров (на самом деле, либо много частиц, либо много параметров, но не того и другого сразу)
Есть глобальные параметры: вектор из K величин, которые задают свойства окружения.
Параметры частиц меняются по простой формуле (функция из арифметических операций от параметров частицы и глобальных параметров).

Задача 1: собственно, эмуляция. При данном значении глобальных параметров и данном значении параметров частиц рассчитать параметры частиц через шаг времени dt.

Задача 2(более актуальна): подбор оптимальных глобальных параметров. Есть критерий качества установки, который является функцией от глобальных параметров, и считается как сумма некой f(глоб. параметры, частица) по всем частицам. f дифференцируема по глобальным параметрам, поэтому можно воспользоваться градиентным спуском. Поэтому думаю сделать так: записываю параметры частиц в текстуру, где строчка - частица, столбец - параметр. Если надо - использую несколько текстур. Изначально глобальные параметры генерируются случайно, в каком-то разумном диапазоне. Шейдер принимает на вход текстуры и текущее значение глобальных параметров, на выходе - сумму градиентов (куда надо сместить глобальные параметры). Программа смещает параметры, и снова пропускает через шейдер. Повторяет до сходимости.

Собственно, вопрос:
Насколько адекватен подход в целом, и какие подводные камни я встречу?
Куда читать?

P.S. так как точных формул я не знаю, буду делать а-ля фреймворк, а параметров много - потому что это коэффициенты ряда в разложении сложной функции по Тейлору/чему-нибудь ещё.

[Sam777e]

Все математические методы, конечно же, имеют массу всевозможных подводных корней. Градиентные методы очень трудные, там точно есть камни, даже каменюги.

Жаль, что много параметров.
А вот если бы их было [ относительно, а лучше - абсолютно ] немного, то посоветовал бы посмотреть в сторону ГА - генетических [ точнее - эволюционных ] алгоритмов. Безусловно, там тоже есть тонкости, но программируется очень просто, легко можно поиграть параметрами алгоритма и так далее. Точного экстремума не найдет, начиная с какого-то момента сходимость замерзнет - надо просто ограничить количество поколений. Но вполне приличные результаты получить можно без особых трудов + это просто интересно.
http://habrahabr.ru/post/171751/

[Debugger]

Все математические методы, конечно же, имеют массу всевозможных подводных корней. Градиентные методы очень трудные, там точно есть камни, даже каменюги.

Жаль, что много параметров.
А вот если бы их было [ относительно, а лучше - абсолютно ] немного, то посоветовал бы посмотреть в сторону ГА - генетических [ точнее - эволюционных ] алгоритмов. Безусловно, там тоже есть тонкости, но программируется очень просто, легко можно поиграть параметрами алгоритма и так далее. Точного экстремума не найдет, начиная с какого-то момента сходимость замерзнет - надо просто ограничить количество поколений. Но вполне приличные результаты получить можно без особых трудов + это просто интересно.

Вопрос не в том, какой метод круче, а в том, как его пересчитать в GPU.

Генетический алгоритм - это здорово (к слову, 1k геномов - это окей), но простая прикидка показывает, что расчет 100 поколений 100 особей эквивалентно тому, чтобы 10 раз посчитать градиентный спуск на 1000 шагов. Естественно, что лучше - зависит от функции, но обычно второй случай даст и более адекватный результат, и можно будет прикинуть разброс (насколько локальные минимумы расходятся).

Можно было зарулить в сторону симплексов и метода Нелдера-Мида, но он при большой размерности пространства параметров работает не очень.

А аналитически экстремум не найти, увы.

Кастую Mikle в тред.

[Mikle]

Есть много (~миллионы) частиц, у каждой из которых N (~тысячи) параметров

Если не смотреть в сторону OpenCL и т. п., а ограничиться уровнем графического рендера в DX9, то множество параметров будут препятствием, по крайней мере тогда, когда эти параметры меняются динамически самим рендером. Если бОльшая часть параметров статичны (напр. вес, цвет, коэффициент трения...), и только небольшая часть меняется (позиция, скорость), то задача вполне решаема.

записываю параметры частиц в текстуру, где строчка - частица, столбец - параметр.

Я бы делал 3D тектстуру, где по осям X и Y расположены частицы, а по Z - параметры, изменяемые параметры по Z расположены на нулевом уровне, если это D3DFMT_A32B32G32R32F - то мы имеем 4 изменяемых параметра, можно так же попробовать задействовать мультирендер. Рендер идёт в 2D текстуру, потом она копируется в нулевой слой исходной 3D текстуры, и можно выполнять следующий тик.

[Debugger]

Есть много (~миллионы) частиц, у каждой из которых N (~тысячи) параметров

Если не смотреть в сторону OpenCL и т. п., а ограничиться уровнем графического рендера в DX9, то множество параметров будут препятствием, по крайней мере тогда, когда эти параметры меняются динамически самим рендером. Если бОльшая часть параметров статичны (напр. вес, цвет, коэффициент трения...), и только небольшая часть меняется (позиция, скорость), то задача вполне решаема.

записываю параметры частиц в текстуру, где строчка - частица, столбец - параметр.

Я бы делал 3D тектстуру, где по осям X и Y расположены частицы, а по Z - параметры, изменяемые параметры по Z расположены на нулевом уровне, если это D3DFMT_A32B32G32R32F - то мы имеем 4 изменяемых параметра, можно так же попробовать задействовать мультирендер. Рендер идёт в 2D текстуру, потом она копируется в нулевой слой исходной 3D текстуры, и можно выполнять следующий тик.

Посмотрел в сторону OpenCL. Спасибо за наводку, это круто, то, что нужно, но хочется разобраться с самими шейдерами.

Для эмуляции это должно подойти. Если изменяемых параметров больше 4, можно будет отрендерить в 3D текстуру, или надо в несколько двумерных, и потом их складывать в стопку?

Насчет подбора глобальных параметров. У нас есть матрица, K частиц на N параметров, и N глобальных параметров. Соответственно, их надо запихать в текстуру (K+1) на N, и в нулевую строчку положить глобальные параметры, и рендерить в, хм, двумерную текстуру N на 1. Ага?

[Mikle]

Если изменяемых параметров больше 4, можно будет отрендерить в 3D текстуру, или надо в несколько двумерных, и потом их складывать в стопку?

В 3D текстуру, к сожалению, рендерить нельзя. Рендерить несколько раз в 2D можно, но есть "Multielement Texture" - можно рендерить в несколько рендертаргетов одновременно. Точнее это не совсем независимые рендертаргеты, у них общий буфер глубины (регистр oDepth) и независимы колорбуферы (oC#).

У нас есть матрица, K частиц на N параметров, и N глобальных параметров. Соответственно, их надо запихать в текстуру (K+1) на N, и в нулевую строчку положить глобальные параметры, и рендерить в, хм, двумерную текстуру N на 1. Ага?

Поэтому я и написал вначале, что ИСХОДНАЯ текстура нужна 3D. Иначе при слишком большом "K" у тебя просто предел размера текстуры ограничит.