Рекомендация в оптимизации ARM NEON

Question

В академических целях я хочу попытаться написать ARM NEON оптимизацию следующего алгоритма, даже для проверки того, можно ли добиться какого-либо улучшения производительности или нет. Я думаю, что это не очень хороший кандидат для оптимизации SIMD, потому что результаты объединены с потерей доходов от параллелизации.

Это алгоритм:

const uchar* center = ...; 

int t0, t1, val; 
t0 = center[0]; t1 = center[1]; 
val = t0 < t1; 
t0 = center[2]; t1 = center[3]; 
val |= (t0 < t1) << 1; 
t0 = center[4]; t1 = center[5]; 
val |= (t0 < t1) << 2; 
t0 = center[6]; t1 = center[7]; 
val |= (t0 < t1) << 3; 
t0 = center[8]; t1 = center[9]; 
val |= (t0 < t1) << 4; 
t0 = center[10]; t1 = center[11]; 
val |= (t0 < t1) << 5; 
t0 = center[12]; t1 = center[13]; 
val |= (t0 < t1) << 6; 
t0 = center[14]; t1 = center[15]; 
val |= (t0 < t1) << 7; 

d[i] = (uchar)val; 

Это то, что я думал, что в ARM сборки:

VLD2.8 {d0, d1} ["center" addr] 

предполагающей 8-битные символы, это первая операция должна загрузить все значения t0 и t1 альтернативно 2 регистра.

VCLT.U8 d2, d0, d1 

отдельная операция «меньше» для всех сравнений. ПРИМЕЧАНИЯ: Я читал, что VCLT возможен только с константой # 0 как второй операнд, поэтому это нужно инвертировать в a> =. Чтение документации ARM. Думаю, результат каждого 8-битного значения будет «все 1» для true (11111111) или «all 0» для false (00000000).

VSHR.U8 d4, d2, #7 

этот сдвиг вправо удалит 7 из 8 значений в регистре 8-битных «клеток» (в основном, чтобы удалить из них 7). Я использовал d4, потому что следующим шагом будет первый регистр d, отображаемый в q2.

Теперь проблемы начинаются: сдвигаются и ОР.

VSHLL.U8 q2[1], d4[1], 1 
VSHLL.U8 q2[2], d4[2], 2 
... 
VSHLL.U8 q2[7], d4[7], 7 

Я могу представить только этот способ (если можно использовать [смещения]) для левых сдвигов. Q2 следует указывать вместо d4 в соответствии с документацией.

VORR(.U8) d4[0], d4[1], d4[0] 
VORR(.U8) d4[0], d4[2], d4[0] 
... 
VORR(.U8) d4[0], d4[7], d4[0] 

Последний шаг должен дать результат.

VST1.8 d4[0], [d[i] addr] 

Простой магазин результата.

Это мой первый подход к ARM NEON, поэтому, вероятно, многие допущения могут быть неверными. Помогите мне понять возможные ошибки и предложите лучшее решение, если это возможно.

EDIT: Это последний рабочий код после предложенных решений:

__asm__ __volatile ("VLD2.8 {d0, d1}, [%[ordered_center]] \n\t" 
"VCGT.U8 d2, d1, d0 \n\t" 
"MOV r1, 0x01 \n\t" 
"MOV r2, 0x0200 \n\t" 
"ORR r2, r2, r1 \n\t" 
"MOV r1, 0x10 \n\t" 
"MOV r3, 0x2000 \n\t" 
"ORR r3, r3, r1 \n\t" 
"MOVT r2, 0x0804 \n\t" 
"MOVT r3, 0x8040 \n\t" 
"VMOV.32 d3[0], r2 \n\t" 
"VMOV.32 d3[1], r3 \n\t" 
"VAND d0, d2, d3 \n\t" 
"VPADDL.U8 d0, d0 \n\t" 
"VPADDL.U16 d0, d0 \n\t" 
"VPADDL.U32 d0, d0 \n\t" 
"VST1.8 d0[0], [%[desc]] \n\t" 
: 
: [ordered_center] "r" (ordered_center), [desc] "r" (&desc[i]) 
: "d0", "d1", "d2", "d3", "r1", "r2", "r3"); 

Answer 1

После сравнения, у вас есть массив из 8 булевых представленных 0xff или 0x00. Причина, по которой SIMD-сопоставления (по любой архитектуре) создают эти значения, заключается в том, чтобы сделать их полезными для операции с битовой маской (и/или бит-select в случае NEON), чтобы вы могли быстро и быстро преобразовать результат в произвольное значение без умножения.

Поэтому, вместо того, чтобы уменьшать их до 1 или 0 и перемещая их, вам будет легче маскировать их с помощью константы 0x8040201008040201. Затем каждая полоса содержит бит, соответствующий его положению в конечном результате. Вы можете предварительно загрузить константу в другой регистр (я буду использовать d3).

VAND d0, d2, d3 

Затем, чтобы объединить результаты, вы можете использовать VPADD (вместо OR), которая будет сочетать в себе соседние пары полос, d0[0] = d0[0] + d0[1], d0[1] = d0[2] + d0[3] и т.д ... Так как битовые образы не не перекрываются нет переносить и добавлять работы так же хорошо, как и. Кроме того, поскольку выход в два раза меньше ввода, мы должны заполнить вторую половину барахлом. Для этого я использовал вторую копию d0.

Вам нужно добавить три раза, чтобы собрать все столбцы.

VPADD.u8 d0, d0, d0 
VPADD.u8 d0, d0, d0 
VPADD.u8 d0, d0, d0 

и теперь результат будет теперь в d0[0].

Как видите, d0 имеет место для еще семи результатов; и некоторые полосы операций VPADD работают с данными мусора. Было бы лучше, если бы вы могли получить больше данных за один раз и подавать дополнительную работу, когда вы идете так, чтобы ни одна из арифметических действий не была потрачена впустую.

---

РЕДАКТИРОВАТЬ

Предположив петлю раскатывают четыре раза; с результатами в d4, d5, d6 и d7; константа упоминалась ранее, должна быть загружена в, скажем, d30 и d31, а затем некоторые q регистре арифметический может быть использована:

VAND q0, q2, q15 
VAND q1, q3, q15 

VPADD.u8 d0, d0, d1 
VPADD.u8 d2, d2, d3 
VPADD.u8 d0, d0, d2 
VPADD.u8 d0, d0, d0 

С конечным результатом в d0 [0..3], или просто 32- бит в d0 [0].

Кажется, есть много регистров, которые могут развернуть его дальше, но я не знаю, сколько из них вы будете использовать при других вычислениях. Регистр объявления

Answer 2

1. нагрузки со значением 0x8040201008040201
2. VAND с результатом ВКПМД
3. vpaddl.u8 от 2)
4. vpaddl.u16 от 3)
5. vpaddl.u32 от 4)
6. магазина самых низкий один байты от 5)

Answer 3

Старта с выражающим параллелизмом явно начать с:

int /* bool, whatever ... */ val[8] = { 
    center[0] < center[1], 
    center[2] < center[3], 
    center[4] < center[5], 
    center[6] < center[7], 
    center[8] < center[9], 
    center[10] < center[11], 
    center[12] < center[13], 
    center[14] < center[15] 
}; 
d[i] = extract_mask(val); 

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

Сравнение вышеуказанных шестнадцати значений может быть выполнено, сначала сделав нагрузку структуры (vld2.8), чтобы разделить смежные байты на два uint8x8_t, а затем на параллельное сравнение. Результатом этого является uint8x8_t с 0xff или 0x00 в байтах. Вы хотите по одному биту в соответствующей позиции бит.

Это «экстракт маски»; на Intel SSE2, который будет MASKMOV, но на Neon нет прямого equiv; три vpadd, как показано выше (или см. SSE _mm_movemask_epi8 equivalent method for ARM NEON для получения дополнительной информации об этом), являются подходящей заменой.