Самый быстрый способ добавить смесь двойных слов и четырехъярусных слов с помощью AVX2?

Question

Я пишу код, который генерирует высоко оптимизированный машинный код, ориентированный на Haswell (поэтому у него есть инструкции AVX2), и я пытаюсь найти наиболее эффективный способ добавить заранее определенное количество четырехъядерных и двойных слов. Так, например, я мог бы иметь структуру, как это:

0-8: QWORD a 
8-16: QWORD b 
16-20: DWORD c 
20-28: QWORD d 
28-36: QWORD e 
36-40: DWORD f 
40-48: QWORD g 
48-56: QWORD h 
56-64: QWORD i 

Я хотел бы добавить это к другой структуре с одной и той же компоновке, таким образом, что (конечная) = а (первый) + а (второй), b (final) = b (первый) + b (второй) и т. д. Я смотрел инструкции VPADDUSD и VPADDUSQ, но, очевидно, ни одна из них не будет работать во всех случаях. VPADDUSD не удается добавить QWORD, которые превышают (2^32) -1. VPADDUSQ не работает, если QWORD не выравнивается по 8 байт. Я в порядке с переполнениями, в результате чего генерируются плохие данные. Я бы подумал, что неправильно спрогнозированная ветвь стоила твердых 15 циклов. Допустимо оптимизировать это для чисел, которые обычно не превышают 2^31. Идеи?

Answer 1

Загрузите структуру в регистр ymm. Перенесите такие слова, чтобы каждое dword было равно нулю в qword, и каждый qword находился на границе qword. Затем добавьте qword. Наконец, отмените перестановку, чтобы вернуть структуру назад. Отбросьте 32-разрядный бит для полей dword.

Например, для вашей структуры, вы могли бы сделать следующую последовательность операций:

Загрузить один 256 битное значение со смещением 0 структуры в ymm0. Регистр теперь должен содержать следующую DWORDs:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
al ah bl bh cx dl dh el eh fx gl gh hl hh il ih 

Теперь переставить регистр, используя vpermilps таким образом, что он содержит следующие значения:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
al ah bl bh cx xx dl dh fx xx gl gh hl hh il ih 

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

Обратите внимание, что el и eh исчезли из структуры, мы должны вручную добавить их в отдельный шаг. Мы исключаем el и eh вместо, скажем, il и ih, потому что мы не можем переставлять их по двум 128-битным дорожкам. Обратите внимание на то, что два слова (c и f) имеют нулевое расширение до 64 бит. Теперь вы можете добавить два регистра с этой перестановкой и применить соответствующую перестановку, чтобы упаковать их обратно, как они были раньше.

---

Если вы можете изменить порядок полей, это гораздо проще: Просто переставить их так, чтобы все qwords являются первыми, а затем всеми двойными словами. Теперь вы можете просто добавить все qwords за один шаг, а затем все слова без перетасовки.

Answer 2

Алгоритм, который я пишу часто будет ограничено кэшем , кроме L1

ответ Fuz должен быть быстрым, но, ограниченный кэш L2 означает, что некоторые задержки могут быть скрыты за он, например, добавляет поля DWORD после QWORDS, потому что, когда SIMD ALU заняты вычислением QWORD, вы можете загрузить эти 2 DWORDs из L2 (для добавления в скалярный блок).

Возможно, вам стоит провести сравнение, рассчитать QWORD, тогда как параллелизм уровня инструкций загружает DWORDs из L2. Загруженные DWORDS могут быть добавлены в скалярный ALU, чтобы получить еще больше параллелизма?

Но опять же, ответ fuz должен быть окончательным решением, поскольку все делается в CPU-регистрах раз и навсегда.

Answer 3

Для случая, когда некоторые перегруппировки, чтобы гарантировать, что qwords полностью содержится в 32-выровненный блоке они начинают в (так что они в конечном итоге в регистре вместо Spanning через два регистра), вы можете добавить DWORDs, а затем разрешает перенос только там, где вы хотите. Грубо говоря (не тестировалось)

vmovdqa ymm0, [x] 
vpaddd ymm1, ymm0, [y] 
vpmaxud ymm2, ymm1, ymm0 
vpcmpeqd ymm2, ymm2, ymm1 
vpandn ymm2, ymm2, [carrymask] 
vpermd ymm2, ymm2, [lshift32] 
vpaddd ymm1, ymm1, ymm2 

Расчет переноса основан на carry = (x + y) < x, а потому, что нет знака сравнения, это переписать carry = max(x + y, x) != x + y.

Медленный vpermd заставляет меня грустить, ломтики пытаются разрушить все, как обычно, поэтому старый vpslldq на самом деле не работает здесь - если вы не можете переставить qwords, чтобы они также не пересекали 16-байтовые границы.

Конечно, вы можете сохранить переносную маску и lshift32 в регистрах, чтобы эти нагрузки не учитывались.