SIMD и обработка изображений
Обработка изображений (здесь мы сознательно ограничиваем в себя только растровыми картинками и опускаем широкий класс векторных изображений), как правило, представляет собой набор простых операций, которые применяются к каждой точке изображения. Если учесть, что цветовые каналы, из которых состоит точка изображения (пиксель) обычно представлены в виде целых чисел небольшой размерности, то обработка изображения сводится к огромному числу однотипных операций над 1-2 байтными целыми числами.
Выполнение подобных операций при помощи процессорных команд общего назначения не совсем эффективно, так как они оптимизированы для обработки 4-8 байтных чисел. Фактически при работе с 1 байтными числами их эффективность будет падать в 4—8 раз. Производители процессоров уже давно предложили достаточно эффективное решение, для увеличения производительности при работе с такими данными – SIMD (Single instruction, multiple data) – наборы векторных инструкций, которые позволяют обрабатывать большое количество данных за одну операцию. Если рассматривать платформу x86, то на ней существует большое количество SIMD-расширений: MMX, 3DNow!, SSE, SSE2, SSE3, SSEE3, SSE4.1, SSE4.2, AVX и AVX2. Большинство из этих расширений предназначены для векторной обработки вещественных чисел. Если касаться векторных целочисленных инструкций, то можно выделить наборы команд MMX, SSE2 и AVX2, которые соответственно содержат операции для работы с 8, 16 и 32-байтовыми векторами. Расширение MMX впервые появилось в процессоре Pentium MMX в 1997 году и в настоящее время представляет скорее исторический интерес, так как все современные x86 процессоры поддерживают более совершенный набор команд SSE2, который был впервые представлен в процессоре Intel Pentium 4, вышедшем в 2000 году. Однако жизнь не стоит на месте, и в 2013 году вышло семейство процессоров iCore 4-го поколения с поддержкой инструкций AVX2, которые в скором будущем получат широкое распространение.
И так, у нас есть какой-нибудь алгоритм, написанный на С++, осуществляющий обработку изображения, скорость которого критична для данного приложения (такие алгоритмы чаще всего встречаются при обработке видео). Учитывая наличие SIMD расширений процессора, которые позволяют в потенциально ускорить скорость выполнения алгоритма в 10 и более раз, логичным будет попытаться их каким-либо образом задействовать. И так встает вопрос на сколько это просто сделать? Ниже я постараюсь на него ответить, подробно перечислив все плюсы и минусы, с которым придется столкнуться разработчику в процессе задействования SIMD расширений процессоров в своем проекте
Плюсы
- Применение SIMD инструкций позволяет осуществить одновременную обработку сразу над несколькими наборами исходных данных, тем самым значительно уменьшив общее время работы алгоритма.
- Расширенные наборы инструкций содержат специализированные команды (например нахождение среднего или максимального числа для пары чисел, сложение или вычитание с насыщением), которые заменяют собой несколько инструкций общего назначения. Применение этих комманд может дать дополнительный весьма значительный выигрыш в скорости исполнения.
- Для того, что бы задействовать SIMD расширения процессора, вопреки распространенному заблуждению, совсем не обязательно использовать ассемблер. Все современные компиляторы C++ поддерживают так называемые intrinsic – функции, которые компилятор напрямую транслирует в команды для CPU. Потому при задействовании SIMD, можно полностью оставаться в рамках синтаксиса С/С++ в привычной IDE.
Минусы
- Потеря универсальности кода, который задействует расширения процессора. Действительно, существует большое количество процессорных архитектур, каждая из которых может содержать (а может и нет), свой собственный набор векторных инструкций. Потому или нам приходится ограничивать применимость нашей программы какой-либо конкретной архитектурой, или писать несколько реализаций алгоритма для каждой из требуемых нам архитектур.
- Входные и выходные данные должны лежать в памяти упорядоченно (желательно последовательно, хотя возможно достаточно эффективное извлечение каждого второго или каждого четвертого элемента). Чем плотнее лежат входные и выходные данные, тем меньше операций по их переупорядочиванию нам придется исполнить и тем эффективнее будет наш алгоритм. Указанное требование заставляет пересматривать способы хранения данных, например, хранить цветное изображение в виде набора отдельных цветовых плоскостей, а не в единой плоскости с чередованием цветовых каналов для каждой точки (как в BGR-24).
- Желательно, что бы входные и выходные данные данные были выровнены в памяти (по 16 байтной границе для SSE2, по 32 байтной границе для AVX2), так ка чтение и сохранение выровненных данных происходит значительно быстрее. В случае, если мы контролируем создание входных и выходных данных, то их выравнивание достигается применением специальных аллокаторов памяти. В противном случае, мы должны или смириться с потерей скорости работы алгоритмов, или писать две версии алгоритма для случая выровненных или не выровненных данных.
- Если при обработке изображений в регистрах общего назначения, проблема переполнения чисел в процессе вычислений практически не встречается (мы просто используем стандартный тип int, который вряд ли переполнится при работе с 8 битными данными), то при обработке с помощью векторных инструкций эту проблему нужно постоянно держать под контролем. Если, например, в алгоритме возможно переполнение 8-битных данных в процессе расчета, то мы должны их преобразовать их в 16-битные, выполнить расчет и сделать обратное преобразование. Конечно для этого существуют специальные векторные инструкции паковки и распаковки векторов, но все это замедляет алгоритм, равно как и то, что векторные инструкции над 16-битными данными обрабатывают в два раза меньше данных за 1 раз, по сравнению с 8-битными.
- При обработке векторных инструкций, отсутствует возможность условного исполнения команд для каждого элемента. В некоторых случаях условные переходы можно эмулировать, для чего приходится выполнять обе ветки кода, а затем объединять результаты их работы. Это естественным образом сказывается на производительности алгоритма и если код насыщен условными переходами, то смысл в SIMD оптимизации теряется.
- При обработке изображения точки, которые располагаются на границах, как правило обрабатываются особым образом. Для векторных инструкций дело осложняется тем, что в граничном блоке точек часть точек обрабатывается по общему алгоритму, а часть по алгоритму для граничных точек, что значительно усложняет разработку.
- Ширина изображения не всегда бывает кратной размеру вектора. Потому для обработки изображений с произвольной шириной необходимо особым образом обрабатывать последний блок в строке, который может быть заполненным лишь частично.
- Не все математические операции, которые доступны для скалярных регистров имеют свои аналоги для векторных инструкций. Например, отсутствует целочисленное деление. В этих случаях приходится или отказываться от векторизации, или пытаться эмулировать их при помощи имеющихся инструкций, что приводит к снижению эффективности и усложенению кода.
- Читаемость кода, содержащего векторные инструкции, как правило значительно уступает читабельности скалярного кода.
- Отладка кода, содержащего векторные инструкции значительно сложнее, так как программисту приходится отслеживать корректность не отдельных скалярных значений, а целых векторов. А современные IDE, не смотря на значительный прогресс в этой области, отображают векторные данные значительно хуже скалярных.
- Опыт показывает, что написание корректно работающего алгоритма использующего векторные инструкции практически не возможно, без наличия юнит тестов, которые покрывают все характерные случаи, в которых он будет использоваться.
Как видно из выше перечисленного, использование SIMD расширений процессора может дать большой прирост производительности, но в тоже время сопровождается существенным усложнением процесса разработки. Стоит ли одно другого зависит от условий конкретного проекта и остается на усмотрение разработчика.
Послесловие
Автор данной статьи, по роду своей деятельности (разработка алгоритмов для видео аналитики) посвятил довольно большое время процессу оптимизации алгоритмов обработки изображений на C++ при помощи различных векторных инструкций (в основном это SSE2 и AVX2). В частности, результатом этой работы стала библиотека алгоритмов обработки изображений на С++ с открытым исходным кодом, которая имеется в открытом доступе. Если читатели сочтут эту тему интересной, то я готов написать несколько статей, которые будут описывать особенности оптимизации на конкретных примерах.
Автор: ErmIg
