...

пятница, 29 ноября 2013 г.

Стоит ли оптимизировать обработку изображений на С++ при помощи SIMD?

SIMD и обработка изображений




Обработка изображений (здесь мы сознательно ограничиваем в себя только растровыми картинками и опускаем широкий класс векторных изображений), как правило, представляет собой набор простых операций, которые применяются к каждой точке изображения. Если учесть, что цветовые каналы, из которых состоит точка изображения (пиксель) обычно представлены в виде целых чисел небольшой размерности, то обработка изображения сводится к огромному числу однотипных операций над 1-2 байтными целыми числами.

image



Выполнение подобных операций при помощи процессорных команд общего назначения не совсем эффективно, так как они оптимизированы для обработки 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 расширений процессоров в своем проекте


Плюсы





  1. Применение SIMD инструкций позволяет осуществить одновременную обработку сразу над несколькими наборами исходных данных, тем самым значительно уменьшив общее время работы алгоритма.

  2. Расширенные наборы инструкций содержат специализированные команды (например нахождение среднего или максимального числа для пары чисел, сложение или вычитание с насыщением), которые заменяют собой несколько инструкций общего назначения. Применение этих комманд может дать дополнительный весьма значительный выигрыш в скорости исполнения.

  3. Для того, что бы задействовать SIMD расширения процессора, вопреки распространенному заблуждению, совсем не обязательно использовать ассемблер. Все современные компиляторы C++ поддерживают так называемые intrinsic – функции, которые компилятор напрямую транслирует в команды для CPU. Потому при задействовании SIMD, можно полностью оставаться в рамках синтаксиса С/С++ в привычной IDE.


Минусы





  1. Потеря универсальности кода, который задействует расширения процессора. Действительно, существует большое количество процессорных архитектур, каждая из которых может содержать (а может и нет), свой собственный набор векторных инструкций. Потому или нам приходится ограничивать применимость нашей программы какой-либо конкретной архитектурой, или писать несколько реализаций алгоритма для каждой из требуемых нам архитектур.

  2. Входные и выходные данные должны лежать в памяти упорядоченно (желательно последовательно, хотя возможно достаточно эффективное извлечение каждого второго или каждого четвертого элемента). Чем плотнее лежат входные и выходные данные, тем меньше операций по их переупорядочиванию нам придется исполнить и тем эффективнее будет наш алгоритм. Указанное требование заставляет пересматривать способы хранения данных, например, хранить цветное изображение в виде набора отдельных цветовых плоскостей, а не в единой плоскости с чередованием цветовых каналов для каждой точки (как в BGR-24).

  3. Желательно, что бы входные и выходные данные данные были выровнены в памяти (по 16 байтной границе для SSE2, по 32 байтной границе для AVX2), так ка чтение и сохранение выровненных данных происходит значительно быстрее. В случае, если мы контролируем создание входных и выходных данных, то их выравнивание достигается применением специальных аллокаторов памяти. В противном случае, мы должны или смириться с потерей скорости работы алгоритмов, или писать две версии алгоритма для случая выровненных или не выровненных данных.

  4. Если при обработке изображений в регистрах общего назначения, проблема переполнения чисел в процессе вычислений практически не встречается (мы просто используем стандартный тип int, который вряд ли переполнится при работе с 8 битными данными), то при обработке с помощью векторных инструкций эту проблему нужно постоянно держать под контролем. Если, например, в алгоритме возможно переполнение 8-битных данных в процессе расчета, то мы должны их преобразовать их в 16-битные, выполнить расчет и сделать обратное преобразование. Конечно для этого существуют специальные векторные инструкции паковки и распаковки векторов, но все это замедляет алгоритм, равно как и то, что векторные инструкции над 16-битными данными обрабатывают в два раза меньше данных за 1 раз, по сравнению с 8-битными.

  5. При обработке векторных инструкций, отсутствует возможность условного исполнения команд для каждого элемента. В некоторых случаях условные переходы можно эмулировать, для чего приходится выполнять обе ветки кода, а затем объединять результаты их работы. Это естественным образом сказывается на производительности алгоритма и если код насыщен условными переходами, то смысл в SIMD оптимизации теряется.

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

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

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

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

  10. Отладка кода, содержащего векторные инструкции значительно сложнее, так как программисту приходится отслеживать корректность не отдельных скалярных значений, а целых векторов. А современные IDE, не смотря на значительный прогресс в этой области, отображают векторные данные значительно хуже скалярных.

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


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


Послесловие


Автор данной статьи, по роду своей деятельности (разработка алгоритмов для видео аналитики) посвятил довольно большое время процессу оптимизации алгоритмов обработки изображений на C++ при помощи различных векторных инструкций (в основном это SSE2 и AVX2). В частности, результатом этой работы стала библиотека алгоритмов обработки изображений на С++ с открытым исходным кодом, которая имеется в открытом доступе. Если читатели сочтут эту тему интересной, то я готов написать несколько статей, которые будут описывать особенности оптимизации на конкретных примерах.


This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.


Комментариев нет:

Отправить комментарий