Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 5
×

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

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

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

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

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

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

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

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
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 и пр. могут не хуже

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Потоки — 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. При этом первая видеокарта в играх просто летает, а интелловская тормозит безбожно :) Вот она сила оптимизации под конкретную платформу.

А как вообще считают пересечение луча (прямой) с поверхностью.
Как угодно :) Ты же автор кода. Я взял готовую откуда-то, уже не помню откуда:
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.
Т.е. нету.
Да я даже не искал, я просто взял чей-то доступный сишный код рейтрейсера и переписал его для compute shaders, попутно добавив туда кучу плюшек типа radiosity, photon emission для получения реалистического освещения.
в случае с GPGPU просто проверяется пересечение с каждым треугольником или другой частью поверхности (ну то бишь интерполятор прилепить)?
Там нет треугольников, есть параметрическя поверхность. Читай :) en.wikipedia.org/...osity_(computer_graphics
Важно, что в GPGPU мы просто находим пересечение с поверхностью в каждой ячейке — это выполняется параллельно на GPGPU. Я правильно понимаю?
Да, в описанном случае GPGPU обрабатывал параллельно 10К лучей. Плохо, что если луч уже встретился с поверхностью и отразился (я делал классических 16 проходов), то мы новый не можем пустить, а отражаем его в бесконечность и тупо считаем пустоту, пока последний луч не будет просчитан.

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

Ничего страшного. Каждый программист в своей жизни должен написать:
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.

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

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

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

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

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

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

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