company_banner

Разработчик на распутье: как векторизовать?!


    На тему векторизации написано немало интересного. Вот скажем, отличный пост, который много полезного объясняет по работе автовекторизации, очень рекомендовал бы его к прочтению. Мне интересен другой вопрос. Сейчас в руках у разработчиков большое количество способов, чтобы создать «векторный» код – от чистого ассемблера до того же автовекторизатора. На каком же способе остановиться? Как найти баланс между необходимым и достаточным? Об этом и поговорим.

    Итак, получить «заветные» векторные инструкции можно несколькими способами. Представим схематично в виде следующей таблицы:



    Если мы опытные гуру и можем себе позволить писать на чистом ассемблере, то, пожалуй, этот путь даст нам 100% уверенности в использовании максимума в нашем коде. Ещё бы, мы сразу напишем на нужных инструкциях и используем все возможности процессора. Вот только «заточен» он будет под конкретный набор инструкций, а значит, и под конкретное «железо». Выход очередных новых инструкций (а прогресс не стоит на месте), потребует глобальной переработки и новых трудозатрат. Очевидно, стоит подумать о чём-то более легком в использовании. И на следующей «ступеньке» появляются intrinsic функции.

    Это уже не чистый ассемблер, тем не менее, времени на переписывание кода всё равно потребуется немало. Скажем, простой цикл, в котором складывают два массива, будет выглядеть так:

    #include <immintrin.h>
    
    double A[100], B[100], C[100];
    for (int i = 0; i < 100; i += 4) {
              __m256d a = _mm256_load_pd(&A[i]);
              __m256d b = _mm256_load_pd(&B[i]);
              __m256d c = _mm256_add_pd(a, b);
              _mm256_store_pd(&C[i], c);
    }
    

    В данном случае мы используем AVX intrinsic функции. Тем самым мы гарантируем генерацию соответствующих AVX инструкций, то есть опять привязаны к конкретному «железу». Трудозатраты уменьшились, но использовать этот код в будущем мы не сможем – рано или поздно его придётся снова переписывать. И так будет всегда, пока мы явно выбираем инструкции, «прописывая» их в исходном коде. Будь то чистый ассемблер, intrinsic функции или SIMD intrinsic классы. Тоже, кстати, интересная вещь, представляющая следующий уровень абстракции.

    Тот же самый пример перепишется следующим образом:

    #include <dvec.h>
    
    // 4 elements per vector * 25 = 100 elements
    F64vec4 A[25], B[25], C[25];
    
    for(int i = 0; i < 25; i++)
      C[i] = A[i] + B[i];
    

    В этом случае нам уже не нужно знать, какие функции использовать. Код сам по себе выглядит вполне элегантно, а разработчику достаточно создавать данные нужного класса. В этом примере, F64 означает тип float размера 64 бита, а vec4 говорит об использовании Intel AVX (vec2 для SSE).

    Я думаю, всем понятно, почему и этот способ нельзя назвать лучшим по соотношению «цена/качество». Правильно, портируемость всё ещё неидеальна. Поэтому разумным решением является использование компилятора для решения подобных задач. С ним, пересобирая наш код, мы сможем создавать бинарники под нужную нам архитектуру, какой бы она не была, и использовать последние наборы инструкций. При этом нам нужно убедиться, что компилятор в состоянии векторизовать код.

    Пока мы шли по табличке снизу вверх, обсуждая «сложные» пути векторизации кода. Поговорим о более простых способах.
    Очевидно, самый простой – переложить всю ответственность на компилятор и наслаждаться жизнью. Но не всё так просто. Каким бы умным не был компилятор, до сих пор существует множество случаев, когда он бессилен что-либо сделать с циклом без дополнительных данных или подсказок. Кроме того, в ряде случаев, код, удачно векторизованный с одной версией компилятора, уже не векторизуется с другой. Всё дело в хитрых компиляторных эвристиках, поэтому полагаться на автовекторизацию на 100% нельзя, хотя штука, безусловно, полезная. Например, современный компилятор может векторизовать такой код:

    double A[1000], B[1000], C[1000], D[1000], E[1000];
    for (int i = 0; i < 1000; i++)
      E[i] = (A[i] < B[i]) ? C[i] : D[i];
    

    Если бы мы пытались создать аналог кода на intrinsic функциях, гарантируя векторизацию, то получилось бы что-то подобное:
    double A[1000], B[1000], C[1000], D[1000], E[1000];
    for (int i = 0; i < 1000; i += 2) {
      __m128d a = _mm_load_pd(&A[i]);
      __m128d b = _mm_load_pd(&B[i]);
      __m128d c = _mm_load_pd(&C[i]);
      __m128d d = _mm_load_pd(&D[i]);
      __m128d e;
      __m128d mask = _mm_cmplt_pd(a, b);
      e = _mm_or_pd(
              _mm_and_pd (mask, c),
              _mm_andnot_pd(mask, d));
      _mm_store_pd(&E[i], e);
    }
    

    Хорошо, когда компилятор умеет делать это за нас! Жаль, что не всегда… и в тех случаях, когда компилятор не справляется, разработчик может помочь ему сам. Для этого можно использовать специальные «хитрости» в виде директив. Например, #pragma ivdep подскажет, что в цикле нет зависимостей, а #pragma vector always позволит не обращать внимания на «политику эффективности» векторизации (часто, если компилятор считает, что векторизовать цикл неэффективно, скажем, из-за доступа к памяти, он этого не делает). Но эти директивы из разряда «возможно помогут». Если компилятор уверен, что зависимости есть, то цикл он так и не будет векторизовывать, даже если имеется pragma ivdep.

    Поэтому я выделил ещё один способ, который основан на директивах, но несколько других принципах работы. Это директивы из нового стандарта OpenMP 4.0 и Inte Cilk Plus #pragma omp simd и #pragma simd соответственно. Они позволяют совсем «забывать» компилятору о собственных проверках, и целиком полагаться на то, что говорит разработчик. Ответственность, в этом случае, естественно, перекладывается на его плечи и голову, так что действовать нужно аккуратно. Отсюда и появляется потребность в ещё одном способе.

    Как бы сделать так, чтобы проверки всё же оставались, но и код гарантированно был векторизован? К сожалению, с существующим в С/С++ синтаксисе, пока никак. А вот с использованием возможностей специального синтаксиса для работы с массивами (array notation), являющегося часть Cilk Plus’a (см. предыдущий пост для того чтобы понять, как много там всего есть), это возможно. Причём синтаксис весьма простой, чем то напоминает Фортран, и имеет следующий вид:

    base[first:length:stride]
    

    Задаём имя, начальный индекс, число элементов, шаг(опционален) и вперёд. Предыдущий пример перепишется с ним так:

    double A[1000], B[1000], C[1000], D[1000], E[1000];
    E[:] = (A[:] < B[:]) ? C[:] : D[:];
    

    Двоеточие означает, что мы обращаемся ко всем элементам. Можно так же осуществлять более сложные манипуляции. Скажем этот код

    for (i = 0; i < 5; i++)
      A[(i*2) + 1] = B[(i*1) + 1];
    

    перепишется более компактно, и главное, гарантирует векторизацию:

    int A[10], *B;
    A[1:5:2] = B[1:5];
    

    Таким образом, мы видим, что способов добиться векторизации действительно много. Если говорить о балансе, то раз уж мы перечислили все способы в табличке «от простого к сложному», то с точки зрения требуемых затрат и результата на выходе, золотая середина сходится на Cilk Plus’е. Но это не значит, что всё так очевидно. Если пациент болен, ему же не всегда сразу выписывают антибиотики, верно? Так же и здесь. Для кого-то может оказаться достаточно автовектризации, для кого-то директивы ivdep и vector always будут вполне разумным решением. Важнее вовлекать компилятор, чтобы не болела голова при выходе новых инструкций и «железа», а здесь у Intel всегда есть что предложить. Так что до новых постов, друзья!
    Intel
    176,95
    Компания
    Поделиться публикацией

    Комментарии 19

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

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

      Такое делают и на чистом ассемблере давно, но это может быстро превратиться в макросовый ад.
        +1
        Вы не правы — увеличение размера регистра далеко не единственный плюс новых наборов. Там появляются именно новые инструкции, упрощающие векторизацию. Например, загрузка в регистр непоследовательных данных и сохранение по маске.
        Кроме того, темплейт будет работать медленнее интринсика по любому, а для некоторых приложений это критично
          0
          Я не зря сказал «для довольно простых алгоритмов». Вы не поверите, но довольно большому количеству рутин достаточно SSE2 набора инструкций. Да, конечно, полезные инструкции есть везде, но не всегда они нужны.

          А насчет того, что темплейт медленней интринсика, вы не правы. Рантайм цена темплейтов в принципе нулевая, если они инлайнятся. А если не инлайнятся, то всегда есть __forceinline.
          0
          По поводу роста раз в 8 лет — это долго на SSE «топтались», уже значительно быстрее. Скажем, посмотрите на рост с 256 до 512. И, как уже было сказано, это не единственный плюс. Для каких то простых алгоритмов — возможно. Но речь то в целом не об этом. Давайте вы будете писать код на темплейтах с интринсиками, а я векторизую цикл через прагму, и сравним время, которое мы затратим на это. Кроме того, ещё и уровень опыта, предъявляемый к разработчику. Ну и будущие изменения в коде, которые так или иначе, затронут вас.
            0
            Да никто не спорит, что C код писать, чаще всего, быстрее и проще. И он может быть даже векторизуется при нужном положении луны нужным компилятором. Не оптимально, но векторизируется.

            Просто мы пока ну очень далеко от состояния, когда можно будет отдать всё компилятору. Вы когда-нибудь видели автовекторизатор, использующий pmaddwd? А сложные шаффлы с pshufb? А punpck**? Может, это обработка видео такая странная, но у меня от автовекторизаторов сплошное разочарование.

            Но речь не об этом. Я просто хотел сказать, что интринсики, да и чистый асм — не абсолютное зло, и не надо их бояться. Если есть желание писать на них универскальный код — это можно сделать. Да, он будет менее читаем, он будет требовать от вас больше знаний, его будет сложнее «поддерживать». Зато без привязки к компилятору (ну разве что иногда производительно интринсиков в vc хромает), без дополнительных зависимостей, без платных тулзов.

            Ну и насчет переписывания кода под новые инструкции — мне кажется, вы преувеличиваете. Даже сейчас многие пишут чистый SSE2-4, ибо огромная база пользователей нормальную реализацию AVX(2) не увидит еще несколько лет (с быстрыми vgather, например). Если уж критично использовать всегда последний сэт инструкций — почему бы не OpenCL? Там и перекомпилировать не придется, всё в рантайме.
            0
            Кстати, изменения эти будут затрагивать вас всё чаще и чаще, потому фокус и смещается от интринсиков к компилятору. Хотя до сих пор, чтобы получить максимальную производительность, лучше использовать интринсики, весь вопрос в целесообразности.
              –2
              А целесообразность использования расширений поддерживаемых ажно одним компилятором ажно для одной платформы типа никого не смущает.

              Ню-ню. Нет, я не спорю, где-то кому-то как-то Inte® Cilk™ Plus может и пригодится, но я бы его всё-таки отнёс в красную зону, а не в синюю. Ибо все эти прагмы влияют только на скорость (даже если векторизовать вообще ничего не удалось, то хоть как-то код работать будет), а вот начиная с Inte® Cilk™ Plus у вас появляется ситуация, когда программа есть, а запустить вы её не можете вообще.

              Вот когда поддержка появится в GCC/Clang'е — уже будет о чём поговорить (например обсудить работоспособность этих чудес на самых быстрых в мире процессорах POWER), а пока — рано.

              P.S. Я знаю что Intel работает и с разработчиками GCC и Clang'а. Уж три года как работает. В релизах пока ничего нету. Я верю, что рано или поздно оно случится, но когда это будет? А когда вам проект сдавать? В 2020м или чуть пораньше? Вот отсюда и исходите…
                +2
                Для ясности — директива pragma simd, с июля этого года часть стандарта OpenMP 4.0 (pragma omp simd), а значит никакой привязки к компилятору. Синтаксис для работы с массивами — так же часть этого стандарта (Array Sections).
                Собственно, как мы видим, всё это весьма быстро переходит из частного для компилятора Intel в общее для всех, ввиду распространенности OpenMP и явного стремления того же gcc его поддерживать.

                «начиная с Inte® Cilk™ Plus у вас появляется ситуация, когда программа есть, а запустить вы её не можете вообще.»
                Это весьма странное утверждение, потому что мы всегда можем сгенерировать дефолтную ветку с поддерживаемыми инструкциями на всех и не «интеловских» процессорах. Хотелось бы понять, что вкладывается в «вообще»?
            0
            Ассемблер, на мой взгляд — самый красивый и чистый способ векторизации.

            Знаю, нехорошо в блоге Intel оставлять комментарии об ARMе, но я всё же приведу пример.
            inline void TransposeSIMD(float32x4_t &x, float32x4_t &y, float32x4_t &z, float32x4_t &w)
            {
            	__asm__ __volatile__ (
            		"vzip.f32 %q0, %q1\n"
            		"vzip.f32 %q2, %q3\n"
            		"vswp %f0, %e2\n"
            		"vswp %f1, %e3\n"
            		"vswp %q1, %q2\n"
            		: "+w" (x), "+w" (y), "+w" (z), "+w" (w)
            	);
            }
            

            Боюсь себе представить, как бы это выгядело с кастами к float32x2_t и без vswp.
              +4
              > самый красивый и чистый способ
              У каждого понятия «красоты» и «чистоты» свои. Понятия «простота разработки/поддержки» и «скорость работы» более объективны.

              Сразу всплывающие проблемы для Вашего примера кода.
              1. Он теперь только для ARM. Если бы этот пример был для IA-32 — та же проблема: код оказывается только для одной архитектуры. У меня были проблемы при попытке переноса огромной массы кода, написанной на асме (ядро двоичного транслятора) даже для случая IA-32 -> Intel 64. Вроде бы одно является развитием другого, а вот фиг асм переиспользуешь.

              2. Поправьте меня, если мои знания устарели, но у ARM всего один вид SIMD — это 128-битный NEON. У Интеловской же архитектуры за всё время накопилось векторных расширений: 64-битный MMX, 128-битный SSE/SSE2/SSE3/SSE4.1/SSE4.2, 128-битный AVX, 256-битный AVX2. А на MIC'ах уже есть 512-битный AVX3.x. И для какой же ширины регистров и набора инструкций писать асм в таком случае, если у пользователя может оказаться совершенно разное железо (разве что MMX можно уже забыть как страшный сон)? Придётся писать 3-4 варианта всех процедур на асме. Я бы предпочёл, чтобы это за меня сделал компилятор.

                0
                А как вы собираетесь через интринсики писать процессоронезависимый код?

                А насчёт скорости (которая для меня — главное, и зачастую она следует как раз из простоты и чистоты) — обёртки над интринсиками тоже не сильно процессоронезависимые, для максимальной производительности всё равно придётся оптимизировать под конкретный процессор.
                  +2
                  Я не предлагал писать что-то через интринсики. Интринсики — это тот же самый асм, только завёрнутый более аккуратно в синтаксис использующего его языка высокого уровня. Вместо ассемблер-специфичных clobber-list, двойных процентов у имён регистров и прочее код оформляется как вызов inline-функций. Сахар, не более.
                    +1
                    Так про то и разговор. А компилятор даёт более универсальное решение, и мы стараемся как можно сильнее минимизировать разницу между написанием кода на чистых интринсиках и тем, что выдаёт компилятор. Вот только речь не об автовекторизации, а о векторизации, контролируемой разработчиком. Кроме того, ещё и о специальном синтаксисе, при использовании которого вы гарантированно получите векторный код. Раньше таких гарантий компилятор не давал. Вот и вопрос встаёт, насколько вам критично получать дополнительный прирост производительности от более тонкого написания кода на интринсиках, и последующего его переписывания при выходе новых наборов инструкций, или же написать код, который точно будет векторизован сейчас и на всех последующих архитектурах. Скажу сразу, что есть организации, и их не так уж и мало, которые выбрали и выберут интринсики. Но для большинства это будет лишними «расходами».
                  0
                  А зачем касты, если есть vzipq_f32 и vswp тоже можно подумать, чем заменить
                  0
                  Последние векторные инструкции в процессорах Intel мне всё больше напоминают некоторые функции стандарта MPI (message passing interface). Тут тебе и gather/scatter, и stride-access. Интересно, скоро ли напишут вариант реализации MPI для систем с общей памятью прямо на интринсиках :-)

                    0
                    [deleted]
                    0
                    Интересно есть ли решение которое бы давало векторный код между разными CPU архитектурами, как пары ARM/x86 актуальной для Андроид. Для одной архитектуры оптимально наверное использовать intrinsic. Если мы идем наверх в сторону «легкии» то встречаем Intel Cilk Plus, который мог бы быть оптимальным решением, однако скорей всего будет работать под одну архитектуру.
                      +1
                      Чуть выше в треде привели пример решения — pragma simd, описываемая стандартом. Дело теперь за компиляторами — надо её поддержать для всех архитектур, тогда и векторный код будет генерироваться.
                      +1
                      Спасибо за обзор.
                      На практике встречал сообщения компилятора о векторизации цикла и пробовал использовать интринсики (на предмете текущего семестра). Нужно будет посмотреть Inte® Cilk™ Plus — планируется его включение в GCC 4.9.

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

                      Самое читаемое