Существует ли инструкция SIMD для сопоставления индекса памяти в пакетном массиве?

Question

В моем случае RGB к серому:

Y = (77*R + 150*G + 29*B) >> 8;

Я знаю, что SIMD (NEON, SSE2) может делать следующее:

foreach 8 elements:
{A0,A1,A2,A3,A4,A5,A6,A7} = 77*{R0,R1,R2,R3,R4,R5,R6,R7}
{B0,B1,B2,B3,B4,B5,B6,B7} = 150*{G0,G1,G2,G3,G4,G5,G6,G7}
{C0,C1,C2,C3,C4,C5,C6,C7} = 29*{B0,B1,B2,B3,B4,B5,B6,B7}
{D0,D1,D2,D3,D4,D5,D6,D7} = {A0,A1,A2,A3,A4,A5,A6,A7} + {B0,B1,B2,B3,B4,B5,B6,B7}
{D0,D1,D2,D3,D4,D5,D6,D7} = {D0,D1,D2,D3,D4,D5,D6,D7} + {C0,C1,C2,C3,C4,C5,C6,C7}
{D0,D1,D2,D3,D4,D5,D6,D7} = {D0,D1,D2,D3,D4,D5,D6,D7} >> 8

Тем не менее, инструкция умножения занимает не менее 2 тактов, и R,G,B в [0-255], мы можем использовать три таблицы поиска (массив, длина =256) для хранения частичного результата 77*R(отметка как X), 150*G(пометить как Y), 29*B(пометить как Z). Поэтому я ищу инструкции могут сделать намерение:

foreach 8 elements:
{A0,A1,A2,A3,A4,A5,A6,A7} = {X[R0],X[R1],X[R2],X[R3],X[R4],X[R5],X[R6],X[R7]}
{B0,B1,B2,B3,B4,B5,B6,B7} = {Y[G0],Y[G1],Y[G2],Y[G3],Y[G4],Y[G5],Y[G6],Y[G7]}
{C0,C1,C2,C3,C4,C5,C6,C7} = {Z[B0],Z[B1],Z[B2],Z[B3],Z[B4],Z[B5],Z[B6],Z[B7]}
{D0,D1,D2,D3,D4,D5,D6,D7} = {A0,A1,A2,A3,A4,A5,A6,A7} + {B0,B1,B2,B3,B4,B5,B6,B7}
{D0,D1,D2,D3,D4,D5,D6,D7} = {D0,D1,D2,D3,D4,D5,D6,D7} + {C0,C1,C2,C3,C4,C5,C6,C7}
{D0,D1,D2,D3,D4,D5,D6,D7} = {D0,D1,D2,D3,D4,D5,D6,D7} >> 8

Есть хорошие предложения?

Answer 1

В AVX2 / AVX512 нет инструкций по сбору байтов или слов, а в NEON вообще нет сборок. Собранные DWORD гораздо медленнее, чем умножение! например, один на 5 циклов пропускной способности для vpgatherdd ymm,[reg + scale*ymm], ymmв соответствии с таблицей инструкций Агнера Фога для Skylake.

Вы можете использовать перемешивание в качестве параллельного поиска в таблице. Но ваша таблица для каждого поиска составляет 256 16-битных слов. Это 512 байт. AVX512 имеет некоторые тасовки, которые выбирают из конкатенации 2 регистров, но это "только" 2x 64 байта, и их версии размером в байты или слова являются множественными мопами на текущих процессорах. (например, AVX512BWvpermi2w). Они по-прежнему фантастически мощные по сравнению с vpshufb, хоть.

Так что использование shuffle в качестве LUT не будет работать в вашем случае, но в некоторых случаях оно работает очень хорошо, например, для popcount вы можете разбить байты на 4-битные кусочки и использовать vpshufb сделать 32 поиска параллельно из 16-элементной таблицы байтов.

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

---

Смиритесь и используйте pmullw /_mm_mullo_epi16, У вас есть параллелизм на уровне команд, и Skylake имеет 2 на тактовую пропускную способность для умножения 16-битной SIMD (но с задержкой в ​​5 циклов). Для обработки изображений обычно пропускная способность имеет значение больше, чем задержка, если вы удерживаете задержку в разумных пределах, чтобы ее можно было скрыть при выполнении не по порядку.

Если ваших множителей достаточно мало 1 биты в их двоичном представлении, вы можете рассмотреть возможность использования shift/add вместо фактического умножения. например B * 29 = B * 32 - B - B * 2, Или же B<<5 - B<<1 - B, Однако многие инструкции, вероятно, имеют более высокую пропускную способность, чем одно умножение. Если бы вы могли сделать это всего за 2 условия, это могло бы того стоить. (Но опять же, возможно, все еще нет, в зависимости от ЦП. Общая пропускная способность команд и узкие места векторных ALU имеют большое значение.)