Резервная реализация для обнаружения конфликтов в AVX2

Ответ 1

TL: DR: поскольку полное обнаружение конфликта элементов дорого, возможно, стоит потратить больше усилий на возврат в обмен на более дешевое обнаружение. Это зависит от ваших вариантов/стратегий управления конфликтами.

Я придумал довольно эффективный способ проверить наличие/отсутствие конфликтов, не найдя их местоположения, например этот ответ для 64-битных целых элементов. Это на самом деле быстрее, чем Skylake-AVX512 с микрокодированием vpconflictd ymm, но, конечно, это дает вам гораздо меньше информации. (KNL имеет быстрый vpconflictd).

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

Поведение только влево или только вправо трудное, но мой метод может дать вам маску, какие элементы конфликтуют с любым другим элементом (например, v[0] == v[3] приведет к тому, что как conflict[0], так и conflict[3] будет истинным). Это стоит всего 1 дополнительный перетасовку, или, может быть, 0 с редизайном с этой целью.

(Сначала я неправильно понял вопрос, я думал, что вы хотите проверить оба направления, вместо того, чтобы говорить о двух разных вариантах реализации для большей части того, что делает vpconflictd. Фактически сначала я думал, что вам просто нужна проверка наличия/отсутствия, как bool any_conflicts(__m256i).)

Поиск наличия/отсутствия конфликтов: bool any_conflicts32(__m256i)

8 choose 2 - это 28 полных скалярных сравнений. Это 3,5 вектора упакованных сравнений. Мы должны стремиться сделать это с помощью 4 векторных сравнений, что оставляет место для некоторой избыточности.

Создание входных данных для этих сравнений потребует перетасовки, и некоторые из них должны быть пересекающимися полосами. Для 4 уникальных сопоставлений требуется не менее 4 векторов (включая исходную неповрежденную копию), так как 3 выбрать 2 - всего 3.

В идеале как можно меньше перетасовки пересекаются, и существует множество ILP для сравнения и ORing результатов сравнения. Также приятно, если в тасования не требуется векторный контроль тасования, просто imm8. Также хорошо, если они не замедляются на AMD Ryzen, где 256b команд декодируются на несколько 128-бит. (Некоторые тасования хуже других, например, vperm2i128 очень плохо, гораздо хуже, чем vpermq для замены верхней и нижней половин одного вектора. К сожалению, clang ошибочно делает это даже с -mtune=znver1 и компилирует _mm256_permute4x64_epi64 в vperm2i128, когда это возможно).

Я нашел решение довольно рано, чтобы достичь большинства из этих целей: 3 перетасовки, 4 сравнения. Один из перетасовков находится в полосе. Все они используют вместо байта непосредственный управляющий байт.

// returns a 0 or non-zero truth value
int any_conflicts32(__m256i v)
{
    __m256i hilo       = _mm256_permute4x64_epi64(v, _MM_SHUFFLE(1,0,3,2));  // vpermq is much more efficient than vperm2i128 on Ryzen and KNL, same on HSW/SKL.
    __m256i inlane_rotr1 = _mm256_shuffle_epi32(v, _MM_SHUFFLE(0,3,2,1));
    __m256i full_rotl2 = _mm256_permute4x64_epi64(v, _MM_SHUFFLE(2,1,0,3));

    __m256i v_ir1 = _mm256_cmpeq_epi32(v, inlane_rotr1);
    __m256i v_hilo= _mm256_cmpeq_epi32(v, hilo);           // only really needs to be a 128b operation on the low lane, with leaving the upper lane zero.
                                                           // But there no ideal way to express that with intrinsics, since _mm256_castsi128_si256 technically leaves the high lane undefined
                                                           // It extremely likely that casting down and back up would always compile to correct code, though (using the result in a zero-extended register).
    __m256i hilo_ir1 = _mm256_cmpeq_epi32(hilo, inlane_rotr1);
    __m256i v_fl2 = _mm256_cmpeq_epi32(v, full_rotl2);

    __m256i t1 = _mm256_or_si256(v_ir1, v_hilo);
    __m256i t2 = _mm256_or_si256(t1, v_fl2);
    __m256i conflicts = _mm256_or_si256(t2, hilo_ir1);    // A serial dep chain instead of a tree is probably good because of resource conflicts from limited shuffle throughput

    // if you're going to branch on this, movemask/test/jcc is more efficient than ptest/jcc

    unsigned conflict_bitmap = _mm256_movemask_epi8(conflicts);  // With these shuffles, positions in the bitmap aren't actually meaningful
    return (bool)conflict_bitmap;
    return conflict_bitmap;
}

Как я разработал этот:

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

Я начал с нескольких тасований, которые можно было сделать дешево, и оказалось, что мои ранние догадки работали достаточно хорошо.

Мои примечания к дизайну:

    // 7 6 5 4 | 3 2 1 0

    // h g f e | d c b a
    // e h g f | a d c b    // inlanerotr1 = vpshufd(v)
    // f e d c | b a h g    // fullrotl2 = vpermq(v)

    // d c b a | h g f e    // hilo = vperm2i128(v) or vpermq.  v:hilo has lots of redundancy.  The low half has all the information.

          v:lrot1      v:frotr2     lrotr1:frotl2                (incomplete)
 * ab   [0]v:lrotr1                 [3]lr1:fl2
 * ac                  [2]v:frotl2
 * ad   [3]v:lrotr1                 [2]lr1:fl2
 * ae                                                                           [0,4]v:hilo
 * af                                           [4]hilo:lrotr1
 * ag                  [0]v:frotl2
 * ah                                           [3]hilo:lrotr1

 * bc   [1]v:lrotr1
 * bd                  [3]v:frotl2                               [5]hilo:frotl2
 * be                                           [0]hilo:lrotr1
 * bf                                                                           [1,5]v:hilo
 * bg                               [0]lr1:fl2  [5]hilo:lrotr1
 * bh                  [1]v:frotl2

 * cd   [2]v:lrotr1
 * ce                  [4]v:frotl2  [4]lr1:fl2
 * cf                                           [1]hilo:lrotr1
 * cg                                                                           [2,6]v:hilo
 * ch                               [1]lr1:fl2  [6]hilo:lrotr1

 * de                                           [7]hilo:lrotr1
 * df                  [5]v:frotl2                               [7]hilo:frotl2
 * dg                               [5]lr1:fl2  [2]hilo:lrotr1
 * dh                                                                           [3,7]v:hilo

 * ef   [4]v:lrotr1                 [7]lr1:fl2
 * eg                  [6]v:frotl2
 * eh   [7]v:lrotr1                 [6]lr1:fl2

 * fg   [5]v:lrotr1
 * fh                  [7]v:frotl2

 * gh   [6]v:lrotr1

 */

Оказывается, что в полосе rotr1 == полный rotl2 имеет много избыточности, поэтому его не стоит использовать. Также выясняется, что все допустимое резервирование в v==hilo отлично работает.

Если вы заботитесь о том, какой результат в каком элементе (а не просто проверять наличие/отсутствие) то v == swap_hilo(lrotr1) мог бы работать вместо lrotr1 == hilo.  Но нам также нужно swap_hilo(v), так что это будет означать дополнительный перетасовку.

Мы могли вместо этого перетасовать после hilo == lrotr1, для лучшего ILP. Или, может быть, есть другой набор тасов, который дает нам все. Может быть, если мы рассмотрим VPERMD с векторным контролем тасования...

Выход ASM компилятора против оптимального asm

gcc6.3 -O3 -march=haswell производит:

Хасуэлл имеет один блок перетасовки (на порту5).

   # assume ymm0 ready on cycle 0
    vpermq  ymm2, ymm0, 78     # hilo ready on cycle 3 (execution started on cycle 0)
    vpshufd ymm3, ymm0, 57     # lrotr1 ready on cycle 2  (started on cycle 1)
    vpermq  ymm1, ymm0, 147    # frotl2 ready on cycle 5  (started on 2)
    vpcmpeqd  ymm4, ymm2, ymm0  # starts on 3, ready on 4
    vpcmpeqd  ymm1, ymm1, ymm0  # starts on 5, ready on 6
    vpcmpeqd  ymm2, ymm2, ymm3  # starts on 3, ready on 4
    vpcmpeqd  ymm0, ymm0, ymm3  # starts on 2, ready on 3
    vpor    ymm1, ymm1, ymm4    # starts on 6, ready on 7
    vpor    ymm0, ymm0, ymm2    # starts on 4, ready on 5
    vpor    ymm0, ymm1, ymm0    # starts on 7, ready on 8
         # a different ordering of VPOR merging could have saved a cycle here.  /scold gcc
    vpmovmskb       eax, ymm0
    vzeroupper
    ret

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

Это быстрее, чем Skylake-AVX512 vpconflictd ymm, который имеет задержку 17 с, по одной на 10с пропускную способность. (Конечно, это дает вам гораздо больше информации, а эмуляция @harold требует еще много инструкций).

К счастью, gcc не переупорядочил перетасовки и не представил потенциальный конфликт с обратной записью. (например, поместив vpshufd last, будет означать, что отправка shuffle uops на port5 в старом первом порядке будет иметь vpshufd в том же цикле, что и первый vpermq (задержка 1c против 3c).) gcc это для одной версии кода (где я сравнивал неправильную переменную), поэтому кажется, что gcc -mtune=haswell не учитывает это. (Может быть, это не очень важно, я не думал, что такое реальное влияние на латентность. Я знаю, что планировщик умеет выбирать uops из Станции резервирования, чтобы избежать конфликтов с обратной записью, но IDK, насколько он умен, то есть, будет ли он запускать vpshufd перед более поздним vpermq, чтобы избежать конфликта обратной записи, поскольку ему придется искать вперед, чтобы даже увидеть предстоящий конфликт обратной записи. Скорее всего, это просто задержит vpshufd для дополнительного цикла перед отправкой.)

В любом случае, поэтому я помещаю _mm_shuffle_epi32 в середину в источнике C, где это облегчает выполнение ООО.

Clang 4.0 идет berserk и упаковывает каждый результат сравнения до 128b векторов (с vextracti128/vpacksswb), а затем расширяется до 256b после трех vpor xmm до pmovmskb. Сначала я думал, что это делалось из-за -mtune=znver1, но он делает это с помощью -mtune=haswell. Он делает это, даже если мы вернем a bool, что позволило бы ему просто pmovmskb/test на упакованном векторе. /Facepalm. Он также пессимизирует hilo shuffle до vperm2i128, даже с -mtune=znver1 (Ryzen), где vperm2i128 равно 8 uops, но vpermq равно 3. (Agner Fog insn tables по некоторым причинам пропустили их, поэтому я взял эти числа из эквивалентов FP vperm2f128 и vpermpd)

@harold говорит, что использование add вместо or останавливает clang от упаковки/распаковки, но vpaddd имеет более низкую пропускную способность, чем vpor на Intel pre-Skylake.

Еще лучше для Рызена, сравнение v == hilo может делать только низкую половину. (т.е. использовать vpcmpeqd xmm2, xmm2, xmm3, который составляет всего 1 мкп вместо 2). Однако нам все еще нужен полный hilo для hilo == lrot1. Поэтому мы не можем просто использовать vextracti128 xmm2, xmm0, 1 вместо vpermq shuffle. vextracti128 имеет отличную производительность по Ryzen: 1 uop, 1c latency, 0,33c пропускная способность (может работать на любом из P0/1/3).

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

Как я уже отмечал в комментариях, IDK, как безопасно писать это с помощью встроенных функций. Очевидным способом было бы использовать _mm256_castsi128_si256 (_mm_cmpeq_epi32(v, hilo)), но это технически оставляет верхнюю полосу undefined, а не ноль. Там нет разумного способа, чтобы компилятор делал что-либо, кроме использования полноразмерного ymm-регистра, который содержит регистр xmm с результатом сравнения 128b, но было бы законно в соответствии с документами Intel для компилятора Deathstation-9000 размещать там мусор. Любой явный способ получения нулей в верхней половине будет зависеть от компилятора, который его оптимизирует. Может быть, _mm256_setr_si128(cmpresult, _mm_setzero_si128());.

Нет текущих процессоров с AVX512F, но не AVX512CD. Но если это комбо интересно или уместно, clang делает интересный asm из моего кода с помощью -mavx512f -mavx512vl. Он использует EVEX vpcmpeqd в регистрах масок и korw, чтобы объединить их. Но затем он расширяет это обратно в вектор, чтобы настроить для vpmovmaskb, вместо того, чтобы просто оптимизировать анимацию movemask и использовать результат korw./Facepalm.