Что вы делаете без быстрого сбора и разброса в инструкциях AVX2?

Question

Я пишу программу для определения чисел простых чисел. Одна часть - это отсеивание возможных кандидатов. Я написал довольно быструю программу, но подумал, посмотрю, есть ли у кого-нибудь лучшие идеи Моя программа могла бы использовать некоторые инструкции по быстрому сбору и рассеянию, но я ограничен аппаратным обеспечением AVX2 для архитектуры x86 (я знаю, что у AVX-512 они есть, хотя я не уверен, насколько они быстры).

#include <stdint.h>
#include <immintrin.h>

#define USE_AVX2

// Sieve the bits in array sieveX for later use
void sieveFactors(uint64_t *sieveX)
{
    const uint64_t totalX = 5000000;
#ifdef USE_AVX2
    uint64_t indx[4], bits[4];

    const __m256i sieveX2 = _mm256_set1_epi64x((uint64_t)(sieveX));
    const __m256i total = _mm256_set1_epi64x(totalX - 1);
    const __m256i mask = _mm256_set1_epi64x(0x3f);

    // Just filling with some typical values (not really constant)
    __m256i ans = _mm256_set_epi64x(58, 52, 154, 1);
    __m256i ans2 = _mm256_set_epi64x(142, 70, 136, 100);

    __m256i sum = _mm256_set_epi64x(201, 213, 219, 237);    // 3x primes
    __m256i sum2 = _mm256_set_epi64x(201, 213, 219, 237);   // This aren't always the same

    // Actually algorithm can changes these
    __m256i mod1 = _mm256_set1_epi64x(1);
    __m256i mod3 = _mm256_set1_epi64x(1);

    __m256i mod2, mod4, sum3;

    // Sieve until all factors (start under 32-bit threshold) exceed the limit
    do {
        // Sieve until one of the factors exceeds the limit
        do {
            // Compiler does a nice job converting these into extracts
            *(__m256i *)(&indx[0]) = _mm256_add_epi64(_mm256_srli_epi64(_mm256_andnot_si256(mask, ans), 3), sieveX2);
            *(__m256i *)(&bits[0]) = _mm256_sllv_epi64(mod1, _mm256_and_si256(mask, ans));

            ans = _mm256_add_epi64(ans, sum);

            // Early on these locations can overlap
            *(uint64_t *)(indx[0]) |= bits[0];
            *(uint64_t *)(indx[1]) |= bits[1];
            *(uint64_t *)(indx[2]) |= bits[2];
            *(uint64_t *)(indx[3]) |= bits[3];

            mod2 = _mm256_sub_epi64(total, ans);

            *(__m256i *)(&indx[0]) = _mm256_add_epi64(_mm256_srli_epi64(_mm256_andnot_si256(mask, ans2), 3), sieveX2);
            *(__m256i *)(&bits[0]) = _mm256_sllv_epi64(mod3, _mm256_and_si256(mask, ans2));

            ans2 = _mm256_add_epi64(ans2, sum2);

            // Two types of candidates are being performed at once
            *(uint64_t *)(indx[0]) |= bits[0];
            *(uint64_t *)(indx[1]) |= bits[1];
            *(uint64_t *)(indx[2]) |= bits[2];
            *(uint64_t *)(indx[3]) |= bits[3];

            mod4 = _mm256_sub_epi64(total, ans2);
        } while (!_mm256_movemask_pd(_mm256_castsi256_pd(_mm256_or_si256(mod2, mod4))));

        // Remove one factor
        mod2 = _mm256_castpd_si256(_mm256_blendv_pd(_mm256_setzero_pd(), _mm256_castsi256_pd(sum), _mm256_castsi256_pd(mod2)));
        mod4 = _mm256_castpd_si256(_mm256_blendv_pd(_mm256_setzero_pd(), _mm256_castsi256_pd(sum2), _mm256_castsi256_pd(mod4)));
        ans = _mm256_sub_epi64(ans, mod2);
        ans2 = _mm256_sub_epi64(ans2, mod4);
        sum = _mm256_sub_epi64(sum, mod2);
        sum2 = _mm256_sub_epi64(sum2, mod4);
        sum3 = _mm256_or_si256(sum, sum2);
     } while (!_mm256_testz_si256(sum3, sum3));
#else
     // Just some example values (not really constant - compiler will optimize away code incorrectly)
     uint64_t cur = 58;
     uint64_t cur2 = 142;
     uint64_t factor = 67;

     if (cur < cur2) {
        std::swap(cur, cur2);
    }
    while (cur < totalX) {
        sieveX[cur >> 6] |= (1ULL << (cur & 0x3f));
        sieveX[cur2 >> 6] |= (1ULL << (cur2 & 0x3f));
        cur += factor;
        cur2 += factor;
    }
    while (cur2 < totalX) {
        sieveX[cur2 >> 6] |= (1ULL << (cur2 & 0x3f));
        cur2 += factor;
    }
#endif
}

Имейте в виду, что места могут сначала перекрываться. Через некоторое время в цикле это не так. Я был бы рад использовать другой подход, если это возможно. Примерно 82% времени в этой части алгоритма находится в этом цикле. Надеюсь, это не слишком близко к другим опубликованным вопросам.

Answer 1

Я только что посмотрел, что именно вы здесь делаете: для случая mod1 = mod3 = _mm256_set1_epi64x(1); вы просто устанавливаете отдельные биты в битовой карте с элементами ans в качестве индекса.

И он развернут двумя, с ans и ans2, работающими параллельно, используя mod1 << ans и mod3 << ans2. Прокомментируйте свой код и объясните, что происходит на большой картинке, используя английский текст! Это просто очень сложная реализация цикла установки битов обычного сита Эратосфена. (Так что было бы неплохо, если бы вопрос был задан в первую очередь.)

Развертывание с несколькими параллельными стартами / шагами - очень хорошая оптимизация, поэтому обычно вы устанавливаете несколько битов в строке кэша, пока в L1d все еще жарко. Кэш-блокировка для меньшего количества различных факторов одновременно имеет аналогичные преимущества . Итерируйте один и тот же фрагмент памяти размером 8 кБ или 16 кБ для нескольких факторов (шагов), прежде чем переходить к следующему. Развертывание с 4 смещениями для каждого из 2 различных шагов может быть хорошим способом создания большего количества ILP.

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

---

Возможен особый случай для шагов <256 </h3> Одна 256-битная векторная загрузка / VPOR / хранилище может устанавливать несколько битов. Хитрость заключается в создании векторной константы или набора векторных констант с битами в правильном положении. Тем не менее, повторяющийся шаблон имеет длину LCM(256, bit_stride) бит. Например, шаг = 3 повторяется в шаблоне длиной 3 вектора. Это очень быстро становится непригодным для нечетных / простых шагов, если нет чего-то более умного: ( 64-битный скаляр интересен тем, что для создания последовательности шаблонов доступно побитовое вращение, но вращение с переменным числом на процессорах семейства SnB стоит 2 моп. Возможно, вы сможете сделать больше с этим; может быть, что-то поможет не выровненные нагрузки. Повторяющийся шаблон битовых масок может быть полезен даже для случая большого шага, например, вращаясь на stride % 8 каждый раз. Но это было бы более полезно, если бы вы выполняли цикл JIT, который жестко закодировал шаблон в or byte [mem], imm8, с выбранным коэффициентом развертывания, соответствующим конгруэнтной длине. Уменьшение конфликтов с более узкими грузами / магазинами Вам не нужно загружать / изменять / хранить 64-битные блоки, когда вы устанавливаете только один бит. Чем уже ваши операции RMW, тем ближе могут быть ваши битовые индексы без конфликта. (Но у вас нет длинной переносимой цепочки деп в одном и том же месте; вы будете двигаться дальше, пока OoO exec не остановится, ожидая перезагрузки в конце длинной цепочки. Так что, если конфликты не являются корректными проблема в том, что здесь вряд ли что-то изменится. В отличие от растровой гистограммы или чего-то, где может легко произойти длинная цепочка повторных попаданий на соседние биты.) 32-битные элементы были бы очевидным выбором. x86 может эффективно загружать / хранить слова в / из регистров SIMD, а также скаляр. (скалярные операции с байтами тоже эффективны, но для хранения байтов из регистров SIMD всегда требуется несколько операций ввода с pextrb.) Если вы не собираете в регистры SIMD, ширина элемента SIMD для ans / ans2 не должна совпадать с шириной RMW. 32-битный RMW имеет преимущества перед 8-битными, если вы хотите разделить битовый индекс на адрес / битовое смещение в скаляре, используя сдвиги или bts, которые неявно маскируют счетчик сдвигов до 32 бит (или 64 бит для 64-битных). сдвиги немного). Но 8-битный shlx или bts не существует. Основное преимущество использования 64-битных элементов SIMD заключается в том, что вы вычисляете указатель, а не просто индекс. Если бы вы могли ограничить свой sieveX до 32 бит, вы все равно могли бы сделать это. например выделить с mmap(..., MAP_32BIT|MAP_ANONYMOUS, ...) в Linux. Предполагается, что вам не нужно более 2 ^ 32 бит (512 МБ) пространства сита, поэтому ваши битовые индексы всегда соответствуют 32-битным элементам. Если это не так, вы все равно можете использовать 32-битную векторы элементов до этой точки, затем используйте токовую петлю для старшей части. Если вы используете 32-битные элементы SIMD, не ограничивая sieveX в качестве 32-битного точечного указателя, вам придется отказаться от использования вычислений SIMD-указателя и просто извлечь бит-индекс или все еще разделить SIMD на idx / bit и извлеките оба. (С 32-битными элементами SIMD -> скалярная стратегия, основанная на сохранении / перезагрузке, выглядит еще более привлекательной, но в C это в основном зависит от вашего компилятора.) Если вы собирали вручную 32-битные элементы, вы больше не могли бы использовать movhps . Вы должны будете использовать pinsrd / pextrd для старших 3 элементов, и тем, кто никогда не использует микроплавкий предохранитель / всегда нужен порт 5 в UB-семействе. (В отличие от movhps, который является чистым магазином). Но это означает, что vpinsrd по-прежнему 2 моп с индексированным режимом адресации. Вы все еще могли бы использовать vmovhps для элемента 2 (затем переписать верхнее двойное слово вектора с помощью vpinsrd); не выровненные грузы дешевы, и можно перекрывать следующий элемент. Но вы не можете делать movhps магазинов, и это было действительно хорошо. Есть две больших проблемы производительности с вашей текущей стратегией : Очевидно, вы иногда используете это с некоторыми элементами mod1 или mod3, равными 0, что приводит к совершенно бесполезной потраченной впустую работе, выполняя [mem] |= 0 для этих шагов. Я думаю, как только элемент в ans или ans2 достигнет total, вы выпадете из внутреннего цикла и будете делать ans -= sum 1 каждый раз в течение внутренний цикл. Не обязательно сбрасывать его обратно ans = sum (для этого элемента), чтобы повторить ORing (установочные биты, которые уже были установлены), потому что эта память будет холодной в кеше. Что мы действительно хотим, так это упаковать оставшиеся в использовании элементы в известные места и ввести другие версии цикла, которые выполняют всего 7, затем 6, а затем 5 элементов. Тогда мы до 1 вектора. Это кажется действительно неуклюжим. Лучшая стратегия для одного элемента, достигающего конца, может заключаться в том, чтобы завершить оставшиеся три в этом векторе скалярным, по одному, а затем запустить оставшийся одиночный вектор __m256i. Если все шаги находятся поблизости, вы, вероятно, получите хорошую локальность кэша. Дешевле скаляр, или, может быть, все еще SIMD, но извлечь только битовый индекс

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

Если мы сможем заставить компилятор делать хороший скалярный код для разделения битового индекса, мы могли бы рассмотреть чистый скаляр. Или, по крайней мере, извлечь только битовые индексы и пропустить SIMD-сдвиг / маску.

Жаль, что скалярное назначение памяти bts не быстрое. bts [rdi], rax установит этот бит в строке битов, даже если он находится за пределами dword, выбранного [rdi]. (Такое сумасшедшее поведение CISC , почему это не быстро, хотя! Как 10 мопов на Skylake.)

Чистый скаляр, возможно, не идеален. Я играл с этим на Годболте :

#include <immintrin.h>
#include <stdint.h>
#include <algorithm>

// Sieve the bits in array sieveX for later use
void sieveFactors(uint64_t *sieveX64, unsigned cur1, unsigned cur2, unsigned factor1, unsigned factor2)
{
    const uint64_t totalX = 5000000;
#ifdef USE_AVX2
//...
#else
     //uint64_t cur = 58;
     //uint64_t cur2 = 142;
     //uint64_t factor = 67;
     uint32_t *sieveX = (uint32_t*)sieveX64;

    if (cur1 > cur2) {
        // TODO: if factors can be different, properly check which will end first
        std::swap(cur1, cur2);
        std::swap(factor1, factor2);
    }
    // factor1 = factor2;  // is this always true?

    while (cur2 < totalX) {
         sieveX[cur1 >> 5] |= (1U << (cur1 & 0x1f));
         sieveX[cur2 >> 5] |= (1U << (cur2 & 0x1f));
         cur1 += factor1;
         cur2 += factor2;
    }
    while (cur1 < totalX) {
         sieveX[cur1 >> 5] |= (1U << (cur1 & 0x1f));
         cur1 += factor1;
    }
#endif
}

Обратите внимание, как я заменил ваш внешний if () на выбор между циклами с сортировкой cur1, cur2.

GCC и clang помещают 1 в регистр вне цикла и используют shlx r9d, ecx, esi внутри цикла для выполнения 1U << (cur1 & 0x1f) за один цикл без разрушения 1. (MSVC использует load / BTS / store, но неуклюже с большим количеством mov инструкций. Я не знаю, как сказать MSVC, что разрешено использовать BMI2.)

Если бы индексированный режим адресации для or [mem], reg не стоил лишних ударов, это было бы здорово.

Проблема в том, что вам нужно где-то там shr reg, 5, и это разрушительно. Помещение 5 в регистр и использование его для копирования + сдвига битового индекса было бы идеальной установкой для загрузки / BTS / store, но компиляторы не знают, что оптимизация кажется.

Оптимальное (?) Скалярное разбиение и использование битового индекса

   mov   ecx, 5    ; outside the loop

.loop:
    ; ESI is the bit-index.
    ; Could be pure scalar, or could come from an extract of ans directly

    shrx  edx, esi, ecx           ; EDX = ESI>>5 = dword index
    mov   eax, [rdi + rdx*4]
    bts   eax, esi                ; set esi % 32 in EAX
    mov   [rdi + rdx*4]


    more unrolled iterations

    ; add   esi, r10d               ; ans += factor if we're doing scalar

    ...
    cmp/jb .loop

Итак, учитывая битовый индекс в регистре GP, это 4 мопа, чтобы установить бит в памяти. Обратите внимание, что загрузка и сохранение выполняются с mov, поэтому индексированные режимы адресации не влияют на Haswell и более поздние версии.

Но лучшее, что я мог сделать для компиляторов, было 5, я думаю, используя shlx / shr / or [mem], reg. (В режиме индексированной адресации or равно 3 моп вместо 2.)

Я думаю, что если вы хотите использовать рукописный asm, вы можете быстрее работать с этим скалярным и канавым SIMD полностью. Конфликты никогда не являются проблемой правильности для этого.

Может быть, вы даже можете заставить компилятор выдавать что-то сравнимое, но даже один дополнительный моп на развернутый RMW это большое дело.

Answer 2

IDK, почему вы используете разные части одного и того же массива cur[8] для индексов и значений; это усложнило понимание источника, чтобы понять, что существует только один реальный массив. Другой - просто перебрасывать векторы в скаляры.

Похоже, у вас есть только вектор -> скаляр, не вставляя скаляры обратно в вектор. А также, что ничто внутри цикла не зависит от каких-либо данных в sieveX[]; Я не знаком с вашим алгоритмом просеивания, но, полагаю, смысл в том, чтобы создать данные в памяти для последующего использования.

---

AVX2 имеет сборы (не разбрасывает), но они работают только на Skylake и новее . Они в порядке на Broadwell, медленнее на Haswell и медленнее на AMD. (Как один на 12 часов для Райзена vpgatherqq). См. http://agner.org/optimize/ и другие ссылки на производительность в вики-теге x86 .

В руководстве по оптимизации Intel есть небольшой раздел, посвященный ручному сбору / разбрасыванию (с использованием вставки / извлечения или movhps) и аппаратных инструкций, которые, возможно, стоит прочитать. В этом случае, когда индексы являются переменными времени выполнения (не постоянным шагом или чем-то еще), я думаю, что Skylake может извлечь выгоду из инструкций по сбору AVX2 здесь.

См. Руководство по встроенным функциям Intel для поиска встроенных инструкций asm, таких как movhps. Я просто говорю о том, что вы хотите, чтобы ваш компилятор испускал, потому что это то, что важно, и мнемоника asm короче, чтобы печатать и не нуждается в приведении. Вы должны знать мнемонику asm, чтобы искать их в таблицах инструкций Agner Fog, или читать выходные данные компилятора из векторизации, поэтому я обычно думаю в asm, а затем транслирую это в intrinsics.

---

С AVX у вас есть 3 основных варианта:

• делать все скалярно. Регистрация давления может быть проблемой, но генерация индексов по мере необходимости (вместо того, чтобы делать все 4 добавления или подпрограммы для генерации curr[4..7] сразу) может помочь. Если эти mask векторы не имеют разных значений в разных элементах.

  (Использование источников памяти для скалярных констант может быть неплохим, однако, если они не помещаются в 32-разрядные операции немедленного доступа и если вы не ограничиваете 2 операции памяти за такт. Назначение памяти or инструкции будет использовать режимы индексированной адресации, поэтому нельзя использовать выделенный AGU хранилища на порту 7 в Haswell и более поздних версиях. Таким образом, пропускная способность AGU может быть узким местом.)

  Извлечение всех 4 элементов вектора в виде скаляра обходится дороже, чем 4x скаляр add или инструкции по сдвигу, но вы выполняете больше работы, чем это. Тем не менее, с BMI2 для сдвигов с переменным числом 1 моп (вместо 3 на Intel) это может быть не страшно. Я думаю, что мы сможем добиться большего успеха с SIMD, особенно при тщательной настройке.

• извлекает индексы и значения в скалярные значения, как вы делаете сейчас, поэтому ИЛИ в sieveX[] является чистым скаляром . Работает, даже если два или более индекса совпадают.

  Это будет стоить вам около 7 мопов на вектор ymm -> 4х скалярных регистров с использованием инструкций извлечения ALU или 5 мопов с использованием сохранения / перезагрузки (стоит учитывать для компилятора, возможно, для одного или двух из 4 векторных извлечений, потому что этот код вероятно, не удается узкое место по пропускной способности порта загрузки / сохранения.) Если компилятор превращает сохранение / перезагрузку в источнике C в инструкции shuffle / extract, вы не можете легко переопределить его стратегию, разве что с помощью volatile. И кстати, вы бы хотели использовать alignas(32) cur[8], чтобы убедиться, что фактические векторные хранилища не пересекают границу строки кэша.

  or [rdi + rax*8], rdx ( с индексированным режимом адресации, предотвращающим полное микросинтезирование ) - 3 моп на современных процессорах Intel (Haswell и более поздних). Мы могли бы избежать индексированного режима адресации (сделав его 2 моп для внешнего интерфейса), масштабируя + добавляя к базовому адресу массива с помощью SIMD : например, srli 3 вместо 6, замаскируйте младшие 3 бита (vpand) и vpaddq с set1_epi64(sieveX). Таким образом, это требует 2 дополнительных SIMD-инструкции для сохранения 4 мопов на семействе SnB на каждый вектор индексов. (Вы извлекаете uint64_t* элементы указателя вместо uint64_t индексов. Или, если sieveX может быть 32-битным абсолютным адресом ¹ , вы можете пропустить vpaddq и извлечь уже масштабированный индексы для того же усиления.)

  Это также позволило бы мопам с адресом магазина работать на порту 7 (Haswell и более поздние версии) ; простой AGU на порту 7 может обрабатывать только неиндексированные режимы адресации. (Это делает извлечение значений для скалярного с помощью store + reload более привлекательным. Вы хотите меньшую задержку для извлечения индексов, потому что значения не нужны до тех пор, пока не завершится загрузка части памяти-dst or.) Это означает, что больше не используется -домен мопов для планировщика / исполнительных блоков, но вполне может стоить компромисса.

  Это не победа на других процессорах AVX2 (экскаватор / Ryzen или Xeon Phi); только семейство SnB имеет входную стоимость и ограничения порта выполнения для индексированных режимов адресации.

• извлечь индексы, вручную собрать в вектор с vmovq / vmovhps для SIMD vpor, затем рассеять обратно с помощью vmovq / vmovhps.

  Точно так же, как HW-сбор / рассеяние, корректность требует, чтобы все индексы были уникальными , поэтому вы захотите использовать один из указанных выше вариантов, пока не дойдете до этой точки в своем алгоритме. (Обнаружение конфликтов векторов + откат не будет стоить затрат по сравнению с обычным извлечением в скаляр: Реализация откатов для обнаружения конфликтов в AVX2 ).

  См. выборочную запись элементов списка с инструкциями AVX2 для встроенной версии. (Я знал, что недавно написал ответ с ручным сбором / разбросом, но мне потребовалось некоторое время, чтобы найти его!) В этом случае я использовал только 128-битные векторы, потому что не было никакой дополнительной работы SIMD, чтобы оправдать дополнительную vinserti128 / vextracti128.

  На самом деле я думаю, что здесь вы захотите извлечь верхнюю половину результата _mm256_sllv_epi64, чтобы у вас были (данные, которые будут) cur[4..5] и cur[6..7] в двух отдельных __m128i переменных. Вы бы получили vextracti128 / 2x vpor xmm вместо vinserti128 / vpor ymm / vextracti128.

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

  Выполнение вычисления адреса в векторе 256b и извлечение указателей вместо индексов может снизить нагрузку на vmovhps на Intel (индексированные нагрузки не могут оставаться слитыми до vmovhps ² ). Смотрите предыдущий пункт. Но vmovq загрузки / хранилища - это всегда один моп, и индексированные хранилища vmovhps могут оставаться на плаву в Haswell и более поздних версиях, так что это безубыточность для внешней пропускной способности и хуже для AMD или KNL. Это также означает больше мопов в неиспользуемом домене для планировщика / исполнительных блоков, что выглядит скорее как потенциальное узкое место, чем давление AGU порта 2/3. Единственным преимуществом является то, что мопы с адресом магазина могут работать на порту 7, что снимает некоторое давление.

AVX2 дает нам одну новую опцию:

• AVX2 vpgatherqq для сбора (_mm256_i64gather_epi64(sieveX, srli_result, 8)), затем извлекайте индексы и разбрасывайте вручную. Так что это похоже на ручной сбор / разброс вручную, за исключением того, что вы заменяете сбор вручную на аппаратная сборка AVX2. (Две 128-битные сборки стоят больше, чем одна 256-битная сборка, так что вы захотите взять удар параллелизма на уровне команд и собрать в один 256-битный регистр).

  Возможно, выигрыш на Skylake (где vpgatherqq ymm - это пропускная способность 4 моп / 4 с, плюс 1 моп настройки), но не даже Broadwell (9 моп, один на пропускную способность 6c) и определенно не Haswell (пропускная способность 22 моп / 9 c) ). В любом случае вам нужны индексы в скалярных регистрах, так что вы только сохраняете часть работы, собранную вручную. Это довольно дешево.

---

Общая стоимость каждой стратегии на Skylake

Похоже, это не будет узким местом для какого-либо одного порта. GP reg-> xmm нужен порт 5, но xmm-> int нужен порт 0 на процессорах семейства SnB, поэтому менее вероятно, что узкое место на порту 5 будет смешано с шаффлами, необходимыми для извлечения. (например, vpextrq rax, xmm0, 1 - это команда 2 uop, один порт 5 shuffle uop для захвата высокого qword и порт 0 uop ​​для отправки этих данных из SIMD в целочисленный домен.)

Так что ваш расчет SIMD, где вам нужно часто извлечь вектор в скаляр менее плохо, чем если бы вам нужно было часто вставлять скалярные результаты вычислений в векторы. См. Также Загрузка xmm из регистров GP , но речь идет о данных, которые начинаются в регистрах GP, а не в памяти.

• извлечение обоих / скалярное ИЛИ: всего = 24 моп = 6 циклов входной пропускной способности.

  • vpaddq + vpand address calc (2 моп для порта 0/1/5 на Skylake)
  • 2x vextracti128 (2 моп для порта 5)
  • 4x vmovq (4 p0)
  • 4x vpextrq (8: 4p0 4p5)
  • 4x or [r], r (4x2 = 8 входных элементов каждого. Backend: 4p0156 4p23 (загрузка) 4p237 (сохранение-адреса) 4p4 (сохранение-данные)). Неиндексированный режим адресации.

  Итого = 6 моп для р5, едва подходит. Сохранение / перезагрузка для извлечения данных выглядит разумно, если бы вы могли заставить свой компилятор сделать это. (Но компиляторы обычно не моделируют конвейер достаточно подробно, чтобы использовать комбинацию стратегий в одном и том же цикле для балансировки давления порта.)

• Ручная сборка / разбрасывание: 20 моп, 5 циклов пропускной способности фронтальной части (Haswell / BDW / Skylake). Также хорошо на Ryzen.

  • (необязательно, вероятно, не стоит): vpaddq + vpand address calc (2 мопа для порта 0/1/5 на Skylake) Пропустите их, если вы можете использовать не-VEX movhps для 1-мегапиксельной микроплавкой индексированная нагрузка. (Но тогда магазины p237 становятся p23).
  • vextracti128 указатели (1 моп для порта 5)
  • 2x экстракт vmovq (2p0)
  • 2x vpextrq (4 = 2p0 2p5)
  • 2x vmovq load (2p23)

  • 2x vmovhps xmm, xmm, [r] неиндексированная нагрузка (2 входных микроконтроллера: 2p23 + 2p5)

  • vextracti128 разделить данные (p5)

  • 2x vpor xmm (2p015)
  • 2x vmovq store (2x 1 микроплавленый моп, 2p237 + 2p4)
  • 2x vmovhps store (2x 1 микроплавленый моп, 2p237 + 2p4)

  Узкие места в портах: 4 p0 и 4 p5 удобно размещаются в 5 циклах, особенно когда вы смешиваете это с вашим циклом, который может выполнять несколько своих мопов на порте 1. На Haswell paddq - это только p15 (не p015), и сдвиги только р0 (не р01). AVX2 _mm256_sllv_epi64 - это 1 моп (p01) на Skylake, а на Haswell - 3 моп = 2p0 + p5. Таким образом, Haswell может быть ближе к узкому месту p0 или p5 для этого цикла, и в этом случае вы можете рассмотреть стратегию извлечения с сохранением / перезагрузкой для одного вектора индексов.

  Пропуск вычисления SIMD-адреса, вероятно, хорош, поскольку давление AGU не выглядит проблемой, если вы не используете извлечение для сохранения / перезагрузки. И это означает меньше команд / меньший размер кода и меньше мопов в кеше мопов. (Разрушение не происходит до окончания кэширования декодеров / UOP, поэтому вы все еще выигрываете от микросинтеза в ранних частях интерфейса, но не в узком месте проблемы.)

• Сборка / ручное рассеяние Skylake AVX2: Всего = 18 мопов, 4,5 цикла входной пропускной способности. (Хуже на любом более раннем Uarch или AMD).

  • vextracti128 индексы (1 моп для порта 5)
  • 2x экстракт vmovq (2p0)

  • 2x vpextrq (4 = 2p0 2p5)

  • vpcmpeqd ymm0,ymm0,ymm0 создать маску "все единицы" для vpgatherqq (p015)

  • vpgatherqq ymm1, [rdi + ymm2*8], ymm0 4 моп для некоторых портов.

  • vpor ymm (p015)

  • vextracti128 в результате ИЛИ (p5)
  • 2x vmovq store (2x 1 микроплавленый моп, 2p23 + 2p4). Обратите внимание на порт 7, мы используем индексированные хранилища.
  • 2x vmovhps store (2x 1 микроплавленый моп, 2p23 + 2p4).

Таким образом, даже при наилучшем выборе пропускной способности мы по-прежнему управляем только 4 загрузками / 4 хранилищами за 4,5 цикла, и это без учета работы SIMD в цикле, которая стоит некоторой интерфейсной пропускной способности. Так что мы не близки к узким местам в пропускной способности AGU и не должны беспокоиться об использовании порта 7.

Возможно, мы могли бы подумать о сохранении / перезагрузке для одного из экстрактов (если бы мы были компилятором), заменив последовательность 7 uop 5 vextracti128 / 2x vmovq / 2x vpextrq последовательностью 5 uops store / 4x load.

---

В целом: один цикл, пока мы не закончим с конфликтами, затем SIMD-цикл сбора

Вы говорите, что после определенного момента у вас нет конфликтов (совпадений) между такими индексами, как cur[0] == cur[2].

Вам определенно нужен отдельный цикл, который вообще не проверяет наличие конфликтов, чтобы воспользоваться этим. Даже если у вас был AVX512, vpconflictq Skylake - это микрокод и не быстрый. (У KNL есть single-uop vpconflictq, но его все же быстрее избежать).

Я оставлю на ваше усмотрение (или отдельный вопрос), как точно выяснить, когда вы покончили с конфликтами, и можете выйти из цикла, объясняющего такую ​​возможность.

Возможно, вам нужна стратегия извлечения индексов + данных, в то время как могут быть конфликты. Проверка конфликта SIMD возможна, но это не дешево, 11 моп для 32-битных элементов: Реализация резервной реализации для обнаружения конфликтов в AVX2 . Версия qword, очевидно, намного дешевле, чем dword (меньше тасует и сравнивает, чтобы получить все против всех), но вы, вероятно, все еще хотите делать это каждые 10 итераций или около того вашего цикла извлечения.

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

Так что, если вы можете надежно обнаружить, когда вы закончили с конфликтами, используйте что-то вроде

int conflictcheck = 10;

do {

    if (--conflictcheck == 0) {
       vector stuff to check for conflicts
       if (no conflicts now or in the future)
           break;

       conflictcheck = 10;  // reset the down-counter
    }

    main loop body,  extract -> scalar OR strategy

} while(blah);


// then fall into the gather/scatter loop.
do {
    main loop body, gather + manual scatter strategy
} while();

Это должно компилироваться в dec / je, который стоит только 1 моп в невыполненном случае.

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

---

Сноска 1 :

Если sieveX является статическим и вы создаете не PIC-код в Linux (не MacOS), тогда его адрес будет соответствовать disp32 как часть режима адресации [reg+disp32]. В этом случае вы можете пропустить vpaddq. Но заставить компилятор трактовать uint64_t как уже масштабированный индекс массива (с очищенными младшими битами) было бы ужасно. Вероятно, придется привести sieveX к uintptr_t и добавить, затем вернуть обратно.

Это невозможно в исполняемом файле PIE или совместно используемой библиотеке (где 32-разрядные абсолютные адреса запрещены) или вообще в OS X (где статические адреса всегда больше 2 ^ 32). Я не уверен, что позволяет Windows. Обратите внимание, что [disp32 + reg*8] имеет только 1 регистр, но все еще является индексированным режимом адресации, поэтому применяются все штрафы семейства SnB. Но если вам не нужно масштабирование, reg + disp32 - это просто base + disp32.

Сноска 2 : Интересный факт: нагрузки не-VEX movhps могут оставаться в микросреде на Haswell. Это не приведет к остановке SSE / AVX на Skylake, но вы не получите компилятор, который будет выдавать версию без VEX в середине функции AVX2 .

IACA (инструмент статического анализа Intel), однако, ошибается. :( Что такое IACA и как мне его использовать? .

Это в основном пропущенная оптимизация для -mtune=skylake, но она будет останавливаться на Haswell: Почему этот код SSE в 6 раз медленнее без VZEROUPPER на Skylake? .

"Штраф A" (выполнить SSE с грязным верхом) на Skylake - просто ложная зависимость от этого одного регистра. (И объединяющий uop для инструкций, которые в противном случае были бы доступны только для записи, но movhps уже является объектом чтения-изменения-записи своего назначения.) Я проверил это на Skylake с Linux perf, чтобы подсчитать количество мопов, с помощью этого цикла:

    mov     r15d, 100000000

.loop:
    vpaddq  ymm0, ymm1, ymm2      ; dirty the upper part
    vpaddq  ymm3, ymm1, ymm2      ; dirty another register for good measure

    vmovq  xmm0, [rdi+rbx*8]       ; zero the full register, breaking dependencies
    movhps xmm0, [rdi+rbx*8+8]     ; RMW the low 128 bits
                          ; fast on Skylake, will stall on Haswell

    dec r15d
    jnz .loop

Цикл работает на ~ 1,25 циклах на итерацию на Skylake (i7-6700k), максимизируя пропускную способность внешнего интерфейса 4 мопа за такт. Всего 5 мопов с слитными доменами (uops_issued.any), 6 мопов с не слитыми доменами (uops_executed.thread). Таким образом, микро-синтез определенно происходил для movhps без каких-либо проблем с SSE / AVX.

Изменение его на vmovhps xmm0, xmm0, [rdi+rbx*8+8] замедлило его до 1,50 циклов на итерацию, теперь 6 слитых доменов, но все еще те же 6 мопов с неиспользованным доменом.

Никакого дополнительного мопа нет, если верхняя половина ymm0 загрязнена, когда movhps xmm0, [mem] работает. Я проверил, комментируя vmovq. Но изменение vmovq на movq приводит к результату в виде дополнительного uop: movq становится микросинхронизированной нагрузкой + слиянием, которая заменяет младшие 64 бита (и все еще обнуляет верхние 64 бита xmm0, так что это не совсем movlps).

---

Также обратите внимание, что pinsrq xmm0, [mem], 1 не может использовать микроплавкий предохранитель даже без VEX. Но с VEX вы предпочитаете vmovhps из соображений размера кода.

Ваш компилятор может захотеть "оптимизировать" встроенную функцию для movhps целочисленных данных в vpinsrq, хотя я не проверял.