×Закрыть

OpenCL (CUDA) алгоритмы оптимизации

Всем привет.
А давайте поговорим за алгоритмы оптимизации, что реализуются на OpenCL (CUDA).

Я как-то порыскал по инету и ничего толком не нашел, кроме некоторых статей.

А так понимаю, что их реализация на GPGPU чрезвычайно сложна, ибо все эти алгоритмы итерационные и они не подходят для GPGPU и смысл имеет только реализовывать алгоритмы, основанные на Монте-карло подходе?
Для остальных только CPU?

Или я плохо искал и ошибаюсь?

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

LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

дык любой популярный deep learning framework идет с поддержкой GPU и кучей оптимизационных алгоритмов, которые, как правило, можно использовать отдельно от всего остального. я так пользовался torch7/optim, но, я думаю, tensorflow и пр. могут не хуже

А давайте поговорим за алгоритмы оптимизации, что реализуются на OpenCL (CUDA).
Это немного другое.

тогда я не понимаю, что именно тебе нужно. в том же торче можно использовать и CUDA, и OpenCL бекенд, а алгоритмы при этом те же, из того же пакета optim. берешь свой тензор, загоняешь в GPU, пишешь свою функцию, которая считает значение и градиент в данной точке, скармливаешь все это в какой-нибудь LBFGS или AdaDelta, и будет тебе счастье. впрочем, я так и не понял, какую задачу ты решаешь. расскажи, что именно ты сейчас делаешь, что тебя не устраивает, и чего ты хочешь добиться. тогда, может, и помощь будет больше по теме.

ru.wikipedia.org/...рия:Алгоритмы_оптимизации
Градиентные, неградиентные (в частности Брента) и еще стадо их.

блин. я знаю, что такое оптимизация — я просто понять не могу, что ТЕБЕ нужно. какую задачу ты решаешь? или просто поговорить хочется?

Аналог матлабовской fmincon мне нужен.

ах, так у тебя constrained optimization? ну дык и сказал бы сразу. тогда хз, все пакеты для ML, что я знаю, unconstrained. попробуй построить лагранжиан и свести задачу к оптимизации unconstrained dual problem.

се пакеты для ML, что я знаю
Перечисли их, плиз.
свести задачу к оптимизации unconstrained dual problem.
Эт можно.

дык писал же уже. я использовал torch7 и немного tensorflow — там точно есть; еще из слов для погуглить попробуй MXNet, Theano, Caffe, CNTK, Leaf, но за эти я не ручаюсь

Ээ OpenCL — это С. Очень многопоточный. Если можешь на С переложить и распараллелить, то и на OpenCL переведёшь без особых проблем. Я не гуру, писал сам ручками фильтр 5×5 и Reed-Solomon декодера код переводил. Профит был. Для фильтра дохрена профита, сотни раз, для декодера меньше, но достаточно слабая видюха таки нагнула многопоточную реализацию на CPU и код там был весьма страшен и не оптимизирован.

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

Посмотреть исходники рендерера Cycles, DirectCompute, C++ AMP.

Я пытался 2 года назад переложить на GPU один очень медленный алгоритм (image processing). Было немного наработок на java. Короткие выводы :

GPU полны багов и проблем. Шаг вправо, шаг влево и вся система висит. Помогает только hard reset.
Разного рода врапперы вокруг GPU API — говно на палочках. Куча проблем. Очень и очень все сырое.

Потратил несколько недель на чтение доки и попытки кодинга. Так и не смог достичь результат.

Мои имхо — быстро и с наскоку не получится. Надо будет довольно сильно погрузится и быть говтоым тратить много времени.

Готовых алгоритмов — очень мало.

GPU полны багов и проблем. Шаг вправо, шаг влево и вся система висит. Помогает только hard reset.
С этого места по-подробнее плиз.

К сожалению все наработки канули в лету. Не осталось ни примеров кода, ни железа.

не знаю, не знаю
пока проблем на opencl не было, юзаю обычную обертку cloo для шарпа

Получается-ли реальный выйгрыш в производительности?
По синтетическим тестам красиво всё выглядит, но синтетические на то и синтетические.

Недавно запускал ViennaCL тест, так HD6770 всего в 4-5 раз быстрее AMD 1055 проца оказалась.
GTX 1060 или 970 дадут-ли реальный прирост в сравнении в двумя Ксеонами (с частотой около 2 ГГц) по 8 ядер?
Т.е. имеет-ли смысл заморачиваться на GPGPU вообще. Или лучше процессор заменить на более современный и получить те же результаты?

Есть выигрыш, в некоторых случаях на порядок. На моих задачах hd6770 гораздо быстрее чем i5 3 ГГц. Но опять таки — у меня узкое место алгоритма хорошо распараллеливается на 100500 блоков гпу. Что до замены проца, то в моем случае это тоже даст прирост, т.к. алгоритм параллельно реализован для проца и для гпу. На мелких наборах данных проц быстрее, т.к. нет накладных расходов на пхание данных на видяху и обратно.

в некоторых случаях на порядок.
Если даже порядок 10-тичный, то не всегда оно стоит того. Если раз в 50-100, то это уже интересно и GPGPU стоит того в среднем случае.
Только вот итерационные алгоритмы очень сложно параллелить. Один мой знакомый диссер на этом защитил, причем только на одном узком классе алгоритмов.
Прозрачно у меня только 16-32 потока получаются в параллель, дальше нужно сильно заморачиваться — это внутри целевой функции распараллеливание, не собственно итерационного алгоритма. Ну и данных для целевой функции прилично нужно (они не меняются) — матрица 3000×3000 (влезет-ли она в GPGPU и какую карту).

Т.е. думаю, есть-ли смысл в заморачивании с GPGPU или лучше ксеоны по разумной цене подобрать и на них мой старенький АМД 1055 заменить? На них я могу 16 ядер получить плюс гипертрединг.

Просто сильно смущает море работы по запихиванию итерационного алгоритма в GPGPU с неизвестным результатом. Вот поэтому и поднял эту тему, обсудить.

Стоит еще как. Когда объемы такие, что загибается 48 головый сервак на оптеронах, то выигрыш больше. А матрица влезет, вопрос только в том что если она вся целиком используется для каждого потока, то будут накладные расходы на обращение к глобальной памяти, а вот если ее можно на мааленькие кусочки разобрать и по частям скопировать в локальную память блоков гпу, то тогда все будет очень даже шустро

Целиком вся. Она не меняется и только читается, но вся. Не можно, конечно не всю использовать, но надо сильно алгоритм менять. Это фактически функция на равномерной сетке.
Ну и понятно что такое железо меня не интересует. Мне надо крутиться в обычном.

Ну и это только 16-32 потока вычислительных будет, а не пару сотен. Т.е. имеет ли смысл GPGPU для такого?

Если потоков только 16-32, то думаю что нет. Если бы 1000 и больше, тогда был бы смысл

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

Интересно вообще послушать, для каких задач GPGPU имеет смысл.
Только конкретно. От скольки потоков, каких объемов данных, подводные камни.

Потоки — gpu-z в помощь. Она заодно и нагрузку на блоки и память видяхи покажет. В моем случае меньше 2 х количество блоков я на гпу не пускаю, нет смысла. Объем данных сильно зависит от задачи. У меня достаточно много — до десятков гигабайт на весь процесс оптимизации. Но этот объем хорошо разбивается — в очереди заданий может быть и 500к.
Да, сам алгоритм — расчет FF для генетической оптимизации.

еще кстати очень хорошо если удается использовать simd-типы данных, аля int4/int8 и т.д. (ускорение фактически в n раз), мне в этом смысле не повезло — слишком часто нечетная размерность в матрицах, а морочится с учетом фейковых элементов слишком сложно. хотя может со временем и придется поизвращаться если текущей производительности станет мало.

А как оценить количество потоков для конкретной видео карты?
Это очень трудная задача. Например, если взять дохлый автомобильный Intel Iris на базе ApolloLake процессора, то там 48 EU — это выделенные процессоры, 7 ниток или клеток (cell) или слайсов (кто как называет) на EU — это нужно общее количество регистров общего назначения расшарить между нитками (их около 200), если расшарить не получается, то уменьшаешь количество нитей, если компилятор плохой и использует все 200 регистров в одном процессоре, то доступна только одна нить. В каждой ните VLIW ALU, каждая комманда которого может обрабатывать от 8 до 32 задач, но задачи должны быть одинаковые, т.к. это простое SIMD, где одна комманда и множество данных. Т.е. в идеальном случае получается 48*7*32=10752 вычислений параллельно. И это, напомню, дохлый, обрезанный 4W ApolloLake с пониженными частотами.

Я на Compute Shaders написал простенький рейтрейсер: s14.postimg.org/3sexetmbl/screenshot.jpg , так вот когда запустили его в автомобиле на FullHD дисплее оно дало 84 кадра в секунду, народ просто дар речи потерял. Для сравнения — самый жирный PowerVR RGX (можно взять Apple Pro iPad 9 или 12 дюймов) выдал со скрежетом 8 fps.

Для сравнения ATI/AMD Radeon HD 8790M (Mars-XTX) выдал 160 fps, а десктопный Intel Iris GT3e (Skylake) 280 FPS. При этом первая видеокарта в играх просто летает, а интелловская тормозит безбожно :) Вот она сила оптимизации под конкретную платформу.

А как вообще считают пересечение луча (прямой) с поверхностью.
Можно параметрически задать прямую, поверхность через интерполяцию по сетке и получить точку пересечения. Самый тупой подход.
А вот GPGPU просто считают пересечение с каждым треугольником (седлом, если по прямоугольнику)?
А может уже есть готовые либы для этого?

А как вообще считают пересечение луча (прямой) с поверхностью.
Как угодно :) Ты же автор кода. Я взял готовую откуда-то, уже не помню откуда:
Intersect intersect(Ray ray, Sphere sphere) {
    vec3 oc = sphere.position - ray.origin;
    float l = dot(ray.direction, oc);
    float det = pow(l, 2.0) - dot(oc, oc) + pow(sphere.radius, 2.0);
    if (det < 0.0) return miss;

    float len = l - sqrt(det);
    if (len < 0.0) len = l + sqrt(det);
    if (len < 0.0) return miss;
    return Intersect(len, (ray.origin + len*ray.direction - sphere.position) / sphere.radius, sphere.material);
}                                                                                                                     
А вот GPGPU просто считают пересечение с каждым треугольником (седлом, если по прямоугольнику)?
Если ты спрашиваешь про GPU, то там нет рейтрейса, обычное умножение на матрицу показывает будет ли объект (треугольник) видимый или за пределами области видимости, вне поля зрения, но там принцип рендеринга совершенно другой, нежели в рейтрейсе. А в GPGPU ты всё делаешь сам, на то оно и GP.
А может уже есть готовые либы для этого?
Т.е. нету.
И в случае с GPGPU просто проверяется пересечение с каждым треугольником или другой частью поверхности (ну то бишь интерполятор прилепить)?
Т.е. нету.
Да я даже не искал, я просто взял чей-то доступный сишный код рейтрейсера и переписал его для compute shaders, попутно добавив туда кучу плюшек типа radiosity, photon emission для получения реалистического освещения.
в случае с GPGPU просто проверяется пересечение с каждым треугольником или другой частью поверхности (ну то бишь интерполятор прилепить)?
Там нет треугольников, есть параметрическя поверхность. Читай :) en.wikipedia.org/...osity_(computer_graphics

Мне очень не хотелось в GPGPU именно лезть. Это в нем придется плотно разобраться. Думал, что уже написали подобное и можно просто заюзать.

Фактически поверхность — это некоторая функция на прямоугольной сетке в простейшем случае. Можно в каждой ячейке как взять два треугольника, так и проинтерполировать ее (используя соседние узлы — порядок интерполяции и метод), так и делоне триангуляцию заюзать — это неважно.

Важно, что в GPGPU мы просто находим пересечение с поверхностью в каждой ячейке — это выполняется параллельно на GPGPU. Я правильно понимаю?

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

Важно, что в GPGPU мы просто находим пересечение с поверхностью в каждой ячейке — это выполняется параллельно на GPGPU. Я правильно понимаю?
Да, в описанном случае GPGPU обрабатывал параллельно 10К лучей. Плохо, что если луч уже встретился с поверхностью и отразился (я делал классических 16 проходов), то мы новый не можем пустить, а отражаем его в бесконечность и тупо считаем пустоту, пока последний луч не будет просчитан.

Вот второе предложение мне и не надо. Мне нужно только первое.
И луч один, но поверхность задана на сетке 3000×3000 и аналитически не представляется. Т.е. некая функция f(x,y) на сетке.
Можно спроецировать прямую на некоторую плоскость (она уже есть) и проверить только по тем прямоугольникам, через которые проходит проекция прямой.
Вот и думаю, что проще, GPGPU заюзать и по всей сетке его прогнать или только по 3000*3 прямоугольникам проверить на CPU.
Или градиентный спуск быстрее все же будет.
Похоже, что все это проверять придется. Последний вариант уже есть, но медленно получается.

У меня пока только в планах написание рейтрейсера.

Ничего страшного. Каждый программист в своей жизни должен написать:
1) Рейтрейсер
2) Класс для логирования сообщений.
3) Архиватор
4) Калькулятор

5) Компилятор или интерпретатор.

Логирование было, очень нравится и на форму и в файл

Архиватор — с теорией знакомился

Калькуляторы были

Конвертеры разнообразные были

Немного тестов с алгоритмом горения

Вывод спрайтов на ассемблере с использованием mmx

Спрайты на sse в процессе

Формы с внешним видом из растрового изображения

Рендерер в планах, с gi, ao

Редактор для 3d моделирования развертки и текстурирования в планах

Редактор спрайтов и 2d карт в планах

Написание языка программирования — было знакомство с теорией, в планах реализация в виде макросов к 2d и 3d редакторам выше

CPU не сравнится с GPU, так как CPU предназначен для задач общего рода, а GPU ориентирован на быструю обработку больших объемов данных, и частота памяти выше и шина. И чем шина больше тем скорость карты выше, с 256, 384 бит и выше с GDDR5 видеокарты должны быть с очень хорошими показателями. Мне кажется что если видео в 4 раза быстрее CPU это довольно хороший показатель. Но и у CPU есть инструкции SSE, использование которых тоже может добавить производительности. Например, функция копирования на ассемблере будет небольшим бонусом к GPU.

И еще, возможно стоит так-же учитывать и поддерживаемую версию cuda, opencl, возможно более новая версия может обладать подходящими возможностями. Ну это если на случай апгрейда.

матрица 3000×3000 (влезет-ли она в GPGPU и какую карту).
Какие проблемы. Карты нынче по 2 гига и более имеют на борту.

И для матриц есть developer.nvidia.com/cublas

матрица 3000×3000 (влезет-ли она в GPGPU и какую карту).
Ха, испугал ежа голой задницей :) У тебя небось максимальное разрешение текстуры 4096×4096 или даже 8192×8192, с четырьмя 64 битовыми компонентами. Для текстуры 4096×4096 с 4 double компонентами это всего лишь 512Mb — сущие понты для современного GPGPU.

Вот тут главное знать устройство современных GPU, если ты передаёшь данные как массив, то, боюсь ты попал, обращение к памяти будет стоить очень дорого, но если ты передашь данные как текстуру, например типа R64_DOUBLE, если у тебя каждый элемент массива — дабл, то ты сможешь использовать очень оптимизированный tiler cache, но доставать данные нужно через сэмплер, с выключенными интерполяциями и т.п., чтобы получить данные без предварительной обработки, как они есть. Соответственно задачи нужно запускать не по строчке линейно, а используя тайлы, например 64×64, 128×128, т.е. разбить изначальную матрицу на мини-квадратики, тогда скорость работы GPGPU можно ускорить на порядок. Просто хозяйке на заметку, GPGPU — это всё-таки не CPU, поэтому мозг нужно немного выворачивать при программировании GPGPU.

Ясненько. Пока CPU мне больше нравиться в моем случае. Переписать (или попробовать от GSL) еще реализацию Brent’а на плюсах. На матлабе я уже уперся в его скриптовость в реализации этого алгоритма. Просто у меня не получается такое количество потоков, что имеет смысл для GPGPU, максимум 16 потоков.

А разве дабл арифметика не порезана по скорости вне Tesla линейки?

Не теслой единой ...

Видел как-то сравнение обсчета нейронных сетей. Они умудрились в С++ сделать дико неэффективную структуру с объектом на каждый нейрон, веса произвольно раскиданы по памяти, попаданий в кэш мало. В куде реорганизовали данные, чтобы потоки могли сразу большой последовательный кусок считывать. Итого разница в 20-30 раз.

Если реорганизовать С++ код похожим образом + векторизовать, разница начала составлять всего 3 раза без учета гоняний данных по шине

Конкретно библиотек, решающих данный тип задач не встречал, но быстрый поиск дал пару результатов: github.com/painnick/lbfgsb-on-gpu и github.com/jwetzl/CudaLBFGS . Если есть понимание как эти алгоритмы работают, то можно попробовать использовать cuSOLVER, Thrust, cuBLAS и т.п. (видел несколько реализаций) , скорее всего, будет быстрее чем писать напрямую используя OpenCL или CUDA (предполагая что ты с ними не знаком).

Если есть понимание как эти алгоритмы работают
Есть, а также есть понимание, что это приличный объем написания и особенно отладки.
Почему и спрашиваю, а вдруг кто уже написал и выложил в opensource.

За ссылки спасибо. Сам их сходу не нашел, всё больше на статьи выкидывает (а это опять самому писать).

В какой области ? Итерационные (типа распространения волны) вполне нормально. На OOPSLA большая часть оптимизационного потока была про GPU, к примеру — 2016.splashcon.org/...-graph-algorithms-on-gpus

Методы поиска оптимумов — их много и разных от тех, что без производных, градиентные и т.п.

Ну и были-ли представлены реализации и есть-ли они в opensource. Ну и можно-ли скачать материалы конфы где бесплатно?

Подписаться на комментарии