Низкоуровневая оптимизация кода на платформе Эльбрус: векторное сложение uint16_t с помощью интринсиков



    В этой статье мы расскажем про более низкоуровневые оптимизации, которые можно делать на процессорах Эльбрус.

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

    Однако в текущей версии EML мы не нашли некоторых интересных нам функций, поэтому приняли решение написать их сами.

    Для этого мы использовали интринсики. Интринсики – конструкции, выглядящие для программиста как обычные функции, но их вызовы заменяются компилятором “по месту” на высокоэффективный код. Чаще всего интринсики нужны, когда хочется использовать векторные расширения процессора, позволяющие выполнять одну и ту же операцию над регистром, содержащим сразу несколько элементов данных. Даже оптимизирующий компилятор не всегда может угадать, что такая конструкция ускорит ваш код. В таких случаях раньше, если не было подходящей оптимизированной библиотеки, приходилось использовать ассемблер. Но быстродействие ассемблерного кода существенно зависит от эффективности использования регистров, учета задержек АЛУ и прочих чудесных вещей. А Эльбрус еще и имеет VLIW-архитектуру, а значит, если мы хотим писать на ассемблере, нам предстоит самостоятельно следить за формированием широких командных слов. С другой стороны, для подобных тонкостей и создаются оптимизирующие компиляторы. Переход на интринсики позволяет разумно распределить работу между человеком и программой. Код, использующий интринсики, можно без проблем переносить между системами, поддерживающими все задействованные интринсики. То есть в нашей ситуации интринсики очевидно являются оптимальным решением.


    Микропроцессоры Эльбрус-4С и Эльбрус-8С поддерживают векторные операции с регистром размера 64 бита. С помощью такого регистра можно одновременно обработать два 32-битных числа, четыре 16-битных целых числа или восемь 8-битных целых чисел. Набор интринсиков микропроцессора Эльбрус включает в себя операции для преобразования данных, инициализации элементов вектора, арифметических операций, побитовых логических операций, перестановки элементов вектора и, как нам показалось, достаточно похож на набор инструкций SSE/SSE2 процессоров x86.


    Итак, приступим к оптимизации. Возьмем кусочек кода для сложения двух массивов типа uint16_t с записью результата в третий массив (такой операции в EML пока нет):


    // Вариант 0
    // eml_16u *src1 - указатель на первый аргумент суммы массивов
    // eml_16u *src2 - указатель на второй аргумент суммы массивов
    // eml_16u *dst - указатель на результирующий массив
    // len - длина массивов
    for (size_t i = 0; i < len; ++i)
      dst[i] = src1[i] + src2[i];

    Теперь перепишем его с использованием интринсиков. Для простоты будем считать, что длина массивов len делится на 4, а остающиеся элементы массивов обрабатываются отдельно. Тогда получится примерно так:


    // Вариант 1
    // eml_16u *src1 - указатель на первый аргумент суммы массивов
    // eml_16u *src2 - указатель на второй аргумент суммы массивов
    // eml_16u *dst - указатель на результирующий массив
    // len - длина массивов
    static const size_t block_size = sizeof(eml_64u) / sizeof(eml_16u);
    for (size_t i = 0; i < len; i += block_size, src1 += block_size, src2 += 
        block_size, dst += block_size)
      *(__di*)dst = __builtin_e2k_paddh(*(__di*)src1, *(__di*)src2);

    Здесь __di – 64-битный тип данных, а __builtin_e2k_paddh – интринсик, осуществляющий 16-битное беззнаковое сложение.


    Однако этот код неоптимален, поскольку для загрузки невыровненного 64-битного числа r по адресу p процессору необходимо осуществить следующие элементарные операции:


    1. Определить смещение s адреса p от границы выравнивания на 64-бита (см. Рис. 1). Адрес выровненного 64-битного числа, содержащего начало r будет равен p - s. Адрес следующего за ним выровненного 64-битного числа, содержащего конец r, будет равен p - s + 8.


    2. Загрузить из памяти 2 64-битных числа r1, r2, содержащих r, по выровненным адресам.


    3. Найти число r, зная r1, r2, s.


    Рис. 1. Схема невыровненной загрузки 64-битных данных из памяти.


    Для дальнейшей оптимизации запишем это в явном виде, используя макросы Эльбруса:


    __di s = E2K_BYTES_FROM_ALIGN(p, 8);
    __di tmp;
    E2K_PREPARE_ALIGN(s, tmp);
    const __di *p_aligned = (__di *)E2K_ALIGN_PTR_BACK(p, 8);
    __di r1 = *p_aligned;
    __di r2 = *(p_aligned + 1);
    __di r;
    E2K_ALIGN_DATA(r1, r2, r, tmp);

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


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


    // Вариант 2
    // eml_16u *src1 - указатель на первый аргумент суммы массивов
    // eml_16u *src2 - указатель на второй аргумент суммы массивов
    // eml_16u *dst - указатель на результирующий массив
    // len - длина массивов
    size_t i = 0;
    // Найдем количество элементов до границы выравнивания на 64-бита для dst и обработаем их
    size_t offset = E2K_BYTES_TO_ALIGN(dst, sizeof(eml_64u)) / sizeof(eml_16u);
    for (; i < offset; ++i)
      dst[i] = src1[i] + src2[i];
    // Обработаем основную часть массива
    __di spec0, spec1;
    __di tmp0, tmp1;
    __di align1 = E2K_BYTES_FROM_ALIGN(src1 + offset, sizeof(eml_64u));
    E2K_PREPARE_ALIGN(align1, spec0);
    __di align2 = E2K_BYTES_FROM_ALIGN(src2 + offset, sizeof(eml_64u));
    E2K_PREPARE_ALIGN(align2, spec1);
    const __di *v1 = (__di *)E2K_ALIGN_PTR_BACK(src1 + offset, 8);
    const __di *v2 = (__di *)E2K_ALIGN_PTR_BACK(src2 + offset, 8);
    __di *v3 = (__di*)(dst + offset);
    __di d01, d11;
    __di d00 = *v1;
    __di d10 = *v2;
    ++v1;
    ++v2;
    static const size_t block_size = sizeof(eml_64u) / sizeof(eml_16u);
    size_t effective_len = offset + ((len - offset) & ~(block_size - 1));
    for (; i < effective_len; i += block_size, ++v1, ++v2, ++v3) {
      d01 = *v1;
      d11 = *v2;
      E2K_ALIGN_DATA(d00, d01, tmp0, spec0);
      E2K_ALIGN_DATA(d10, d11, tmp1, spec1);
      *v3 = __builtin_e2k_paddh(tmp0, tmp1);
      d00 = d01;
      d10 = d11;
    }
    // Обработаем оставшиеся элементы последовательно, если они есть

    Казалось бы, что можно ещё сделать?


    Однако, как мы помним, на современных Эльбрусах имеется 6 каналов исполнения, в которые можно поместить до 24 инструкций, и они будут исполняться за 1 такт. Из этих инструкций только 6 могут быть арифметическими для целых чисел, т. к. на каждый канал есть только одно векторное АЛУ (другие инструкции могли бы относиться к вещественной арифметике, загрузке/записи и пр.) Кроме того, есть ещё одна тонкость: эти 6 АЛУ разные, и каждая арифметическая команда может быть исполнена только в определенных каналах. Для ненасыщающего сложения подходят только каналы 0 и 3. Поэтому за 1 такт мы можем выполнить не больше 2 сложений. Чтобы подсказать осторожному компилятору, что эти два сложения независимы (т. е. результат первого не используется во втором), развернем цикл. Это можно сделать вручную или с помощью директивы компилятора:


    #pragma unroll(2)


    Кроме того, можно подсказать компилятору количество ожидаемых итераций цикла, например, для цикла по строке изображения подойдёт число около 1024 (это вполне разумная оценка линейных размеров распознаваемых изображений, да и коллеги из МЦСТ рекомендовали такой размер; общая идея в том, что число должно быть достаточно большим, чтобы компилятор счёл уместным использовать специальные цикловые оптимизации):


    #pragma loop count(1024)


    Разумеется, в заведомо коротких циклах компилятору следует оставить противоположную подсказку (см. ниже).


    // Вариант 3
    // eml_16u *src1 - указатель на первый аргумент суммы массивов
    // eml_16u *src2 - указатель на второй аргумент суммы массивов
    // eml_16u *dst - указатель на результирующий массив
    // len - длина массивов
    size_t i = 0;
    // Найдем количество элементов до границы выравнивания
    на 64-бита для dst и обработаем их
    size_t offset = E2K_BYTES_TO_ALIGN(dst, sizeof(eml_64u)) / sizeof(eml_16u);
    #pragma loop count(3)
    for (; i < offset; ++i) {
      dst[i] = src1[i] + src2[i];
    }
    // Обработаем основную часть массива
    __di spec1, spec2;
    __di tmp0, tmp1;
    __di align1 = E2K_BYTES_FROM_ALIGN(src1 + offset, sizeof(eml_64u));
    E2K_PREPARE_ALIGN(align1, spec1);
    __di align2 = E2K_BYTES_FROM_ALIGN(src2 + offset, sizeof(eml_64u));
    E2K_PREPARE_ALIGN(align2, spec2);
    const __di *v1 = (__di *)E2K_ALIGN_PTR_BACK(src1 + offset, sizeof(eml_64u));
    const __di *v2 = (__di *)E2K_ALIGN_PTR_BACK(src2 + offset, sizeof(eml_64u));
    __di *v3 = (__di*)(dst + offset);
    __di d01, d11, d02, d12;
    __di d00 = *v1;
    __di d10 = *v2;
    ++v1;
    ++v2;
    size_t effective_len = offset + ((len - offset) & ~0x03);
    #pragma unroll(2)
    #pragma loop count(1024)
    for (; i < effective_len; i += 4, ++v1, ++v2, ++v3) {
      d01 = *v1;
      d11 = *v2;
      E2K_ALIGN_DATA(d00, d01, tmp0, spec0);
      E2K_ALIGN_DATA(d10, d11, tmp1, spec1);
      *v3 = __builtin_e2k_paddh(tmp0, tmp1);
      d00 = d01;
      d10 = d11;
    }
    // Обработаем оставшиеся элементы последовательно, если они есть

    Теперь приведем результаты замеров. Для этого мы измеряли время сложения двух массивов длины 105. Среднее время по 105 итерациям приведено в таблице.


    Вариант Среднее время сложения массивов, мкс
    0 219,0
    1 250,7
    2 62,6
    3 31,4

    Наша оптимизация позволила в 7 раз ускорить сложение! Мы видим, что, задавшись целью выжать максимум производительности и потратив немного времени на изучение особенностей Эльбруса, можно добиться значительных результатов.


    Большое спасибо сотрудникам МЦСТ, которые неоднократно консультировали нас при написании этого материала!

    Smart Engines
    89,00
    Обработка изображений, распознавание в видеопотоке
    Поделиться публикацией

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

      +1
      В первом цикле инкремент или по индексу, или по указателям, но не и то и другое.
        0
        Спасибо, исправили. По ошибке скопипастили при выкладывании.
        –2
        Вы серьезно?
        "… Для простоты будем считать, что длина массивов len делится на 4.." и "… невыровненного 64-битного числа r по адресу p процессору необходимо..."
          +3
          По первому замечанию: Вам действительно интересен код, замусоренный обработкой «хвостика» массива? На производительность это не влияет. Код — элементарный. А тема поста — производительность. Маловероятно, что среди читателей есть разработчики на Эльбрусе, мечтающие именно о 16-битном сложении и надеющиеся на готовую копипасту. Поэтому мы выкинули то, что ухудшило бы подачу материала. Напротив, невыровненность начала массива — это ключевая проблема. Отдельной обработкой «начала» она не лечится. Что же касается второго замечания, то, простите, не ясно, что именно вызывает раздражение. Не уточните?
          0
          Было бы гораздо интересней увидеть прирост производительности на более реальной задаче. А то бывает оптимизируешь, оптимизируешь, а узкое место в другом месте
            0
            В задаче распознавания паспорта РФ использование EML и интринсиков (для реализации функций, которых пока нет в EML) ускоряет вычисления где-то в 2 раза на Эльбрус-401PC. Сейчас научная статья, включающая эти результаты, находится в печати.
            0

            А чем кроме непроизносимого названия отличаются интринсики от обычных инлайн-функций?

              0

              Интринсики — это компиляторная магия. Зачастую вызов функции-интринсика может быть преобразован в единственную инструкцию. Иногда без интринсиков невозможно достичь желаемого (если не юзать хардкорный асм): https://gcc.gnu.org/onlinedocs/gcc/x86-transactional-memory-intrinsics.html#x86-transactional-memory-intrinsics

                0
                Получается, что интринсики — это когда кто-то за вас сделал хардкорный асм в виде инлайн-функций и собрал их в библиотеку?
                  0
                  Интринсики, скорее, продолжение языка компилятора. Он обрабатывает их по особому, не как обычную библиотеку.
                  0
                  Определение я прочитал перед тем как писать комментарий, но всё равно не понял отличия от инлайн-функций.

                  Compilers that implement intrinsic functions generally enable them only when a program requests optimization, otherwise falling back to a default implementation provided by the language runtime system (environment).

                  Если не включить оптимизацию при компилляции, то будет обычный вызов функции; если оптимизацию включить, то будет инлайн-функция?
                    0
                    Интринсики предоставляют доступ к инструкциям процессора, которые недоступны в С.
                      0
                      Асм-вставки нельзя делать, что ли? Которые можно обернуть в инлайн-функции.
                        +1
                        Интринсики позволяют не думать о соглашениях о вызове и т.п., компилятор сам делает выделение регистров.
                          0
                          Асм вставки мешают оптимизатору и вообще являются жутким костылём.
                          Поэтому некоторые компиляторы их не поддерживают.
                  0
                  А почему сразу не писать на асме?

                  Почему не пропатчить компилятор с++, под вашу платформу? Чтобы он сам занимался оптимизациями.
                    0
                    На каком асме то — nasm fasm yasm wasm?
                      0
                      На Эльбрусе las и gas =)
                    +1
                    Скомпилировал все примеры под Эльбрусом. (переделав на си)
                    Несколько замечаний.
                    1) результаты, похожие на ваш, (но не в 7 раз), получаются при опциях
                    -fforce-vect -fvect-verbose
                    2) неоднократно замечал, что unroll у МЦСТ коряво работает даже в простых случаях…
                    3)Запустил с оптимизацией O3 (да да, у МЦСТ очень даже рабочая), и все ваши оптимизации коту под хвост.
                    t0-t1 45.814001 (первый случай, мкс.) время на обработку 256 массивов по 256.
                    t0-t1 369.018002(второй случай)
                    t0-t1 382.902000l(3-й случай.)
                    4) вместо радости рекомендую еще prefetch сделать.

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

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