Стоит ли оптимизировать обработку изображений на С++ при помощи 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). В частности, результатом этой работы стала библиотека алгоритмов обработки изображений на С++ с открытым исходным кодом, которая имеется в открытом доступе. Если читатели сочтут эту тему интересной, то я готов написать несколько статей, которые будут описывать особенности оптимизации на конкретных примерах.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 33

      +14
      По моему автор описал совсем уж очевидные преимущества и недостатки. Для людей, которые над этой темой не задумывались (имеют малое отношение к программированию, или совсем не имеют), статья «пойдет» как вводная, а для людей, хоть немного знакомых с темой будет «речью Капитана Очевидность».
        +2
        Наверное в некотором роде действительно, так оно и есть — я действительно написал очевидные для специалиста вещи. Но я себя сознательно ограничивал, так как хотел описать проблему в общих чертах, что бы она была понятна не специалистам. Возможно, что я был не прав.
          +1
          Я сразу понял, что статья написана для людей незнакомых с данной темой, и описана, по моему мнению, хорошо. Я работал с 3DNow, MMX, SSE, AVX, поэтому могу сказать, как человек знакомы с темой, что статья хорошо написана для людей абсолютно незнакомых с темой. По крайней мере, им станет понятно, чем отличаются те же SSE сборки от generic.
          P.S. Правда я работал с упакованным и числами с плавающей точкой, но имею представление о работе с упакованными целочисленными числами. А так-же немного «ковырял» NEON для ARM.
            0
            Я больше по целым числам специализируюсь. Но MMX я уже не застал. Лет пять колупал SSE2, последний год — AVX2. Возможно, что скоро руки дойдут до NEON.
              0
              Ну MMX я тоже не застал (а если и застал, то слишком «мелким» был), скорее ради академического интереса на нем написал пару программ.
      • UFO just landed and posted this here
          +1
          Указанное требование заставляет пересматривать способы хранения данных, например, хранить цветное изображение в виде набора отдельных цветовых плоскостей, а не в единой плоскости с чередованием цветовых каналов для каждой точки (как в BGR-24).

          Проблема BGR24 не в том, что он BGR, а в том, что он 24. Это заставляет писать сумасшедшие костыли, которые чаще всего сводятся к конвертации этого дела в BGR32 и обратно. И хорошо, если у вас доступнен pshufb из SSSE3, а если нет?..

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

          Да, было бы интересно почитать.
            +1
            У каждого, кто пытался работать с BGR-24 на SSE2, наверное получились свои собственные уникальные костыли :)
              0
              И хорошо, если у вас доступнен pshufb из SSSE3, а если нет?

              Тогда так
                0
                Не всегда выход, поскольку требует содержать отдельную рутину для обработки планарного RGB, в то время как pshufb позволяет использовать одну и ту же рутину для RGB32 и RGB24 с разницей лишь в пару инструкций.
                Кроме того, а как паковать обратно-то будем? :)
                  0
                  Если вы внимательно присмотритесь, то заметите, что эти преобразования работают в обе стороны.
              +1
              Можно обрабатывать изображения используя IPP. Такой себе компромисс. Не так быстро как если бы при указанном подходе, но значительно быстрее, по сравнению с невекторизированным кодом. IPP может автоматически определять процессор, на котором исполняется.
                +1
                Я думаю, что реализация на IPP будет даже быстрее, если конечно найдется именно та функция, что вам нужна. К сожалению за IPP нужно денежку платить.
                  0
                  Под Linux не в коммерческих целях вполне бесплатно. Но это очень частный случай. Хотя если больно уж захочется попробовать…
                +2
                Мне кажется, стоило бы упомянуть автовекторизацию кода, для каких компиляторов она доступна, какие лучшие практики применения, и т.п. Возможно, от большинства минусов в некоторых случаях можно было бы избавиться, ограничившись переупорядочиванием данных в памяти и добавлением флагов компиляции.
                Также интересно применение NEON для ARM, в частности, при использовании LLVM-компилятора.
                  +2
                  Я SIMD код люблю и уважаю в 2х случаях.
                  1. если он уже написан в составе какой-то библиотеки, вроде Accelerate.framework (vecLib + vImage)
                  2. если он был сгенерирован компилятором с включенной опцией vectorize loops. :)
                  Писать его самому — себе дороже, т.к. со всех сторон разложены грабли и легко можно сделать алгоритму только хуже.
                    +2
                    Может сразу OpenCL использовать?
                      +1
                      Тогда уж OpenVX, когда его до ума доведут.
                      –1
                      В то время, когда все умные люди переходят на работу с числами с плавающей точкой для задач обработки изображений, вы продолжаете бороздить просторы большого театра.
                        0
                        Вот-вот

                        В 8 бит гамма корректированых хрен чего обработаешь, кроме самого примитивного

                          0
                          Дык распаковывайте в 16, а то и в 32.
                          Есть сумасшедшее количество алгоритмов, которым float в принципе не сдался, и которые гораздо быстрее провести в целочисленных вычислениях. Даже если в теории точность может пострадать, очень часто никого не волнуют +-0.5 отклонения.
                            –1
                            8 bit? Это по 2 бита на канал? Ыы, разве такое на прктике встречается?
                          0
                          Вообще идеальная ситуация это когда компилятор сам векторизует то, что можно векторизовать. Писать SSE руками нудно и, к тому же, выигрыш не гарантирован.
                            0
                            без доработки языка ничего хорошего не получится
                            ispc.github.io/
                              0
                              А вот это уже интересно. Но еще нужно уметь векторизовывать на всех уровнях одновременно. Например, у меня 24 карточки Xeon Phi на 12 компах, мне хочется чтобы модель параллелизации была однородной.
                                0
                                Тут слишком много посторонних факторов — зависимость от ОС / характеристики линков между компами.
                                  +2
                                  Не совсем. Тот же Intel поставляет в наборе MKL реализацию FFT, которая использует MPI. Вполне себе портабельно. Тут то же самое можно было бы сделать. Имхо между компьютерами общаться — так MPI это стандарт. А вот между девайсами — тут уж тривиально обернуть WinAPI/pthreads реализации в общий интерфейс, особенно если учесть что нужно всего лишь запустить поток. И тот же OpenMP, кстати, очень даже портабелен между операционками.
                                  +1
                                  Странно, но на Хабре ничего не нашёл про практическое использование Xeon Phi. Было бы интересно почитать, как оно устроено и работает.
                                    0
                                    Ну это не удивительно. Технология во-первых достаточно свежая, а во-вторых очень дорогая для обычного потербителя — намного дороже чем CUDA, хоть и дешевле чем, например, использование FPGA.
                                –1
                                Ту векторизацию, о которой пишет автор, ни один компилятор никогда сам не сделает.
                                  +2
                                  Мне кажется до этого-то техника должна дорости. Особенно если учесть что нам уже говорят про векторизацию в компиляторе. На простых кейсах точно, например если нам надо сделать c = a + b где все переменные uint8_t* и обрабатываются в цикле, что мешает поделить конечное значение цикла, скажем, на 4 и поменять указатели на __m128i* или что-то в этом духе? А это как раз юз-кейс как у автора: обработка 32-битных картинок.
                                +1
                                Да, было бы интересно почитать. Только не затягивайте пожалуйста, очень актуальная для многих тема.
                                  –2
                                  Картинка заинтересовала. Только посмотрел я на неё несколько более приземлённо.
                                  1. Чистая и очень дешёвая обработка пашни. Затрат на производство нет. Конь, пашет, тут же удобряет. Здесь же ест траву, нет затрат на пищу. Дёшево и чисто. Минус только в том, что надо трудиться, так что это плюс. Минус только для лентяев. И очень простое воспроизводство. Не нужно готовить супер-специалистов. Просто старики передают навык молодым. Нужен только конь и человек.
                                  2. Грязная и дорогая обработка пашни. Разработка месторождений руды, добыча, литьё металла. На всё это нужно шахты, производство, оборудование. Огромные людские трудозатраты и огромное количество отходов, загрязнение и загаживание природы. При этом ещё нужно вспомнить о заводах, которые собственно делают станки, которые потом будут делать трактора. И всё это нужно по чему-то доставлять, а значит целая индустрия по строительству дорог. И это только одна стронона. А далее идёт топливо: добыча, производство, перевозка, отходы, выхлопы и т.д.
                                  Забавно, что работая в IT мы как-то перестали задумываться о реальном мире.

                                  Only users with full accounts can post comments. Log in, please.