Метод Левенберга-Марквардта на видеокарте. OpenCL.

[Саваневич Вадим]

В рамках проекта разработки программы обработки астероидных обзоров CoLiTec/CLT (http://neoastrasoft.com/category/news-en/) решили перенести часть операций на видеокарту. Выбрали язык OpenCL, хотя много думали предварительно о CUDA.
Для начала решили перенести на видеокарту фитинг.
Параллельно решили усилить/разнообразить фитинг добавлением в него возможности использования метода/алгоритма Левенберга-Марквардта (LMA,http://alglib.sources.ru/optimization/levenbergmarquardt.php) по разным профилям/моделям изображений объектов. До этого использовали менее трудоемкий (более быстрый) вычислительный метод своей разработки.
Толком код LMA на OpenCL найти не можем.
Прошу помочь.
Может кто-то с этим связан более плотно.
Также приму с благодарностью любые советы по эффективной разработке ПО для неграфических вычислений на видеокарте. Возможно и более тесное сотрудничество (только проект у нас в основном аспирантский (то есть любительский) со всеми финансовыми вытекающими).

Заранее большое спасибо и удач. В небе и на Земле.
С благоговением перед миром,
Вадим

[alex_veles]

Добрый день!
Не уверен что смогу помочь, сам пытаюсь перенять опыт  использования OpenCL у японских коллег :-)
 Насколько помню этот метод, врядли Вы найдёте готовую реализацию LMA ,  сильно зависит от того что хотите минимизировать, вида функции, якобиана и т.п., тем более сразу на OpenCL.

Из моего опыта разработки на OpenCL, несколько выводов (ну они вообще общие для GPGPU).
1. OpenCL следует использовать, если алгоритм можно разбить на большое кол-во независимо вычисляемых, подобных  и небольших частей.
Причем это число должно быть в районе многих тысяч для современных GPU (IMHO раза в 4-10 больше числа потоковых процессоров на чипе), или около сотен для современных CPU.
Причем, при числе потоков до 1-2 тыс. CPU может быть лучше GPU.
2. Простейший вариант, сделать библиотеку на OpenCL с нужной функцией, дергать её из С/С++ кода, передавая массив данных и получая результат (обычно я так делаю, правда  всё под linux).
 Функция примерно не меньше чем на 0.5-1 TFlop операций,чтобы не вызывать сильно часто.
3. Реализаций OpenCL много, каждый вендор пилит что-то свое.
Например  у меня на ПК с двумя geforce две OpenCL платформы и три вычислительных устройства (2 nvidia и intel), на ПК с 2мя  AMD radeon тоже две платформы и 4 вычислительных устройства
(amd умеет считать на CPU) и т.п.
4. Код обычно неплохо переносим между GPU и CPU, но иногда для пущей оптимизации нужны небольшие изменения в зависимости CPU это или GPU.

Из последних наблюдений, nvidia как-то не очень активно продвигает OpenCL, возможно даже жертвует им ради cuda.
Например в новой cuda5 SDK выкинули примеры и opencl библиотеку.
С другой стороны, радует что OpenCL будет от новых xeon phi до чипов на arm :-)
 
 

[xd]

И ещё, алгоритмы для GPU очень не любят переходы, особенно условные. Циклы с фиксированным количеством шагов лучше раскладывать в параллелизм, с переменным - плохо. Условия, проверки, ветвление - беда для GPU.

[Саваневич Вадим]

Большое спасибо за ответы.
Очень им рад.
К работе по переходу на GPU  подступаем медленно как из-за робости, так и из-за обилия других дел.

1. OpenCL следует использовать, если алгоритм можно разбить на большое кол-во независимо вычисляемых, подобных  и небольших частей.
Причем это число должно быть в районе многих тысяч для современных GPU (IMHO раза в 4-10 больше числа потоковых процессоров на чипе), или около сотен для современных CPU.
Причем, при числе потоков до 1-2 тыс. CPU может быть лучше GPU.  Функция примерно не меньше чем на 0.5-1 TFlop операций,чтобы не вызывать сильно часто.

Я думаю распараллелить фитинг по порциям данных (это немного скрасит "бреду" условных переходов, ветвлений, проверок). На кадре обычно от 15 000-25 000 (поле 1.5х1.5 градуса, область вне Млечного Пути, время счета = до 40 секунд) до 80 000 (поле 8х8 градусов) объектоподобных образований. Мы загоним кадр целиком на GPU, параллельно подадим координаты центров изображений объектов. Своим , пока, итерационным методом получим оценки положения и амплитуды объектов и как-то выдадим их в файл или БД. LMA пока забросим, слишком много всего ...
Конечно, количество шагов в итерационном методе мы не сможем определить наперед, да и данные прошлой итерации наперед не посчитаешь.
Как быть?
Я думаю стоит попробовать.
Пусть не выиграем в 30 раз, а в 5-10 = это меня вполне устроит.

[xd]

Ну я вижу ситуацию следующим образом: определение границ и центров тяжести фрагментов можно параллелить на GPU, там нет вообще ветвлений, на входе - массив данных, на выходе - массив значений, определяющих принадлежность к выходным данным. Главное границы регионов правильно нарезать. Хорошо параллелится получение статистики по изображениям для распознавания образов. А потом CPU последовательным перебором уже небольшого набора данных без каких-либо вычислений принимает решение о том, куда дальше плыть.

[alex_veles]

Трудно сказать насколько хорошо распараллелиться, итерации зависят от предыдущего результата + много условных операторов, как сказали, это может убить весь выигрыш от GPU.
А все возможности CPU Вы исчерпали? Многопоточность, SSE, AVX?
Ибо новые процессоры от Intel дают около 300GFlops на хороших задачах, и  опережают GPU для задач с не очень большим числом потоков.
Может попробовать использовать  OpenMP прежде  за  OpenCL ?

[Саваневич Вадим]

А все возможности CPU Вы исчерпали? Многопоточность, SSE, AVX?
Ибо новые процессоры от Intel дают около 300GFlops на хороших задачах, и  опережают GPU для задач с не очень большим числом потоков.
Может попробовать использовать  OpenMP прежде  за  OpenCL ?

1. Мы по своему распроцессили задачу. Каждый кадр обрабатывается на своем ядре. Межкадровая обработка выполняется по обработке всех кадров серии на отдельном ядре для отдельной зоны. Управление программными сущностями = децентрализованное, асинхронное, в принципе = на все ядра локсети, но этого толком не пробовали, одного компа хватает с избытком задержка в обработке данных = не более 10-20 минут в реале. В астросарай поставить локсеть не получается. При мечтах о более крутой обработке упираемся в быстродействие.
2. Я примат (прикладная математика). Вольты от ватт путаю (немного утрирую). Не все в сказанном выше понимаю до уровня практического внедрения. Тем более прога на 2/3 написана на Делфи и не очень понятно как на нем использовать настройки компилятора так глубоко (год назад пробовали, но толком и не сильно пробовали и не сильно получилось = в будущем - конечно).  Сейчас почти переписали фитинг  (как пилотный проект) на MS VS С++. Там надеемся побороться на этом фронте.
3. После пилотного проекта пойдем на межкадровую обработку = она параллелится очень хорошо. Тут нет проблем. Вот бы только реализовать.
Многое упирается в ресурсы.
4. Вообще классно, что Вы откликнулись.
Про Алексея я давно слышал = даже ему письмо писал, даже передавал привет через человека-комету Виталия Невского. Правда ....
А Алекс= по всему видать великий спец ...
Вот бы посотрудничать.
Уже .... движемся вперед.
Спасибо Вам
Вадим

[Freddykrug]

Свой проект в BOINC не хотите создать? Может быть, там, на форумах зададите свой вопрос?

[xd]

В BOINC оперативность получения результатов может быть совсем никакой.

[Саваневич Вадим]

Свой проект в BOINC не хотите создать?

Спасибо,
Может быть со временем.
Вадим

[Freddykrug]

В BOINC оперативность получения результатов может быть совсем никакой.

Кто мешает сделать дедлайн коротким? Тем более расчеты на видеокарте намного быстрее процессорных. И откуда взялось, что:

Ибо новые процессоры от Intel дают около 300GFlops на хороших задачах, и  опережают GPU для задач с не очень большим числом потоков.

мне неясно. Какие такие "новые процессоры от Intel"  и с какими видеокартами сравнивались? 

[Freddykrug]

Кстати, по астероидам уже есть два проекта: orbit@home (из-за отсутствия финансирования не работает) и Asteroids@home . Может, стоит вам попробовать у их разработчиков спросить? Правда, разработчики вам вряд ли чем-то помогут, ибо в обоих проектах приложения разработаны для процессоров.

[alex_veles]

мне неясно. Какие такие "новые процессоры от Intel"  и с какими видеокартами сравнивались?

Ну процессоры не так часто модельно обновляются :-)
В данном случае сравнивались процессоры с AVX инструкциями (core i7-2600K и 3960X) с новыми же картами gtx670 и amd 7970.

[Freddykrug]

gtx670 - карты, для кранчерства непригодные - это уже выяснено. В частности:

Geforcы на кеплере считают двойную точность в 24 раза медленнее одинарной. 

Еще:

Брать 670-ки под кранчинг нет смысла вообще.

Ну и читаем всю эту тема. Так что не надо сравнивать с gtx6ХХ . Некорректно.
Что касается того, что core i7-2600K  побивает amd 7970 - ну не верю!!! Милкивэй считаю на видеокарте  радеоне 6930 (не самой топовой), но недавно по недосмотру запустил и на Core i5-2400 (где AVX тоже есть).  Приложение одно и то же - MilkyWay@Home (есть еще MilkyWay@Home N-Body Simulation) 
На процессоре задачи считались по 6 часов. На радеоне считаются по 54 секунды! А ведь милкивэй - это проект с двойной точностью.
П.С. Сравните лучше с Tesla    Но учтите - нвидиа в последнее время разлюбила OpenCL.

[Саваневич Вадим]

Кстати, по астероидам уже есть два проекта: orbit@home (из-за отсутствия финансирования не работает) и Asteroids@home . Может, стоит вам попробовать у их разработчиков спросить? Правда, разработчики вам вряд ли чем-то помогут, ибо в обоих проектах приложения разработаны для процессоров.

Все  облачно подобные вычисления не сильно подходят астероидно-кометным обзорам. Нужна онлайн обработка.  Сколько раз за счет оперативности представления данных наши пользователи опережали богатые американские обзоры на десяток минут и имели в этой связи приоритет.
Чтобы увидеть что-то на бюджетном телескопе надо быть вдали от засветок, а значит от Инета. Нет возможности перекачивать кадры. Наблюдатель обрабатывает кадры нашей прогой на компах в астросарайчиках, в которых стоят скоп и пару компов (один управляет скопом, другой обрабатывает данные). Наблюдатель часто получает только подозрительные куски кадра по удаленному рабочему столу, сейчас сделали, правда, сайт кропов.    Больше = нет Инета ...
Так что это надо иметь в виду.

[Саваневич Вадим]

П.С. Сравните лучше с Tesla    Но учтите - нвидиа в последнее время разлюбила OpenCL.

Так что = лучше работать с CUDA?
А как тогда быть с Радеонами?

[alex_veles]

Во-первых, я как бы немного разбираюсь в вопросе :-) , не нада рассказывать банальности.

Во-вторых, я нигде не говорил про двойную точность, мне пока хватает одинарной в некоторых задачах.
Я не знаю что такое кранчинг, но gtx670 в одинарной точности в задаче N тел выдает больше 1.3 TFlops при достаточном числе частиц (от 100 тысяч) правда при прямом суммировании. Запустите пример из SDK и убедитесь.
С двойной точностью никому в голову не придет считать ни на gtx6xxx ни на gtx5xxx, для этого есть радеоны и теслы для более состоятельных.

По поводу CPU vs GPU, перечитайте что я писал, до определенного числа потоков CPU эффективнее GPU.
Для задачи N тел, до примерно 1000-2000 частиц, код написанный с AVX на CPU быстрее считается чем на GPU.
Для GPU банально не хватает потоков, она простаивает.

Что Вы там сравниваете, не знаю. Предполагаю, что код не использует AVX, и скорее всего не оптимизирован, абы чтобы считался везде.

[Freddykrug]

Так что = лучше работать с CUDA?
А как тогда быть с Радеонами?

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

Для GPU банально не хватает потоков, она простаивает.

Вообще-то одновременный запуск нескольких задач на одном графическом процессоре - не такая уж и экзотика. Правда, увеличивается продолжительность обработки одного задания, но общая производительность увеличивается в разы. Но, как понял, вам нужна скорость выполнения 1 задания, а не нескольких.
И еще: если так рьяно отстаиваете производительность процессоров перед видеокартами, то зачем вся эта тема? 

[alex_veles]

Так что = лучше работать с CUDA?
А как тогда быть с Радеонами?

Тут, как говориться, простого ответа нет.
Я приверженец OpenCL, и пока на geforce работает, проблем нет.
Если гады отрежут  программно поддержку
 в tesla k20, перейдём на amd 7970 или xeon phi :-)
Этим nvidia только навредит себе , так как обещаный к декабрю k20 ничем не лучше уже год работающего amd 7970, что с одинарной что с двойной точностью.

[Саваневич Вадим]

Что Вы там сравниваете, не знаю. Предполагаю, что код не использует AVX, и скорее всего не оптимизирован, абы чтобы считался везде.

Точно. Оптимизация кода, правильное задание опций компилятору = давно целое искусство.... сам помню .... это еще в 80-е было. Только за счет опций компилятору  прогу можно было ускорить в 2-3 раза без изменения кода...