Библиотека для оптимизации с помощью видеокарты

[Igor_Dmitriev]

Здравствуйте.
Есть сложная функция, записанная в виде алгоритма. Надо найти её экстремум.
Искать собираюсь с помощью метода градиента спуска.
Есть мысль воспользоваться видеокартой для распарралеливания вычислений.
Какая библиотека для этого подходит?

[Pphantom]

Igor_Dmitriev в сообщении #923466 писал(а):

Какая библиотека для этого подходит?

На самый общий вопрос можно дать только самый общий ответ: CUDA или OpenСL (это, правда, не совсем библиотеки, но...).

Однако, вообще говоря, идея кажется сомнительной. Что именно Вы собираетесь распараллеливать?

[Igor_Dmitriev]

Собираюсь распараллеливать вычисление функции в разных точках: чтобы значения функции в разных точках вычислялись не друг за другом, а параллельно.

[Pphantom]

Igor_Dmitriev в сообщении #923492 писал(а):

Собираюсь распараллеливать вычисление функции в разных точках: чтобы значения функции в разных точках вычислялись не друг за другом, а параллельно.

Вот это и кажется неудачным. Графическое ядро - не универсальное, оно совсем не все умеет делать. По большому счету, это очень эффективный инструмент для умножения матриц. А вот считать сложную функцию в точке... подозреваю, что обычный процессор попросту будет эффективнее.

[electric_retard]

Код самой функции можете привести?

[Igor_Dmitriev]

Код сильно длинный, но суть его в том, что функция проделывает линейные и квадратичные операции с массивом, после чего выдаёт результат.
Распараллелить надо не внутренность функции, а вычисление функции в разных точках.

[mustitz]

Pphantom в сообщении #923501 писал(а):

Вот это и кажется неудачным. Графическое ядро - не универсальное, оно совсем не все умеет делать. По большому счету, это очень эффективный инструмент для умножения матриц. А вот считать сложную функцию в точке... подозреваю, что обычный процессор попросту будет эффективнее.

Система команд на видеокарте обьічно чуть несколько более расширена, по сравнению с процессором. Узкое место ветвления. Другое дело, что градиентньій спуск как бьі не заточен под параллельньіе вьічисления, потому как новая точка вьічисляется по предьідущей.

[electric_retard]

А конкретней, что за операции?
Если массив большой, то видеокарточка будет его молоть быстрей цпу.

[Igor_Dmitriev]

Массив от 10 тыс. до 100 тыс. элементов.
Таких массивов от 3 до 10.
Все они одинаковой длины.
Массив проходится последовательно, операции -- сложение, умножение, сравнение, целочисленное деление. Тип - double (но можно и int сделать, если это сильно ускорит).

[Pavia]

Igor_Dmitriev
Для распараллеливания нет. А вот для параллельного исполнения да.
Сходу не назову ищите библиотеку GpGPU с методами оптимизации.
Алгоритм градиентного спуска плохо распалится, так что его надо менять. Либо,
так как параметров в функции более 1000, то лучше делать распараллеливание вычисления самой функции.

Pphantom в сообщении #923501 писал(а):

Вот это и кажется неудачным. Графическое ядро - не универсальное, оно совсем не все умеет делать.

Ошибаетесь оно умеет всё. И обладает базовыми операциями: сложение умножение вычитание, битовые операциями циклами и условными переходами.
Из этого базиса сотрется любой алгоритм. - Собственно поэтому нет ничего удивительного, что NVidia пишет об универсальных ядрах в своих видеокартах.

mustitz в сообщении #923519 писал(а):

Система команд на видеокарте обьічно чуть несколько более расширена, по сравнению с процессором.

Это смотря какой процессор с какой видео картой сравнивать. В х86 команд больше. Хотя в современных видео картах команд прибавилось. Так что скорее их число близкое. Малое число команд должно как раз позволять сделать много, кучу простых процессоров на одном кристалле.

-- Пн окт 27, 2014 20:15:48 --

mustitz в сообщении #923519 писал(а):

Другое дело, что градиентньій спуск как бьі не заточен под параллельньіе вьічисления, потому как новая точка вьічисляется по предьідущей.

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

-- Пн окт 27, 2014 20:21:48 --

Igor_Dmitriev в сообщении #923528 писал(а):

Массив проходится последовательно, операции -- сложение, умножение, сравнение, целочисленное деление. Тип - double (но можно и int сделать, если это сильно ускорит).

Так как в функции есть условия, то она скорее всего не является гладкой. Вы уверенны что градиентный метод вообще работает? Применим к данной функции?
Как правило снижение точности ускоряет вычисления. Double имеет 52 значащих бита, int - 32 бита.

[mustitz]

(Оффтоп)

Pavia в сообщении #923582 писал(а):

mustitz в сообщении #923519 писал(а):

Система команд на видеокарте обьічно чуть несколько более расширена, по сравнению с процессором.

Это смотря какой процессор с какой видео картой сравнивать. В х86 команд больше. Хотя в современных видео картах команд прибавилось. Так что скорее их число близкое. Малое число команд должно как раз позволять сделать много, кучу простых процессоров на одном кристалле.

Да хотя-бьі старенькую Tahiti можно взять. Там операций пободее x86 будет. Включая хитрьіе командьі вьічисления hash для bitcoin. И много много еще чего (см. AMD Open CL extensions).

[Igor_Dmitriev]

Паметров в функции 10-20, оптимизироваться она будет не по тому, что задано в массивах, а по этим 10-20 параметрам.
Какой алгоритм поиска экстремума лучше тогда использовать для параллельных вычислений?

[electric_retard]

Igor_Dmitriev
Какой язык вы используете?
Профилирование проводили? Неужели большую часть времени занимает не вычисление функции, а что-то другое?
Сколько времени вы готовы потратить на освоение GPGPU?)

[mserg]

Есть GPU-пакеты для R. Не уверен, что это то, что надо, но народ пользуется.

[Igor_Dmitriev]

C# или C++.
Изучать досконально я не собирался, я расчитываю на то, что есть оболочка C# или C++ для видеокарт.
Распараллелить функцию не получится, наверное.
Есть ли алгоритмы поиска экстремума для параллельных вычислений?