Comments 17
У AMD есть специальная инструкция для этого
https://www.khronos.org/registry/cl/extensions/amd/cl_amd_media_ops2.txt
amd_median3
Если не хватит, есть еще amd_min3, amd_max3.
В opencl есть char4. Это векторный тип данных который позволяет параллельно выполнять несколько операций. https://www.khronos.org/files/opencl-1-2-quick-reference-card.pdf судя по этому можно выполнять min(char4, char4), потому не надо помнить о вендорно-зависимой __vminu4.
Про bank conflict'ы ни слова. Хотя в принципе я тоже их игнорирую.
Если уже используется локальный буфер а для предзагрузки, то можно увеличить его в 2 раза и закачивать полностью только на первом такте, а все остальные докачивать только новую линию. Ну и тогда нужен индекс для того, чтобы ходить по такому буферу. На 5*5 это вообще жёстко.
Общие пожелания
for (int t = 0; t < 4; ++t)
//...
for (int z2 = 0; z2 < 3; ++z2)
for (int z1 = 0; z1 < 3; ++z1)
Три цикла фиксированного размера. Ну тут просится либо pragma unroll, либо написать свой небольшой кодогенератор, который сгенерирует развёрнутый цикл с подставленными индексами.
if (idy < H — 1)
не рекомендуется использовать в принципе либо использовать тернарные операции, либо
select (который лично мне не нравится за необходимость жёстко задавать определённые типы).
idy * W + idx лишнее умножение
Правильно делать dst_offset = idx
И потом dst_offset += W каждую итерацию.
То же про 3 * z2 + z1 и другие места
Если умножение сильно нужно, но там гарантированно не используется все 32 бита, то есть mul24 и mad24 специально для работы с индексами. Работают в 4 раза быстрее чем честное 32-битное умножение.
Вместо if (idx < W — 1) {} лучше писать if (idx >= W — 1) return; Как минимум код чище, минус одна лесенка.
Дополнительная оптимизация. Убираем const int H, const int W, т.к. скорее всего у нас будет фиксированный размер картинки (не всегда так бывает) и вписываем как константы прямо в код kernel'а получаем еще +5% производительности.
Раз уж я пишу про CUDA, то имею право использовать вендорно зависимые функции. Вы лучше не просто так ссылки пишите, а приведите пример производительности всего того, что упомянули. А так — это голые слова.
На счет буфера А ничего не понял. Может быть имелось в виду то, что повторные загрузки, начиная со второй линии не повторяются — так это и так оптимизируется компилятором и для этого не надо уродовать код.
Про pragma unroll и так было сказано, а описанные вами оптимизации компилятор сделает и так.
Если вы думаете, что тернарная операция сработает быстрее if, то советую обратиться к профилировщику. Видимо для AMD и openCL еще не придумали нормальных инструментов. А вот у Nvidia все по человечески.
Кому нужны ваши 5%? Если бы это были разы, то другое дело.
Если очень интересно реально то показать, то напишите ваш очень оптимизированный код на openCL и запустите на ГПУ Nvidia и посмотрите что получится.
:
а amd_median5 или amd_median7 там есть? И на сколько мощный там ГПУ? + вы не учитываете, что там обращения идут в ЦПУшную память, которая очень медленная.
1. Посмотрите бенчмарки в играх. Поймите, что что-то не так.
2. Загляните в документацию AMD и посмотрите как правильно вынимать нужно с памяти данные, чтобы нормально использовать 4096битную шину.
2.1. Bank conflict'ы там по-жестче чем у nvidia (т.к. их бывает два типа и даже банально по битам получается что нужно разбрасывать массив в памяти сильнее, что для 1920*1080 нереально)
2.2. Вынимать нужно порциями по 16 байт (насколько я помню) (т.е. int4, или char16) это нужно переписать достаточно сильно многие алгоритмы, а если нет — мы не используем мощность HBM на полную)
Ждем HBM2 или Vega, может как-то сгладят недостатки.
По умолчанию всё идет на быструю память видеокарты. Это нужно специально включать pinned memory, если нужен массив памяти больше, чем есть на видеокарте.
amd_median5 и median7 нету по понятной причине. Каждая операция работает с максимум 4 аргументами. amd_median3+amd_min3+amd_max3 достаточно, чтобы за 3 операции отсортировать 3 набора по 4 числа (т.к. int4).
По поводу производительности, посчитайте на досуге производительность AMD/$ и nvidia/$, в чистых tflops/$. Я за те же деньги поставлю больше мощности. В моем случае это 100% можно сделать т.к. у меня просто большой поток однотипной работы, которая не зависит друг от друга. (Прим. Да, это не всем подойдет)
Рассмотрим выполнение kernel'а
1. Скопировать с медленной CPU памяти в быструю GPU.
2. Выполнить на быстрой GPU памяти.
3. Скопировать обратно в медленную CPU память.
Итак. У нас на самом-то деле bottleneck по пропускной способности никуда не делся. Мы не можем выполнять быстрее, чем скорость передачи CPU памяти. А вот задержка стала меньше.
median_5
Сортируем первые 3 элемента. 3 операции
Сортируем последние 3 элемента 2 операции, т.к. max нам не нужен т.к. это глобальный максимум.
Снова сортируем первые 3 элемента. 2 операции т.к. min нам не нужен т.к. это глобальный минимум
Смотрим на 3 центральных элемента и выполняем median3. 1 операция
3+2+2+1 = 8 операций.
Возможно, можно за меньшее количество операций.
Для попарных сравнений операций понадобится явно больше. Плюс я уже писал, что можно захватывать по 4 числа и сортировать их параллельно.
а применить то как median_5 к нахождения медианы в квадрате 5х5?
Алгоритм 1.
1. Движем окно вдоль какого-то направления (X или Y)
2. На каждую итерацию добавляем 5 пикселей и убираем 5 пикселей.
3. Те 5 пикселей, которые добавляем, сортируем сразу и храним все 5 итераций сортированными (3 операции для опеределения предварительных min, max, avg, 3 операции для определения самого минимального, 3 операции для определения самого максимального, 3 операции дабы отсортировать оставшиеся 3 элемента. Итого 12 операций самым наивным методом)
4. Дальше у нас есть массив из 25 элементов, которые частично отсортированы. Утверждение 1. Из всех минимумов только самый большой может быть средним. (аналогичное утверждение для максимума). Используя две операции min и две операции max находим нужные элементы. Эту и все дальнейшие операции выполняем в другом буфере.
5. Необходимо найти среднее из 5*3+2 элементов, о которых мы кое-что уже знаем т.к. 5 троек у нас отсортированы. Расположим эти элементы следующим способом сначала самый минимум(из шага 4) потом все минимумы из троек, потом средние из троек, потом максимумы из троек, потом самый максимум(из шага 4). Дальше подбираем необходимое количество итераций следующего алгоритма:
Проходимся по тройкам чисел с пересечением в 1 число. Ддля каждой тройки осуществляем сортировку этих трёх элементов. После такого прохода справа будет самый большой элемент. Его мы теперь можем гарантированно игнорировать. Проходимся влево. Слева будет самый минимальный элемент, его тоже можно игнорировать. На краях можно сэкономить одну операцию т.к. нам не надо записывать.
Первая итерация будет проходить на буфере размером N=5*3+2. Количество операций сравнения 3 на 3 числа таких троек будет (N-1)/2 = 8. Т.е. 8*3 операции. 2 прохода -> 8*3*2. Минус на краях = 8*3*2-2 = 46 операций.
Вторая итерация будет проходить на массиве на 2 элемента меньше. Сортируем до конца. Получаем точный ответ. Один из самых наивных подходов, но точный. Можно пробовать другой подход к сортировке.
Алгоритм 2.
Первые 4 операции идентичны алгоритму 1
5. Введём операцию сортировки троек. Мы будем сортировать центральный элемент и элементы, которые отстоят от него на +i -i. Применяя последовательно такую операцию мы добьемся момента, когда слева будут элементы меньше центрального, а справа будут элементы больше от центрального. Количество итераций для хорошей точности вычисляется либо аналитически, либо перебором.
Алгоритм 3.
Первые 2 операции идентичны алгоритму
3. Записываем только медианы каждой пятерки (т.е. по факту используем median_5, которая работает за меньше чем 12 операций)
4. Просто находим медиану из 5 медиан.
Данный алгоритм самый быстрый, но дает хуже всего точность и его нельзя принципиально сделать полностью точным.
специально для этого комментария в статье присутствует уточнение. На данный момент нет фиксированной скорости передачи данных между ГПУ и ЦПУ. Также в данном направлении постоянно идет развитие. К примеру, сейчас есть стандарты PCIe 2.0/3.0 и готовится к релизу 4.0. Скорость у них вполне себе известная, для 2.0 — 8 ГБ/сек, для 3.0 — 15ГБ/сек. И я думаю не трудно посчитать самому сколько это будет передаваться. Другое направление — NVlink со скоростью порядка 40-80 ГБ/с.
Но как бы ни была быстра шина между ГПУ-ЦПУ, скорость работы ГПУ все равно будет быстрее и если посмотреть текущие тенденции развития ГПУ и ЦПУ, можно заметить, что ГПУ повышает вычислительную мощность с каждым новым поколением гораздо больше, чем ЦПУ.
Ну и в данном случае предполагалась либо потоковая обработка, либо последовательность фильтров или обработки изображения. Ясное дело, что только одну картинку обрабатывать на ГПУ нет смысла, да и написано это все было ради того, чтобы показать простоту разработки под ГПУ, по отношению к использованию AVX.
Оптимизация обработки изображений с использованием GPU на примере Медианной фильтрации