22 июня автор курса «Разработчик C++» в Яндекс.Практикуме Георгий Осипов провёл вебинар «Вычисляем на видеокартах. Технология OpenCL».



Мы подготовили для вас его текстовую версию, для удобства разбив её на смысловые блоки.

0. Зачем мы здесь собрались. Краткая история GPGPU.
1a. Как работает OpenCL.
1b. Пишем для OpenCL.
2. Алгоритмы в условиях массового параллелизма.
3. Сравнение технологий.

Мы обещали, что разберём написание полноценной программы уже в этой части, но материала оказалось слишком много, и мы разбили эту часть надвое. В первой половине расскажем про основные принципы, которые должен знать каждый OpenCL-разработчик, а во второй напишем программу.

Есть мнение, что для написания эффективного кода для GPU программист обязан понимать архитектуру видеокарты. И это мнение не чьё-нибудь там, а NVIDIA (см. Лекции NVIDIA по GPGPU). Не будем спорить и разберём базовые принципы работы видеокарты.

Kernel и Host

В предыдущей серии шла речь о том, почему не стоит избавляться от CPU. Вот ещё одна причина: центральный процессор необходим для работы видеокарты, ведь именно он отдаёт команды.



В контексте GPGPU центральный процессор называют английским словом host — хозяин. Видеокарта у него как бы в гостях. CPU говорит видеокарте, что именно надо посчитать — готовит задачу и ставит её в очередь. Видеокарта берёт и считает. В комментариях к предыдущей статье отметили, что уже есть технологии, позволяющие обходиться и без CPU, но мы будем рассматривать только те, которые используются широко.

Нужно понимать, что на хосте работает одна программа, а на GPU — другая. Последняя называется kernel. Итак, host — это CPU, kernel — видеокарта. Host даёт команды, kernel считает. Эти слова я буду использовать дальше, и важно их запомнить.

С GPU одновременно могут работать сколько угодно обычных программ, исполняемых CPU. При возникновении задачи она добавляется в очередь и запускается на общих основаниях. Видеокарта может комбинировать задачи и выполнять их в произвольном порядке, чтобы обеспечить наибольшую эффективность, но при этом не нарушить логику работы каждого приложения. Ей неважно, какая программа добавила задачу в очередь.

Теперь о том, как устроены программы, использующие OpenCL. Вы пишете host-код — обычную программу под свою ОС. Кстати, host-код, работающий с OpenCL, можно писать практически на любом языке программирования. Внутри host-программы есть kernel-код в виде обычной строки-ресурса. Он написан на языке C, немножко модифицированном. Программа присылается пользователю. При запуске она ищет динамическую библиотеку OpenCL. И когда программа её находит, то обращается к библиотеке с просьбой скомпилировать кусок kernel-кода. При этом указывается устройство, под которое нужно скомпилировать код. Библиотека OpenCL для этого идёт к драйверу видеокарты, имеющему компилятор. Получается, что библиотека OpenCL — эдакий посредник между вашей программой и драйверами всех устройств, установленных на компьютере, которые могут исполнять OpenCL.



Компиляция происходит непосредственно перед запуском: нельзя заранее скомпилировать kernel-программу и отправить пользователю бинарный код. Потому что вы не знаете, на какой архитектуре будет выполняться ваш kernel. Host-код вы компилируете как обычно, а kernel поставляется исходным кодом и компилируется уже у пользователя.

Геометрия задачи и рабочие группы

Напомню, что OpenCL предназначен для задач массового параллелизма. Это выражается в многократном и синхронном выполнении одного и того же kernel-кода. Одно выполнение kernel называется work item. Для каждой задачи задаётся размерность — она определяет, в виде какой геометрической фигуры удобно представлять себе work item'ы. Иногда удобно располагать их в линию, тогда размерность равна одному. Например, суммирование массива чисел — одномерная задача в work item. Если нужно что-то делать с изображением, тогда один work item — это обработка одного пикселя изображения. Их удобнее расположить в таблице — размерность равна двум. Или задача может быть трёхмерной, если нужно обработать воксели — трёхмерные пиксели.

Work item'ы объединяются в рабочие группы, workgroup. Это важное понятие, смысл которого станет понятен после описания понятия локальной памяти. Все рабочие группы имеют одинаковые размеры. В случае двумерной задачи они будут прямоугольниками, а в случае трёхмерной — параллелепипедами.

При запуске kernel-кода мы задаём следующие параметры.

• Размерность задачи. В виде какой фигуры организованы work item'ы. Обычно допустимы значения 1, 2 и 3.
• Размер задачи, то есть количество work item'ов по каждому измерению. Он называется глобальным размером.
• Размер рабочей группы. Он называется локальным размером.

Размер всей задачи должен нацело делиться на размер рабочей группы. В более новых версиях OpenCL это не обязательно, но мы рассматриваем самую распространённую и базовую версию OpenCL — 1.2.

Рабочие группы делятся на другие группы, которые называются ворпами (warp) или вейвфронтами (wavefront), в зависимости от производителя видеокарты. Я буду использовать термин «ворп». Особенность этого деления в том, что группировка в ворпы происходит автоматически, за кулисами API. Вы не указываете размер ворпа — он зависит только от архитектуры видеокарты.

Допустим, мы майним биткоины. Эта задача одномерная, для неё нет смысла вводить структуру таблицы. Каждый work item — одна элементарная задача, которую нужно вычислить. В данном случае — вычисление одного хеша. Если нужно преобразовать изображение, то work item лучше расположить в таблице. Это двумерная задача, и один work item в ней — вычисление одного пикселя.



Для лучшего понимания работы work item можно представить, что рабочая группа — это рой маленьких роботов. Их много, и каждый робот, work item, исполняет kernel. У него есть данные, одинаковые для всех роботов:

• размер и размерность задачи;
• размер рабочей группы;
• параметры выполнения задачи, которые передал kernel-код. Например, если нужно размыть изображение, тут будет степень размытия;
• данные памяти устройства.

Индивидуальность каждого робота определяется только следующими данными, которые отличают его от остальных:

• номером рабочей группы,
• позицией внутри рабочей группы.

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

У роботов есть доступ к глобальной памяти, которая аналогична обычной RAM, и к локальной, отдельной для каждой рабочей группы. К локальной памяти могут обращаться все work item'ы внутри рабочей группы, но роботы из другой рабочей группы видят другую локальную память.

GPU выполняет рабочие группы как попало, в произвольном порядке. Поэтому нет никаких средств синхронизации между рабочими группами. Смысл рабочих групп — в локальной памяти, которая к тому же очень быстрая. Внутри одной рабочей группы роботы могут синхронизироваться между собой. Например, если они уже выполнили подзадачу, то могут подождать, пока это сделают другие, чтобы вместе приступить к следующей.

Можно представить, что каждая рабочая группа — это отдельный рой, и в нём все роботы связаны между собой через локальную память. Но задачу решают несколько рабочих групп, несколько роёв. И делают это независимо. Как правило, задача kernel сводится к чтению входных данных из глобальной памяти и записи ответа в глобальную же память.

«Синхронное плавание» и какие проблемы оно влечёт

Другая аллегория, которая подходит для описания работы ворпа, — синхронное плавание. В нём спортсменки одновременно выполняют одно и то же действие. Так же устроен и ворп. Он объединяет 32 или 64 work item'а, которые работают синхронно, и производят в один момент одно и то же вычисление, но над разными числами. Нужно понимать: выполняемая инструкция одна и та же, но данные регистров у каждого ворпа свои. Иначе смысла в таком вычислении не было бы.

Роботы в ворпе объединены единым блоком управления. И тут встаёт вопрос: что если они встретятся с ветвлением кода, например с конструкцией if? Предположим, у одних условие выполнилось, а у других нет. Поскольку они работают синхронно, пойти внутрь if должны все work item'ы этого ворпа, даже те, для которых условие ложно. Возникает проблема, называемая дивергенцией.



Те work item'ы, которые не должны были пойти в if, работают в нём вхолостую. Роботы делают вид, что выполняют инструкции, но фактически ничего не делают. При выполнении else они поменяются местами. Те, кто сначала работали вхолостую, в этой ветке начнут работать по-настоящему, и наоборот.

В простых случаях дивергенция не страшна, и не стоит её бояться. Но в более сложных программах она может серьёзно ухудшить производительность. Рассмотрим пример — бинарный поиск.



Из-за дивергенции код бинарного поиска, изображённого на слайде, перестаёт быть логарифмическим и становится линейным.

Разберёмся, как бороться с такими нежелательными явлениями. Совет первый: не использовать рекурсию. С одной стороны, совет бесполезный: в OpenCL рекурсия запрещена. С другой стороны, она может эмулироваться. Тот же бинарный поиск можно реализовать циклом без указанной проблемы.

Совет второй: оптимизируйте код с учётом дивергенции. Если подумать, код можно переписать очень просто: нужно предвычислить интервал, а потом один раз рекурсивно вызвать binsearch. Тогда дивергенция утратит могущество и перестанет быть значимой. Пример показан на слайде.



Дивергенция относится не только к if-else, но также к циклам и switch-case, return, в общем, ко всему, что вызывает ветвление кода. Если в цикле все потоки ворпа, кроме одного, уже завершили свои итерации, то они вместе с отстающим будут продолжать ходить по кругу.

Как выбирать локальные и глобальные размеры

Если размер рабочей группы не делится на размер ворпа, ничего страшного не произойдёт. Но код будет немного неэффективным: видеокарта дополнит рабочую группу до кратного размера «холостыми» потоками.

Чтобы выбрать размер группы, помимо делимости на размер warp нужно учитывать объём локальной памяти. Чем больше рабочая группа, тем больше понадобится памяти, а её размер ограничен. Также у устройств есть жёсткие ограничения на размер рабочей группы, который можно запросить у драйвера.

Часто подходит жёстко зафиксированное значение — 256. Его поддерживают все устройства. Но скажем честно: размер группы не так уж влияет на производительность. Видеокарты умные, они перераспределят нагрузку, даже если вы выберете не самый оптимальный размер. Конечно, совсем маленькие группы делать не стоит: большое их количество влечёт дополнительные издержки.

Следующий вопрос: как распределить выбранный размер рабочей группы? Рассмотрим на примере двумерной задачи. Тут есть минимум три варианта:

• квадратные или прямоугольные рабочие группы, у которых соотношение сторон близко к единице;
• вертикальные полоски;
• горизонтальные полоски.

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

Как мы увидим из следующих частей, в некоторых задачах желательно сократить количество рабочих групп. Следовательно, размер каждой группы должен быть как можно больше. Если жёстко заданный размер вас не устраивает, то нужно действовать следующим алгоритмом:

• узнать размер доступной локальной памяти;
• узнать ограничения устройства на длину, ширину и глубину рабочей группы;
• узнать, сколько локальной памяти требует конкретный kernel для внутренних нужд,
• исходя из всех ограничений выбрать оптимальный размер рабочей группы, делящийся на 64.

После того, как локальный размер выбран, выберите глобальный размер так, чтобы он делился на локальный по всем измерениям и был достаточен, чтобы покрыть задачу целиком. При этом могут возникнуть лишние work item'ы. Но это не страшно: обычно они отметаются if'ом внутри kernel.

На этом подготовка почти закончена. В следующей части статьи приступим к написанию программы.