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

__mm256i detect_conflict(__mm256i a) {
__mm256i cd = _mm256_conflict_epi32(a);
return _mm256_cmpgt_epi32(cd, _mm256_set1_epi32(0));
}

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

Я придумал достаточно эффективный способ проверки наличия / отсутствия конфликтов, не находя их местоположения, например этот ответ для 64-битных целочисленных элементов. Это на самом деле быстрее, чем Skylake-AVX512 в микрокодировании vpconflictd ymm, но, конечно, это дает вам гораздо меньше информации. (КНЛ быстро 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.

В идеале, как можно меньше перестановок пересекают полосу, и есть много ИЛП для сравнения и ORing результатов сравнения. Также хорошо, если тасование не требует векторного управления тасованием, просто imm8, Также хорошо, если они не медленны на AMD Ryzen, где 256-битные инструкции декодируются в несколько 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's no ideal way to express that with intrinsics, since _mm256_castsi128_si256 technically leaves the high lane undefined
// It's 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 == full rotl2 много избыточности, поэтому его не стоит использовать. Также оказывается, что наличие всей разрешенной избыточности в v==hilo работает отлично.

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

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

---

Выходные данные компилятора по сравнению с оптимальной ASM

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

У 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, который имеет задержку 17c, по одному на пропускную способность 10c. (Конечно, это дает вам гораздо больше информации, и эмуляция @ harold требует намного больше инструкций).

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

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

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

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

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

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

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

---

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